53 votes 53 votes 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? $L1 = L2$ $L1 \subset L2$ $L2 \subset L1$ None of the above Theory of Computation gateit-2005 theory-of-computation finite-automata normal + – Ishrat Jahan asked Nov 3, 2014 edited Apr 30, 2019 by Pooja Khatri Ishrat Jahan 16.1k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments Kiyoshi commented Nov 12, 2020 i edited by Kiyoshi Nov 18, 2021 reply Follow Share L2 accepts 101010 but L1 doesn't then how L1=L2. PS : L1 also accepts. 0 votes 0 votes Prateek.py commented Dec 24, 2020 reply Follow Share Both accepts it for L2 repeat state XZZXXZ for L1 XZZXXY @ASNR1010 0 votes 0 votes Pranavpurkar commented Nov 18, 2021 i edited by Pranavpurkar Nov 18, 2021 reply Follow Share @ASNR1010 L1 also accepts 101010. 0 votes 0 votes Please log in or register to add a comment.
Best answer 82 votes 82 votes 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). _Dipak_ answered Apr 1, 2017 edited Jun 15, 2018 by Milicevic3306 _Dipak_ comment Share Follow See all 25 Comments See all 25 25 Comments reply rajoramanoj commented Sep 17, 2017 reply Follow Share nice .... 0 votes 0 votes Brij Mohan Gupta commented Sep 20, 2017 i edited by Puja Mishra Jan 14, 2018 reply Follow Share For reference 25 votes 25 votes sushmita commented Nov 19, 2017 reply Follow Share where is Y to Z edge on 1 as input?? 0 votes 0 votes Mk Utkarsh commented Dec 31, 2017 reply Follow Share sushmita Z to Y on 1 input. similarly Y to Y (input 0) and X to Y(input 0) for Y = 0X + 0Y+ 1Z 0 votes 0 votes Mamta Satywali commented Mar 2, 2018 reply Follow Share How about string '100' which is accepted by Y but not by Z ? 2 votes 2 votes ankitgupta.1729 commented Mar 2, 2018 reply Follow Share @Mamta Satywali ,but 100 is also accepted by Z na .. 0 votes 0 votes Mamta Satywali commented Mar 2, 2018 reply Follow Share 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 2 votes 2 votes ankitgupta.1729 commented Mar 2, 2018 reply Follow Share @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.. 6 votes 6 votes Mamta Satywali commented Mar 2, 2018 reply Follow Share "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. 1 votes 1 votes ankitgupta.1729 commented Mar 2, 2018 reply Follow Share @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.. 2 votes 2 votes Mamta Satywali commented Mar 3, 2018 reply Follow Share @Ankit Thanks a ton! :) 2 votes 2 votes sushmita commented Sep 16, 2018 reply Follow Share But writing in terms of outgoing arrows the expressions don't come same. why so?? 0 votes 0 votes Spider1896 commented Nov 6, 2018 reply Follow Share But when Z is final state it accepts 11011 But Y doesn't accept when Y is final state 0 votes 0 votes Shubhgupta commented Dec 4, 2018 reply Follow Share @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$. 0 votes 0 votes air1ankit commented Dec 12, 2018 reply Follow Share check here ..answer is given option d https://www.geeksforgeeks.org/gate-gate-it-2005-question-37/ –1 votes –1 votes VIDYADHAR SHELKE 1 commented Oct 6, 2019 reply Follow Share Z accept 01* But Y not accept then how 2 equal 0 votes 0 votes ankitgupta.1729 commented Oct 6, 2019 reply Follow Share @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*. 1 votes 1 votes VIDYADHAR SHELKE 1 commented Oct 6, 2019 reply Follow Share thank you 1 votes 1 votes Div1234 commented Jan 6, 2020 reply Follow Share 010 is accepted by L1 but not by L2..please check. 0 votes 0 votes ms sakshi commented Feb 25, 2020 reply Follow Share 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. 0 votes 0 votes Adarsh Pandey commented Jun 19, 2020 reply Follow Share any resource , for where this writing style is taken ......? 0 votes 0 votes ms sakshi commented Jun 24, 2020 reply Follow Share please elaborate....what are you asking? 0 votes 0 votes Adarsh Pandey commented Jun 24, 2020 reply Follow Share 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... 0 votes 0 votes GNANESWARA SAI commented Jan 13, 2023 reply Follow Share Study ardens theorem etc 0 votes 0 votes rhl commented Oct 24, 2023 reply Follow Share After converting to DFA it is easy to see that both will have same final state and hence both languages are same. 4 votes 4 votes Please log in or register to add a comment.
22 votes 22 votes convert this nfa to dfa , you will get the dfa with same final states for both the cases , so option A is correct itsvkp1 answered Aug 30, 2017 itsvkp1 comment Share Follow See all 4 Comments See all 4 4 Comments reply Puja Mishra commented Jan 14, 2018 reply Follow Share Time Consuming ... 0 votes 0 votes pallaviamu commented Apr 7, 2018 i edited by pallaviamu Apr 7, 2018 reply Follow Share @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 1 votes 1 votes kajal84 commented Dec 25, 2019 reply Follow Share Wrong DFA 0 votes 0 votes shashankrustagi commented Jan 17, 2021 reply Follow Share puja mishra, it is not at all time consuming, u just need to be thorough 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 votes converting NFA to DFA, both DFAs are same so,L1=L2 Abhishek Tank answered Oct 29, 2021 Abhishek Tank comment Share Follow See all 3 Comments See all 3 3 Comments reply jainsahil7 commented Aug 4, 2022 reply Follow Share @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 ??? 0 votes 0 votes Pranavpurkar commented Oct 30, 2022 reply Follow Share Helpful👍 0 votes 0 votes sukesh_reddy commented Aug 16, 2023 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Nice Explanation GFg P.s Different ans due to different assumption. Abhisek Tiwari 4 answered Oct 25, 2018 edited Mar 14, 2019 by Abhisek Tiwari 4 Abhisek Tiwari 4 comment Share Follow See all 2 Comments See all 2 2 Comments reply aryavart commented Sep 26, 2021 reply Follow Share Same answer on GFG now 0 votes 0 votes shivmodi94 commented Jul 5, 2022 reply Follow Share GFG solution about interium edges Can we apply only in NFA ? 0 votes 0 votes Please log in or register to add a comment.