# Creating a DFA that only accepts number of a's that are multiples of 3

I am brand new to DFA's and my first exercise requires me to create a DFA instance such that the number of a's in the string is a multiple of 3. We only have two types of symbols: a, b. To my understanding something like "aaabbaaa" would work but "aabbb" would not. Any help or hints would be greatly appreciated

• What have you tried and where did you get stuck? Can you formulate a grammar or regular expression for that language? What would you do if there were no $b$? What would you do if it were multiples of two? – Raphael Nov 3 '14 at 14:34
• You can find an answer here, I guess this question would count as a duplicate. – john_leo Nov 3 '14 at 14:49
• @john_leo That question is about telling whether an integer is a multiple of 3 from its binary representation. This problem has nothing to do with the question here, which is about telling whether the number of occurrences of a letter in a string is a multiple of 4. – Gilles Nov 4 '14 at 10:45
• Hm, OK, sorry. But it does also say $3$ here. – john_leo Nov 4 '14 at 12:17
• Describe in your own words what the further input has to be if the first symbol is b. Or if it is a. – gnasher729 Oct 4 at 14:58

The key idea here is to make a ring of three states, $q_0, q_1, q_2$ with $a$ transitions \begin{align} q_0 & \stackrel{a}{\rightarrow}q_1\\ q_1 & \stackrel{a}{\rightarrow}q_2\\ q_2 & \stackrel{a}{\rightarrow}q_0 \end{align} On input $aaa$, for example, you'll start in state $q_0$ and pass to state $q_1$ on the first $a$, $q_2$ on the second, and back to $q_0$ on the third $a$. Clearly, any multiple of three $a$s will leave you in state $q_0$, so we make that a final state.
What to do about $b$s in the input? They don't have any effect on the number of $a$s, so include transitions \begin{align} q_0 & \stackrel{b}{\rightarrow}q_0\\ q_1 & \stackrel{b}{\rightarrow}q_1\\ q_2 & \stackrel{b}{\rightarrow}q_2 \end{align} and you're done. In fancier terms, we're $q_n$ to "remember" whether the number of $a$s seen so far was congruent to $n\pmod{3}$. This idiom, using the states to remember certain situations, is fundamental when designing FAs.
We need that the number of $a$'s will be only multiple of $3$, e.g words like $aaa,baaab,bababa,bbbbaaaaaa,\dots$ ets, so we will put the accept state on place such that the number of $a$'s $\mod(3)=0$ e.g $0\mod(3)=0,3\mod(3)=0,6\mod(3)=0,\dots$