I have a language $\{a^m b a^n | m+n \equiv 1 mod 3\}$

  • $m+n$ can be 1, 4, 7, 10, 13, 16, 19, 22, ...
  • $m+n$ is the number of all $a$'s in the word

How can I build a DFA for this language?

  • $\begingroup$ 1. Please proof-read your question. Something came out horribly wrong. In particular, your specification of the language is incoherent -- double-check your use of Latex. 2. What have you tried? We expect you to make a significant effort before asking here, and to show us what you tried and where you got stuck. $\endgroup$ – D.W. Mar 9 '15 at 16:38
  • $\begingroup$ I don't want to prove the language is regular, I want to know how the DFA of the language will look like. $\endgroup$ – jannnik Mar 9 '15 at 16:48
  • 1
    $\begingroup$ The answers to cs.stackexchange.com/q/1331/755 should suffice for constructing a DFA. They tell you how to construct a DFA (which is what you want) or a NFA (which you can convert to a DFA) or a regular language (which you can convert to a DFA). See also cs.stackexchange.com/q/7879/755. $\endgroup$ – D.W. Mar 9 '15 at 16:51

Consider six nodes $v_0,v_1,v_2$ and $v_0', v_1', v_2'$, where $v_0$ is the initial state. The automaton is in state $v_i$ if we have already outputted $x \equiv i \mod 3$ times the character 'a' before we outputted a 'b'. Between $v_0$ and $v_1$, between $v_1$ and $v_2$ and between $v_2$ and $v_0$, we add a transition with output 'a'.

The same is done for the nodes $v_0'$, $v_1'$, and $v_2'$, i.e., we are in state $v_i'$ iff the total number (including the part before and the part after the 'b') of outputted 'a' equals $x \equiv i \mod 3$. Correspondingly, we connect $v_0'$ and $v_1'$, $v_1'$ and $v_2'$, and $v_2'$ and $v_0$ with transitions outputting 'a'.

Now we connect each $v_i$ with the corresponding $v_i'$ by a transition with output 'b' (since the output of a 'b' doesn't change the number of 'a' in the string). By assigning $v_1'$ to be the final state, we are done.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much! After drawing the DFA the solution seems to be very easy but I think I would have never found the solution on my own. Is there a kind of algorithm or trick for building DFA's like this one? $\endgroup$ – jannnik Mar 9 '15 at 15:01
  • $\begingroup$ Just Practice :) $\endgroup$ – user1742364 Mar 9 '15 at 15:50
  • 1
    $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Mar 9 '15 at 19:05

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