Minimum-State DFA for Joint Modulo Counts

We consider the language over $\Sigma=\{0,1\}$:

$$L=\{w\in\{0,1\}^*\mid \#0(w)\equiv 0\pmod 3 \ \text{and}\ \#1(w)\equiv 0\pmod 5\}.$$

Here $\#0(w)$ and $\#1(w)$ denote the number of $0$’s and $1$’s in $w$.

The key idea is that a DFA only needs to remember:

• the remainder of $\#0(w)$ modulo $3$ and
• the remainder of $\#1(w)$ modulo $5$.

We will build a DFA via product construction and then argue that it is minimal (so the number of states matches the correct option among (i) 15, (ii) 11, (iii) 10, (iv) 9).

Important concepts:

• DFA
• Myhill-Nerode
• Product construction
• Congruence modulo

Constructing a DFA that tracks remainders

Define two DFAs:

1. A DFA $A_0$ over $\{0,1\}$ that tracks $\#0(w)\bmod 3$.

   • It has states $\{0,1,2\}$ representing the current remainder of $\#0$.
   • On input symbol:
     • reading a $0$ increments the remainder mod $3$,
     • reading a $1$ leaves the remainder unchanged.

2. A DFA $A_1$ over $\{0,1\}$ that tracks $\#1(w)\bmod 5$.

   • It has states $\{0,1,2,3,4\}$ representing the current remainder of $\#1$.
   • On input symbol:
     • reading a $1$ increments the remainder mod $5$,
     • reading a $0$ leaves the remainder unchanged.

Then $L$ is the intersection of:

• strings where $\#0(w)\equiv 0\pmod 3$ and
• strings where $\#1(w)\equiv 0\pmod 5$.

So the DFA for $L$ is the product automaton whose state is the pair:

$$(r_0,r_1)\in \{0,1,2\}\times\{0,1,2,3,4\},$$

meaning $r_0\equiv \#0(w)\pmod 3$ and $r_1\equiv \#1(w)\pmod 5$.

That yields exactly $3\cdot 5=15$ states before minimization.

Mermaid view of product tracking:

Why the minimum DFA has 15 states (no merging possible)

To prove minimality, we show that all $15$ remainder-pairs represent distinct equivalence classes under the Myhill–Nerode relation.

Let two strings $x$ and $y$ reach different pairs:

$$(r_0(x),r_1(x))\neq (r_0(y),r_1(y)).$$

We will produce a distinguishing suffix $z$ such that exactly one of $xz, yz$ is in $L$.

Case 1: $r_0(x)\neq r_0(y)$

So $r_0(x)\in\{0,1,2\}$ differs from $r_0(y)$ modulo $3$. Choose a suffix consisting only of $0$’s:

$$z = 0^{\,t},\quad \text{where } t\equiv -r_0(x)\pmod 3.$$

Then:

• For $xz$: the number of additional $0$’s makes $\#0(xz)\equiv 0\pmod 3$.
• For $yz$: since $r_0(y)\not\equiv r_0(x)\pmod 3$, adding the same $t$ cannot make both remainders zero simultaneously; thus $\#0(yz)\not\equiv 0\pmod 3$.

Because $z$ contains no $1$’s, the $\#1(\cdot)\bmod 5$ part is unchanged for both. Hence exactly one of $xz$ and $yz$ lies in $L$.

Case 2: $r_1(x)\neq r_1(y)$

Symmetric argument using a suffix only of $1$’s:

$$z = 1^{\,s},\quad \text{where } s\equiv -r_1(x)\pmod 5.$$

Then $xz$ fixes $\#1(xz)\equiv 0\pmod 5$, but $yz$ fails because the modulo-5 remainder differs, while the $\#0$ modulo-3 remainder is unchanged.

Therefore, if two states (remainder pairs) differ in either component, they are distinguishable by some suffix, so they cannot be merged.

Conclusion: the constructed product DFA is already minimal, with exactly

$$3\cdot 5 = 15$$

states.