GATE CS 2007 Q29 — Regular Expressions and Finite Automata

To find the number of states in the minimum state DFA, we can analyze the requirements for tracking the number of $0$s and $1$s in any input string $w$:

1. Condition on $0$s: The number of $0$s must be divisible by $3$. To track $n_0(w) \pmod 3$, we need $3$ states corresponding to remainders $\{0, 1, 2\}$.
2. Condition on $1$s: The number of $1$s must be divisible by $5$. To track $n_1(w) \pmod 5$, we need $5$ states corresponding to remainders $\{0, 1, 2, 3, 4\}$.

Since the count of $0$s and $1$s are independent of each other, we construct a product automaton. The states of this DFA are represented as ordered pairs $(r_0, r_1)$, where:

The total number of states in this product automaton is:

Distinguishability:

• The start state is $(0, 0)$, which is also the only accepting state (since both remainders must be $0$).
• All $15$ states are reachable from the start state.
• For any two distinct states $(i_1, j_1)$ and $(i_2, j_2)$, we can always find a string that drives one to the accepting state $(0,0)$ and the other to a non-accepting state. Thus, all $15$ states are pairwise distinguishable.

Therefore, the minimum state DFA has exactly $15$ states.