TOC:- DFA

Question

Consider the following NFA:-

How many final states required in the equivalent DFA?

Comments

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.

---

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?

---

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.

Answer 1

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.

Comments

If you go with subset construction it will given 4.Why did you minimize to 3?

Answer 2

there will be only one final state..

better to check by making equivalent DFA...