Consider the language L given by the regular expression (a+b)*(a+b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ___________.

GATE 2017 · Theory of Computation · Minimal State Automata · medium

Answer: The minimum number of states in a DFA accepting L is 2.

1. Identify the language: L is the set of all strings over {a,b} of length >= 1. The empty string epsilon is NOT in L. Every non-empty string is in L.
2. Determine minimal DFA states using Myhill-Nerode: For Myhill-Nerode, we look at right-congruence classes. String x ~_L y iff for all z: xz in L <=> yz in L. Class 1: epsilon — epsilon*z is in L iff z is non-empty. Class 2: any non-empty string w — w*z is always in L (for any z, including z=epsilon). These two classes are distinct: epsilon is not in L but 'a' is. So there are exactly 2 equivalence classes => minimal DFA has 2 states.