patternMinor
Why the extra state in this automaton?
Viewed 0 times
thiswhythestateautomatonextra
Problem
Why does the following DFA have (to have) the state $b_4$?
Shouldn't states $b_1,b_2,b_3$ already cover "exactly two 1s"?
Wouldn't state $b_4$ mean "more than two 1s", even if it doesn't trigger an accept state?
Shouldn't states $b_1,b_2,b_3$ already cover "exactly two 1s"?
Wouldn't state $b_4$ mean "more than two 1s", even if it doesn't trigger an accept state?
Solution
$b_4$ is what is called a trap state, that is, a state that exists just so that all possible transitions are explicitly represented, even those that do not lead to a final state.
It doesn't change the language that is being defined, and can be omitted for the sake of brevity.
It doesn't change the language that is being defined, and can be omitted for the sake of brevity.
Context
StackExchange Computer Science Q#49325, answer score: 7
Revisions (0)
No revisions yet.