GATE CSE 2003 | Question: 55

Question

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?

• A. $L_1 = \{0,1\}^*-L$
• B. $L_1 = \{0,1\}^*$
• C. $L_1 \subseteq L$
• D. $L_1 = L$

Comments

Please make appropriate corrections in GO PDF book in next edition

---

IN DFA we can find language Of Dfa and for finding language of non state <-->state dfa we can just compliment of dfa language 
but same statement is not true for NFA
Here u have to make nfa and find language of newly created nfa

---

\[
\begin{aligned}
L &= (0+1)^+(0+01) + 1, \\[4pt]
 L_{q_2} &= (0+1)^+, \\[4pt] L_{q_3} &= (0+1)^*0 + \epsilon, \\[4pt] L_1 &= L_{q_2} \cup L_{q_3} \\ &= (0+1)^+ \cup \left((0+1)^*0 + \epsilon\right) \\ &= (0+1)^+ + (0+1)^*0 + \epsilon \\ &= (0+1)^*.
\end{aligned}
\]

Answer 1

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.

Comments

L1 is superset of L

---

Nicely Explained !

---

if c given as L subset of L1 then it will be true

Answer 2

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:-  

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

Comments

Please explain option a) too. You've explained everything else so well!

---

Option a) isn't right.

Reason :

• Automaton 'M' accepts string {1} also i.e. L = {1, ...}
• {0,1}* represents {null, 0, 1, 00, 01, 10, 11,……………..}
• {0,1}* - L removes the string {1} from the solution set, which isn't true because automaton 'M1' accepts string{1} also, i.e. L1 = {null, 0, 1, 00, 01, 10, 11,……………..}

---

applying complementation to nfa is right ???does this approach always give the write  answer???

or we need to change the nfa to dfa then complementation........clear plz??

---

What does option A actually mean?

---

L1 contains all the strings that are not in L. This is wrong as both L and L1 contain many strings in common. Ex: “1”,”00” etc.

---

L1 = {0, 1}* −  L  == {0, 1}* intersection  L’.

---

Option A means L1 is complement of L

Answer 3

Correct statement is B.

 

Answer 4

L= (0+1)^+ while L1= (0+1)^* So Ans is B

Comments

How we can say L = (0+1)^+ ? NFA is not generating all the strings of (0+1)^+.

---

sure L is not (0+1)⁺ as in NFA 0 is not accepting.

Answer 5

@Bikram sir   What will be answer for question given in go pdf? Option C? L1is subset of L? Please confirm

Comments

option B.

Answer 6

In case of DFA we can say that by changing the final and non final states you get complement of the given language but in case of NFA it is not true because : 

For NFA, A string is accepted if there exists at least one path that leads to a final state. It is only rejected if all possible paths lead to non-final states.So, simply interchanging the states does not work here so we have to manually analyse based on the given NFA 

As we can see from the diagram that both L and the new language L1 accept 1 so (A) can't be true now C and D is also not possible simply because L1 accepts more language than L does hence we can say (B) is correct also can verify that language id indeed {0,1}* 

(Like string 0 is not accepted by L but L1 accepts it)