GATE CS 2020 Q51 — Regular and Context-free Languages

Let $n_a(x)$ denote the number of $a$’s in the string $x$. The language $L$ is defined as:

This condition can be analyzed modulo $6$ (since $\text{lcm}(2, 3) = 6$):

• $n_a(x)$ is divisible by $2$ if $n_a(x) \equiv 0, 2, 4 \pmod 6$.
• $n_a(x)$ is divisible by $3$ if $n_a(x) \equiv 0, 3 \pmod 6$.

For $n_a(x)$ to be divisible by $2$ but not by $3$, we must have:

Thus, the language only depends on the count of $a$’s modulo $6$. We can construct a DFA with $6$ states, $Q = \{q_0, q_1, q_2, q_3, q_4, q_5\}$, where state $q_i$ represents $n_a(x) \equiv i \pmod 6$. The start state is $q_0$ and the set of accepting states is $F = \{q_2, q_4\}$. Since transitions on $b$ do not change the state, we only transition on $a$ to the next state modulo $6$.

To verify if any states can be merged, we test pairwise distinguishability. For any two states $q_i$ and $q_j$ ($0 \le i < j \le 5$), we can find a string of $a$’s of length $k$ that distinguishes them (i.e., drives one to an accepting state and the other to a non-accepting state). Since all $6$ states are pairwise distinguishable, the DFA is already minimal.

Therefore, the minimum number of states in the DFA is 6.