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 9.6k 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.