Consider the following language.
L = {x in {a, b}* | number of a's in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is _________
GATE 2020 · Theory of Computation · Regular Language · medium
Answer: The minimum number of states in a DFA that accepts L is 6.
Determine the period of the condition: The condition '#a's divisible by 2 but not by 3' depends on #a's mod 2 and #a's mod 3. By the Chinese Remainder Theorem, this is equivalent to tracking #a's mod LCM(2,3) = mod 6. The accepted residues mod 6 are those n where n mod 2 = 0 and n mod 3 != 0: n in {0,1,2,3,4,5}: n=0: 0 mod 2=0, 0 mod 3=0 => NO. n=1: 1 mod 2=1 => NO. n=2: 2 mod 2=0, 2 mod 3=2 => YES. n=3: 3 mod 2=1 => NO. n=4: 4 mod 2=0, 4 mod 3=1 => YES. n=5: 5 mod 2=1 => NO. So accepting states correspond to residues {2, 4}.
Construct the minimum DFA: States: q0, q1, q2, q3, q4, q5 (representing #a's mod 6). Start state: q0. Accepting states: q2, q4. Transitions on a: qi -> q_{i+1 mod 6}. Transitions on b: self-loop. All 6 states are distinguishable: q0 and q3 differ from accepting states, q1/q3/q5 are odd residues, q2 and q4 accept while q0 does not.
Verify minimality: Consider strings a^0, a^1, a^2, a^3, a^4, a^5. For any two qi and qj with i != j (mod 6), the string a^{(2-i) mod 6} distinguishes them (one accepts, the other doesn't, considering all residue combinations). So all 6 states are pairwise distinguishable. No state can be merged.