# How can I build a DFA for ${a^m b a^n | m+n \equiv 1 mod 3}$? [duplicate]

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?

## marked as duplicate by D.W.♦, Raphael♦Mar 9 '15 at 19:05

• 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. – D.W. Mar 9 '15 at 16:38
• I don't want to prove the language is regular, I want to know how the DFA of the language will look like. – jannnik Mar 9 '15 at 16:48
• 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. – 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.