429 views
0 votes
0 votes
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"

2 Answers

0 votes
0 votes

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".

 

Related questions

1 votes
1 votes
3 answers
2
1 votes
1 votes
1 answer
3
Souvik33 asked Dec 4, 2022
332 views
Consider the following statementS: $\left \{ a^{n}b^{n+k}|n\geq 0,k\geq 1 \right \} \cup \left \{a^{n+k}b^{n}|n\geq 0,k\geq 3 \right \}$ is DCFLThe above statement is:TRU...
0 votes
0 votes
0 answers
4