Consider the regular expression (0+1)(0+1)...(0+1), where (0+1) is repeated n…
1999
Consider the regular expression (0+1)(0+1)...(0+1), where (0+1) is repeated n times. The minimum-state finite automaton that recognizes the language represented by this regular expression contains:
- A.
n states
- B.
n + 1 states
- C.
n + 2 states
- D.
None of the above
Attempted by 34 students.
Show answer & explanation
Correct answer: C
The correct answer is: n + 2 states.
The expression (0+1)(0+1)...(0+1), with (0+1) repeated n times, denotes all binary strings of exactly length n.
A complete DFA must keep track of how many symbols have been read:
q0: 0 symbols read
q1: 1 symbol read
...
qn: n symbols read, accepting state
These give n + 1 states. However, if any more symbol is read after reaching qn, the string has length greater than n and must be rejected. Therefore the complete DFA needs one additional dead state, which loops on both 0 and 1.
Total states = (n + 1) counting states + 1 dead state = n + 2.