The number of states in the minimum sized DFA that accepts the language…
2016
The number of states in the minimum sized DFA that accepts the language defined by the regular expression
\((0+1)^∗ (0+1)(0+1)^∗\)
is ___________ .
Attempted by 139 students.
Show answer & explanation
Correct answer: 2
Key insight: the middle (0+1) forces at least one symbol, so (0+1)* (0+1) (0+1)* is the set of all non-empty binary strings (all strings over {0,1} of length ≥ 1).
Minimal DFA construction:
State 1 (start, non-accepting): represents that no symbol has been seen yet. On input 0 or 1 transition to State 2.
State 2 (accepting): represents that at least one symbol has been seen. On input 0 or 1 stay in State 2.
Why two states are necessary:
The empty string ε is not in the language, while the single-symbol string "0" is in the language. These two strings must be placed in different DFA states (they are distinguishable), so at least two states are required.
Conclusion: The minimum number of states in a DFA accepting the language is 2.
A video solution is available for this question — log in and enroll to watch it.