Topic: Theory of Computation
Consider the Nondeterministic Finite-State Automaton (NFA) below. States with a small incoming arrow are initial states, while a double circle state denotes a final state. (Diagram shows initial state with a self loop on 'a,b', a transition on 'b' to a second state, and a transition from the second state on 'a,b' to a final state). The number of states in the MINIMAL Deterministic Finite-State Automaton (DFA) for this language is:
- A. 2
- B. 4
- C. 6
- D. 8
Answer: B. 4
Explanation: The given NFA diagram describes the regular expression $(a+b)^{*}b(a+b)$, which represents the language of all strings over {a,b} where the second-to-last symbol is a 'b'. Constructing a minimal DFA for strings where the $k$-th symbol from the end is a specific character requires exactly $2^{k}$ states. Since $k=2$, the minimal DFA requires $2^{2} = 4$ states.