-1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Raphael Nov 3 '14 at 14:34
  • $\begingroup$ You can find an answer here, I guess this question would count as a duplicate. $\endgroup$ – john_leo Nov 3 '14 at 14:49
  • $\begingroup$ @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. $\endgroup$ – Gilles Nov 4 '14 at 10:45
  • $\begingroup$ Hm, OK, sorry. But it does also say $3$ here. $\endgroup$ – john_leo Nov 4 '14 at 12:17
  • $\begingroup$ Describe in your own words what the further input has to be if the first symbol is b. Or if it is a. $\endgroup$ – gnasher729 Oct 4 at 14:58
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

Try this DFA:enter image description here

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