ME work book

Question

How many states are there in a minimum state FA accepting {0, 01, 011, 001} ?

Please provide complete DFA. I got 6 states but answer is 5 states.

Comments

ya we need to add a dead state for that

---

but then the no of states would be 6

---

read the question once and than what has been asked.. u will get the answer.

Answer 1

if you read the question. you will notice that they have asked for number of states in minimal FA that can accept the given sequence of strings.

and #states minimum FA = minimum(DFA,NFA)

                           =NFA

as nfa will always have #states <= Dfa #states.

as for the given question we will have 5states for NFA and 6states for DFA. 

so the answer should be 5states for minimal finite automata.

and 6 if they have asked for minimal DFA.