Topic: Theory of Computation
Consider the deterministic finite-state automaton (DFA) below over the alphabet {a,b}. The state with a small incoming arrow is the initial state, while a double circle state denotes a final state.
The number of states in the MINIMAL DFA for the language accepted by this DFA is:
- A. 1
- B. 2
- C. 3
- D. 4
Answer: B. 2
Explanation: The DFA has an initial non-final state $S_0$ and two final states $S_1$ and $S_2$. $S_2$ has self-loops on 'a' and 'b', making it a final sink state that accepts everything. $S_1$ loops to itself on 'b' and goes to $S_2$ on 'a', meaning from $S_1$, any sequence of 'a' and 'b' is also accepted. Because $S_1$ and $S_2$ are both final states from which any string leads to acceptance, they are equivalent and can be merged into a single final state $S_F$. The minimal DFA consists of 2 states: the initial non-final state $S_0$ and the merged final state $S_F$.