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

L2 accepts 101010 but L1 doesn't then how L1=L2.

PS : L1 also accepts.

---

Both accepts it for L2 repeat state XZZXXZ

 for L1  XZZXXY

@ASNR1010

---

@ASNR1010

L1 also accepts 101010.

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

nice ....

---

For reference

---

where is Y to Z edge on 1 as input??

---

 sushmita Z to Y on 1 input.  similarly Y to Y (input 0) and X to Y(input 0) for Y = 0X + 0Y+ 1Z

---

How about string '100' which is accepted by Y but not by Z ?

---

@Mamta Satywali ,but 100 is also accepted by Z na ..

---

Case1 When only Y is accepting state- Start from X and use input string "100" , it will end up in Y which is accepting state.Hence 100 is in L1.

Case2 When only Z is accepting state- Start from X and use input string "100" ,it will end up in X which is not accepting state.Hence 100 is not in L2.

Maybe I am missing out something really stupid :p

---

@Mamta Satywali , yes it is true that we may end up on state X for the string 100... But it is also possible that We may end up in states Y and Z on string 100... But in case of  NFA ,if we get final state after input string "w" from all possible state transitions which are started with initial state then string "w" will definetely be in the language...This thing was explained in one of the videos of Shai Simonson sir... So , here string 100 can go in final state Z ..So , it will definitely be in the language L2..

---

"But it is also possible that We may end up in states Y and Z on string 100"

Please briefly explain-how your above statement true? I am stuck.

---

@Mamta Satywali ,1) start from X ,do self loop on 1 , then on 0 , go to Y ..again self loop on Y , u will end up on state Y here...

2)start from X ,do self loop on 1 , then on 0 , go to Y , then on 0 , go to Z .. here u will end up on state Z..

---

@Ankit Thanks a ton! :)

---

But writing in terms of outgoing arrows the expressions don't come same. why so??

---

But when Z is final state it accepts 11011 But Y doesn't accept when Y is final state

---

@Spider1896, it can accept 11011 when Y is final state by through $X\overset{1}{\rightarrow}X\overset{1}{\rightarrow}X\overset{0}{\rightarrow}Z\overset{1}{\rightarrow}Z\overset{1}{\rightarrow}Y$.

---

check here ..answer is given option d

https://www.geeksforgeeks.org/gate-gate-it-2005-question-37/

---

Z accept 01* But Y not accept then how 2 equal

---

@VIDYADHAR SHELKE 1

Y also accepts :)

If string is '0'. Go from $X$ to $Y$ directly.

If string is '01'. Go from $X$ to $Z$ and then go $Z$ to $Y$.

If string is '011'. Go from $X$ to $Z$. Self loop on Z one time and then go $Z$ to $Y$.

If string is '0111'. Go from $X$ to $Z$. Self loop on Z two times and then go $Z$ to $Y$.

like this you can process 01*.

---

thank you

---

010 is accepted by L1 but not by L2..please check.

---

for L1={010}

from X to Z on 0, Z to Y on 1, then Y on self-loop with 0. So, string accepts on accepting state Y.

for L2={010}

from X to Z on 0, Z to Y on 1, then Y to Z on 0. So, string accepts on accepting state Y.

---

any resource , for where this writing style is taken ......?

---

please elaborate....what are you asking?

---

I want to know how to write state diagram into this kind of expressions ...

 

Y=X0+Y0+Z1
Z=X0+Z1+Y0

Any resource to learn that properly...

---

Study ardens theorem etc

---

After converting to DFA it is easy to see that  both will have same final state and hence both languages are same.

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

Answer 3

converting NFA to DFA,

both DFAs are same so,L1=L2

Comments

@Abhishek Tank how do you know after converting nfa to dfa that state yz represents y only and state xyz represents state z of nfa ???

---

Helpful👍

---

how far dose it make logical scene to make “xyz” a final state because just “x” is a final state . Can this be done in any other case.

Answer 4

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 ?