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.5k 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 Show 22 previous comments 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.
