Consider the following language. $$L = \{x \in \{a, b\}^*| \text{ number of } a\text{'s in } x \text{ is divisible by 2 but not divisible by 3}\}$$ The minimum number of states in a DFA that accepts $L$ is _______.

Let $n_a(x)$ denote the number of occurrences of symbol '$a$' in string $x$.

The condition states:

1. $n_a(x)$ is divisible by 2 $\implies n_a(x) \equiv 0 \pmod 2$

2. $n_a(x)$ is not divisible by 3 $\implies n_a(x)

ot\equiv 0 \pmod 3$

Consider the count of $a$'s modulo $\operatorname{lcm}(2, 3) = 6$:

• $n_a(x) \pmod 6 \in \{0, 1, 2, 3, 4, 5\}$

• Divisible by 2: $\{0, 2, 4\}$

• Not divisible by 3: $\{1, 2, 4, 5\}$

• The intersection is $\{2, 4\}$.

Thus, the DFA must track $n_a(x) \pmod 6$, requiring 6 states (corresponding to remainders $0, 1, 2, 3, 4, 5$). By the Myhill-Nerode theorem, strings $a^0, a^1, a^2, a^3, a^4, a^5$ are mutually distinguishable, so no states can be merged.

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