Design a finite automata by checking division of number of characters

Question

I need to design and draw a finite automata that can accept the letters {a,b}.

The number of the the letters a should be devided by 3, and the number of the letter b should be devided by 2.

For example the following samples should be accepted by the automata:

aaabb, baaba, bbaaabaaba

Thanks in advance.

Answer 1

Hint:

This is such a nice task, so I will give only this little help.

• It is only about words from $L=\{a,b\}^*$
• What FA would accept the words with a number of $a$ symbols divisible by $3$?
• What FA would accept the words with a number of $b$ symbols divisible by $2$?
• How could you construct a FA that combines both former FAs? How would one combine the states and final states of the first with the states and final states of the second FA to get states and final states for the combined FA?

Answer 2

HINT: Use the states to keep track of the numbers of $a$s modulo $2$ and the number of $b$s modulo $3$. That is, use states $q_{0,0},q_{0,1},q_{0,2},q_{1,0},q_{1,1}$, and $q_{1,2}$, and design the automaton so that it is in state $q_{i,j}$ when the number of $a$s is of the form $2m+i$ and the number of $b$s is of the form $2n+j$ for some non-negative integers $m$ and $n$.

• How must the transitions go?
• Which of these states should be the initial state?
• Which state(s) should be acceptor state(s)?