Consider the regular expression (0+1)*1(0+1). The minimum state finite automaton that recognizes the language represented by this regular expression contains: A. 3 states B. 5 states C. n+2 states D. None of the above

GATE 1999 · Theory of Computation · Minimal State Automata · easy

Answer: The minimum state DFA has 3 states. Answer: A. 3 states.

1. Identify Myhill-Nerode equivalence classes: Class A: strings where second-to-last is not 1 (or length < 2 and last char is 0, or empty). Residual: need a '1' then any bit to accept. Class B: strings whose last character is 1 (but second-to-last is unknown or 0). Residual: reading any one bit accepts. Class C: strings where second-to-last is 1. Residual: these strings already satisfy the suffix condition — reading one more bit accepts immediately (already in accept after reading that bit from class B). Actually the accept state is when we just verified second-to-last=1.
2. Verify 3 states are necessary and sufficient: q0 and q1 are distinguishable because from q0, reading '10' accepts (10 in L) but from q1, reading '0' also accepts. However q0 on string '0' rejects while q1 on '0' accepts — so they are distinguishable. q2 (after reading '10') vs q1 (after reading '1'): from q2 reading empty string: q2 IS the accept state so they differ from q0. All 3 states are pairwise distinguishable, so minimum is 3.