# DFA for $L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv 0$ $(mod$ $5) \}$

There is a language: $L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv 0$ $(mod$ $5) \}$. My idea for DFA is - we count number of $a$$\pmod{5} and separately we count number of b$$\pmod{5}$. So we end up with $5*5=25$ states, because each state have to keep track for both number of $a$ and $b$$\pmod{5}$. Is there any better aproach to this DFA ? Because for example when we have$\pmod{10}$ we end up with 100 states. I would appreciate any sugestions.

• It is better to run two automata in parallel if you are simulating. Otherwise make two separate automata and $L_a\bigcap L_b$. May 31 '17 at 11:32

The minimal DFA for $L$ contains 25 states, as can easily be shown using Myhill–Nerode theory.
Indeed, consider the 25 words $\{a^ib^j : 0 \leq i,j < 5\}$. I will show that when a DFA reads any two different words from this list, it cannot end up in the same state. To show this, for any two different words $x,y$ from the list, I will give a word $z$ such that $xz \in L$ but $yz \notin L$.
Let $x = a^i b^j$ and $y = a^k b^\ell$ be two different words from the list. Since $x \neq y$, either $i \neq k$ or $j \neq \ell$ (or both). Assume without loss of generality that $i \neq k$. Take $z = a^{5-i} b^{5-j}$. Then $|xz|_a = |xz|_b = 5$, and so $xz \in L$. In contrast, $|yz|_a = 5-i+k \not\equiv 0 \pmod{5}$, since $i \not\equiv k \pmod{5}$ by assumption, showing that $yz \notin L$.