GATE 2020 CS Q.51: solution and answer

Official answer: 6Source: Official answer key, GATE 2020 CS (IIT Delhi)

1. Only the number of $a$'s matters: a $b$ leaves the situation unchanged. So it is enough to track $n_a\mathrm{mod}6$, because this fixes both $n_a\mathrm{mod}2$ and $n_a\mathrm{mod}3$ (6 = 2 x 3, coprime).

2. A string is in $L$ exactly when $n_a\mathrm{mod}6\in \{2,4\}$. Residue 0 is divisible by 3, so it is excluded. Residues 1, 3 and 5 are odd, so they are excluded. Residues 2 and 4 are even and not divisible by 3.

3. So a 6-state DFA works: states $q_0,\dots ,q_5$, $\delta (q_i,a)=q_{(i+1)\mathrm{mod}6}$, $\delta (q_i,b)=q_i$, start state $q_0$, accepting states $\{q_2,q_4\}$.

4. Minimality: from $q_i$, the string $a^k$ is accepted iff $(i+k)\mathrm{mod}6\in \{2,4\}$. So the set of $k\in \{0,\dots ,5\}$ accepted from $q_i$ is $\{2-i,4-i\}\mathrm{mod}6$.

5. For $i=0,\dots ,5$ these sets are $\{2,4\},\{1,3\},\{0,2\},\{5,1\},\{4,0\},\{3,5\}$. All six are different, so for any two states some $a^k$ is accepted from one and rejected from the other. Every pair of states is distinguishable.

6. No two states can be merged. The DFA is complete (every state has a transition on both symbols), so no extra dead state is needed. The minimum number of states is $6$.