Question 61

Let $N_a(x)$ denote the number of $a$'s in string $x$. The acceptance condition requires:

Examine $N_a(x) \bmod 6$ (since $\text{lcm}(2, 3) = 6$):

• $r = 0$: $0 \bmod 2 = 0$, but $0 \bmod 3 = 0$ (Fails).
• $r = 1$: $1 \bmod 2 = 1$ (Fails).
• $r = 2$: $2 \bmod 2 = 0$ and $2 \bmod 3 = 2 \ne 0$ (Accepts).
• $r = 3$: $3 \bmod 2 = 1$ (Fails).
• $r = 4$: $4 \bmod 2 = 0$ and $4 \bmod 3 = 1 \ne 0$ (Accepts).
• $r = 5$: $5 \bmod 2 = 1$ (Fails).

DFA state requirements:

• A DFA must track the remainder $r = N_a(x) \bmod 6$, requiring 6 states $q_0, q_1, q_2, q_3, q_4, q_5$.
• Transitions: on input $a$, $q_i \to q_{(i+1) \bmod 6}$; on input $b$, self-loop $q_i \to q_i$.
• Accepting states: $\{q_2, q_4\}$.
• Using the Myhill-Nerode theorem, any two states $q_i$ and $q_j$ ($0 \le i < j \le 5$) are distinguishable by appending $a^k$ for a suitable $k$. None of the 6 states can be merged.
• Therefore, the minimum number of states is 6.