GATE IT 2005 | Question: 37

Question

Consider the non-deterministic finite automaton (NFA) shown in the figure.

State $X$ is the starting state of the automaton. Let the language accepted by the NFA with $Y$ as the only accepting state be $L1$. Similarly, let the language accepted by the NFA with $Z$ as the only accepting state be $L2$. Which of the following statements about $L1$ and $L2$ is TRUE?

• A. $L1 = L2$
• B. $L1 \subset L2$
• C. $L2 \subset L1$
• D. None of the above

Comments

what about string 010 it is Accepted in L1 but not in L2

---

See for L2 or L1 for the string 010 first it traverses from X->Z->Y and from here for L1 it loops and for L2 from Y if we give last 0 as the remaining input then it comes back to Z.. hope you understand..

---

010 is accepted by both, look at that like : {X} --0--> {Y,Z}  --1--> {Φ,Y} --0--> {Y,Z} and at the end we can be in either Y or Z and

{Y,Z} ∈ L1, also {Y,Z} ∈ L2

Answer 1

Misprints : Edge $Y \rightarrow Z$ ( $0$ edge )
                   Edge $Z \rightarrow Y$ ( $1$ edge )

Answer: A.

Explanation:

Writing $Y$ and $Z$ in terms of incoming arrows (Arden's method) :

$Y = X0 + Y0 + Z1$

$Z = X0 + Z1 + Y0$

Hence $Y=Z$. So, option (A).

Comments

For the  Above Diagram of NFA

I can prove that this A is false as the correct answer is B 

Consider feeding small strings starting from 0,1,00,10,11,01, and you will find that the string 001 is not accepted by Y but is accepted by Z so yeah, hence proven L1 != L2 

answer is B as Y is the Proper Sub-set of Z 

---

Language $L1$ will accept string $001$ if you follow the path $X\xrightarrow{0}Y \xrightarrow{0} Z \xrightarrow{1}Y$

---

bruh 001 is accepted by Y,
X----0---->Y----0---->Z----1---->Y

Answer 2

convert this nfa to dfa , you will get the dfa with same final states  for both the cases , so option A is correct

Comments

Time Consuming ...

---

@itsvkp1 yes the two DFA's will be exactly same except the final states, for L1 DFA the no of final states=4 whereas for L2 it is 1 only.. then how are two languages equal?

Please explain

---

Wrong DFA

---

puja mishra, it is not at all time consuming, u just need to be thorough

---

no since there are no epsilon moves it becames easy to covert it to dfa in this case .

Answer 3

converting NFA to DFA,

both DFAs are same so,L1=L2

Comments

this can be further minimized, so at the end both the DFA's will be equivalent with exact same states and transitions. There will be finally 2 states, one non-final and one final. (as yz and xyz these two states will be merged in the minimized DFA.

---

the answer should be D 
because "00" is accepted by L1 but not by L2
also "01" is accepted by L2 but not by L1

---

@fixer_GOD "00"is also accepted by L2. reason :x->y->z
similarly check for "01" it is also accepted by L!. reason:x->z->y
AS it is NFA check in all possible ways

Answer 4

The core reason is that NFAs are ambiguous to analyze directly.

---

The Problem with NFAs

In an NFA, from one state you can go to multiple states simultaneously on the same input. So when you ask:

"Does this string get accepted?"

You can't just follow one path — there could be many possible paths, and the string is accepted if any one of them leads to an accepting state.

This makes it hard to compare languages directly.

SO convert nfa to dfa .....and then you can trace the strings easily 

Answer 5

Nice Explanation GFg

P.s Different ans due to  different assumption.

Comments

Same answer on GFG now

---

GFG solution about interium edges
Can we apply only in NFA ?

Answer 6

Alternate solution,

If we make a DFA out of it, then the states Y and Z are always combined together.

If Z is final state then Y is also the final state and vice versa.

Therefore, they represent the same language.