0 0 votes Consider the following NFA:- How many final states required in the equivalent DFA? Theory of Computation theory-of-computation finite-automata number-of-states + – rahul sharma 5 1.6k views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Rishabh Gupta 2 commented Nov 20, 2017 reply Follow flag haha Your drawing :P try this next time: http://madebyevan.com/fsm/ It accepts strings with "ba" substring. So, it will have 3 states and one will be final. 0 0 replyShare rahul sharma 5 commented Nov 20, 2017 reply Follow flag I will use that tool next time.:p But here it is not mentioned that DFA need to be minimal. And subset construction gives 4 as answer.So will it be 3 or 4? 0 0 replyShare Rishabh Gupta 2 commented Nov 20, 2017 reply Follow flag Two DFAs are equivalent if they accept the same language. A DFA and NFA are equivalent if they accept the same language. They are asking for the equivalent DFA, so the question becomes ambiguous. But, we have unique minimized DFA, so I would go for 3 states, with 1 final state. 0 0 replyShare Please log in or register to add a comment.
1 1 vote regular expression of given language = (a+b)* ba (a+b)* {every string contains "ba" as sub string} In general, |w| length sub string contain |w|+1 states in DFA Hence, 3 states are required in which one is final state. Akash Mittal answered Nov 20, 2017 • edited Nov 20, 2017 by Akash Mittal Akash Mittal comment Share Follow See 1 comment 1 1 comment reply rahul sharma 5 commented Nov 20, 2017 reply Follow flag If you go with subset construction it will given 4.Why did you minimize to 3? 0 0 replyShare Please log in or register to add a comment.
0 0 votes there will be only one final state.. better to check by making equivalent DFA... Ankit Srivastava 7 answered Nov 20, 2017 Ankit Srivastava 7 comment Share Follow 0 reply Please log in or register to add a comment.
