TheGateAcademy Test Series

Question

In DFA, does each state need to have transition on "EACH" input alphabet?

The answer was given "False" but I dont think so. Can anyone explain?

Because if this statement is False, then there is no use of "Dead State"

Comments

@Devshree, yes that is evident, but what the concerned doubt over here was that "whether for every state, there should be transition on EACH alphabet". 

For example if $\sum {a,b}$  , then a state Q_i should have a defined transition on  both a and b

---

Yes it should be corect statement.

---

Made Easy and Ace Academy are known for irrelevant and incorrect solutions as well. The given statement is true.

Answer 1

I think its true , if anyone finds counter example then please explain it too.

Answer 2

Gentle bump - I believe this question is referring to a passage in Hopcroft-Ullman taken out of context. Refer to the last paragraph of attached excerpt. It seems to say without a transition for each alphabet, the automaton is an NFA - BUT, the resultant DFA will be very similar with just the addition of the dead states. i.e., it is true out of convenience, but not in a strict academic sense.

The key takeaway is from the passage is "we shall sometimes refer to an automaton as a DFA if it has at most one transition out of any state on any symbol rather than if it has exactly one transition".