6 votes 6 votes The minimum number of states of the non-deterministic finite automaton which accepts the language $\{ a b a b^n \mid n \geq 0 \} \cup \{ a b a^n \mid n \geq 0 \}$ is 3 4 5 6 Theory of Computation ugcnetcse-dec2012-paper3 theory-of-computation finite-automata + – go_editor asked Jul 13, 2016 • recategorized Oct 10, 2018 by Pooja Khatri go_editor 10.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 10 votes 10 votes L={ababn∣n≥0}∪{aban∣n≥0} L={ab, aba , abaa ,abab ,ababb,..........} The minimum number of states of the non-deterministic finite automaton which accepts the language =5 Hence,Option(c)5 is the correct choice. LeenSharma answered Jul 13, 2016 • edited Jul 13, 2016 by LeenSharma LeenSharma comment Share Follow See all 14 Comments See all 14 14 Comments reply shekhar chauhan commented Jul 13, 2016 reply Follow Share @leen why do we need 4 state here can't we make a transaction on b in the 3rd state itself. 0 votes 0 votes LeenSharma commented Jul 13, 2016 i edited by LeenSharma Jul 13, 2016 reply Follow Share no. we ca't draw it in 3 states. According to you Nfa is Now you can see it can accept string ababab which is not accepted by given grammar. 0 votes 0 votes shekhar chauhan commented Jul 13, 2016 reply Follow Share I understood this . I have one more confusion if we don't make 4th state as final and make transition on b and accept in 3rd state only would that be a problem. ? could you please write 3-4 strings of this lang after union of them then i would be able to understand it easily.and that will help me to understand you above comment diagram easily. 0 votes 0 votes LeenSharma commented Jul 13, 2016 reply Follow Share L1={ ababn |n≥0} The strings accepted by L1={aba , abab , ababb , ababbb.......... } L2={ aban |n≥0} The strings accepted by L1={ab , aba , abaa , abaaa.......... } Now what is L1 ∪ L2 ? L1 ∪ L2 is a language which is accepted by L1 or L2. L1 ∪ L2={ ababn |n≥0} ∪ { aban |n≥0} The strings accepted by L1 ∪ L2 ={ab , aba , abaa , abab , ababb , abaaa.......... } state q3 required to accept minimum length string ab. state q4 required because we can't able to accept abb here. we can't draw self loop for both a and b at state q3. 1 votes 1 votes shekhar chauhan commented Jul 13, 2016 reply Follow Share @leen Thank you so much for your response ...I appreciate it 1 votes 1 votes LeenSharma commented Jul 13, 2016 reply Follow Share you are most welcome 0 votes 0 votes Praveen Saini commented Jul 13, 2016 reply Follow Share I think abaab should not belong to L 1 votes 1 votes LeenSharma commented Jul 13, 2016 reply Follow Share Yes i did mistake. 1 votes 1 votes shekhar chauhan commented Jul 13, 2016 reply Follow Share @leen there is correction your FA it is accepting abaab which is not the string in language 0 votes 0 votes LeenSharma commented Jul 13, 2016 reply Follow Share Praveen Saini Number of states should be 5 here. Right? 0 votes 0 votes LeenSharma commented Jul 13, 2016 reply Follow Share @yes correction required.I will update soon. 0 votes 0 votes LeenSharma commented Jul 13, 2016 reply Follow Share Praveen Saini Sir please check this 1 votes 1 votes Praveen Saini commented Jul 13, 2016 reply Follow Share yes now it is correct update in answer 0 votes 0 votes LeenSharma commented Jul 13, 2016 reply Follow Share Thank You sir 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes answer : 4 Correct me if I am wrong sh!va answered Jul 13, 2016 sh!va comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments One commented Jul 28, 2016 i reshown by gatecse May 14, 2021 reply Follow Share ok I got it in case of NFA it is fine 0 votes 0 votes sh!va commented Mar 10, 2017 i reshown by gatecse May 14, 2021 reply Follow Share Yes, This NFA wrongly accepts the string abaaaaabbb.. which does not belong to L Answer is wrong 1 votes 1 votes Priyanshu2602y commented Dec 10, 2023 reply Follow Share @sh!va thanks your point makes a difference here now i got it 0 votes 0 votes Please log in or register to add a comment.