Let L be the set of all binary strings whose last two symbols are same. The…
1998
Let L be the set of all binary strings whose last two symbols are same. The number of states in the minimal state deterministic finite-state automaton accepting L is
- A.
2
- B.
5
- C.
8
- D.
3
Attempted by 29 students.
Show answer & explanation
Correct answer: B
The language is the set of binary strings whose last two symbols are equal, so it is described by the regular expression (0 + 1)*(00 + 11).
A DFA must remember enough recent history to decide whether the last two symbols are 00 or 11. The minimal states can be understood as:
Start state: no symbol has been read yet.
2. Non-accepting state ending in 0, but not yet ending in 00. This covers strings like 0 or strings ending in 10.
3. Non-accepting state ending in 1, but not yet ending in 11. This covers strings like 1 or strings ending in 01.
4. Accepting state ending in 00.
5. Accepting state ending in 11.
These states cannot be merged. For example, the two accepting states ending in 00 and 11 are distinguishable because appending 0 keeps the 00-state accepting but takes the 11-state to a non-accepting state ending in 10. Similarly, the non-accepting states ending in 0 and 1 are distinguishable by appending 0 or 1. The start state is also distinct because it has no last symbol yet.
Therefore, the minimal DFA requires 5 states.