edited by
14,222 views
45 votes
45 votes

Consider the NFA $M$ shown below.

Let the language accepted by $M$ be $L$. Let $L_1$ be the language accepted by the NFA $M_1$ obtained by changing the accepting state of $M$ to a non-accepting state and by changing the non-accepting states of $M$ to accepting states. Which of the following statements is true?

  1. $L_1 = \{0,1\}^*-L$
  2. $L_1 = \{0,1\}^*$
  3. $L_1 \subseteq L$
  4. $L_1 = L$
edited by

5 Answers

Best answer
73 votes
73 votes

Answer is B .

As the problem said:

As in above NFA language $L_1$ is $\{0,1\}^*$ . [we don't know $L$, we need not to find out]

Option A is wrong as $L$ is accepting $1$ and $L_1$ is also accepting $1$ 

Option C is wrong as $L_1$ accepting ^,null, but $L$ is not .

Option D is wrong for same reason as option C is wrong.

edited by
20 votes
20 votes

In case of a Deterministic Finite Automata (DFA) when we change
the accepting states into non-accepting states and non-accepting
states into accepting states, the new DFA obtained accepts the complement
of the language accepted by the initial DFA. It is because we have one
single movement for a particular input alphabet from one state so the strings
accepted by the transformed DFA will be all those which are not accepted by
the actual DFA. 

But it is not the case with the NFA’s (Non-Deterministic Finite
Automata). In case of NFA we need to have a check on the language accepted by the
NFA. The NFA obtained by changing the accepting states to non-accepting states and
non-accepting states to accepting states is as follows:-  

nfa

Here we can see that as
i.  The initial state is an accepting state hence null string is always accepted by
    the NFA.
ii. There is a movement from state 1 to state 2 on both {0, 1} input alphabets and
    further any  number of 1’s and 0’s or even none in the string lets the string be
    at an accepting state(state 2).

Hence the language accepted by the NFA can be any string with any combination of 0’s
and 1’s including a null string i.e. {null, 0, 1, 00, 01, 10, 11,……………..}

so L1= {0, 1}*.

So,answer is B

3 votes
3 votes
L= (0+1)^+ while L1= (0+1)^* So Ans is B
Answer:

Related questions

61 votes
61 votes
7 answers
1
Kathleen asked Sep 17, 2014
14,797 views
Consider the following deterministic finite state automaton $M$.Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $...