GATE CS 2001 Q2.5 — Regular Expressions and Finite Automata

To find the minimum number of states in the DFA, we can use the product construction of two simpler DFAs:

1. DFA $M_1$: Accepts strings where the number of $a$'s is divisible by $6$. This requires tracking the count of $a$'s modulo $6$, which needs exactly $6$ states: $\{0, 1, 2, 3, 4, 5\}$.
2. DFA $M_2$: Accepts strings where the number of $b$'s is divisible by $8$. This requires tracking the count of $b$'s modulo $8$, which needs exactly $8$ states: $\{0, 1, 2, 3, 4, 5, 6, 7\}$.

The product automaton $M = M_1 \times M_2$ tracks both conditions simultaneously. The state set of $M$ is the Cartesian product of the state sets of $M_1$ and $M_2$:

The total number of states in this product DFA is $6 \times 8 = 48$.

Minimality Proof:

Two states $(r_1, c_1)$ and $(r_2, c_2)$ are equivalent if and only if they behave identically for all future inputs. The only accepting state in the product DFA is $(0,0)$.

For any state $(r, c)$, the string $w = a^{6-r} b^{8-c}$ transitions the DFA to the accepting state $(0,0)$. If we apply this same string $w$ to a different state $(r', c')$, it will transition to $( (r' - r) \bmod 6, (c' - c) \bmod 8 )$, which is accepting if and only if $r' = r$ and $c' = c$.

Since every state has a unique distinguishing string that leads to the accepting state, all $48$ states are pairwise distinguishable. Thus, the DFA is already minimal.

Therefore, the minimum number of states is 48.