1
$\begingroup$

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.

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.