Define a DFA to recognize the language $\mathcal L = \{a^i b^j : (i + j) \pmod 3 = 0\}$.

Question

I am trying to create a DFA for this problem. We need string made up of $a$ and $b$ such that the total number of $a'$s and $b$'s is a multiple of $3$. Moreover, an $a$ should not follow $b$. I know how to get a DFA for a $\mod(3)=0$. Basically, we have to get $a$ three times to reach the final state. However, this question is tricky, so far I am stuck because I don't know how to count the number of $a$'s and $b'$s such that it is a multiple of $3$.

Answer 1

If a should not follow b, then all the a's must precede any of the b's.

Then the language is ($^*$ means zero or more repetitions $^{0|1}$ means 0 or 1 times)

$(aaa)^*(abb|aab)^{0|1}(bbb)^*$

i.e., $3n$ a's $(n \ge 0)$, then aab or aab, then $3m$ bbb's ($m \ge 0$).

If you don't have the restriction of a not following b, it would be

$((a|b)^3)^n$.

A state transition diagran is not hard to determine from these.

Answer 2

The possibilities are:

$\epsilon,abb,aab,aaa,bbb,abbbbb,...$ . notice that in the following automata there is no arrow from some $'b'$ to $'a'$ state.

try this automata:

Answer 3

It will help for this problem to think of how you would write a program to recognize the language, using only a finite number of variables of finite range. In this case, pseudocode like the following should work:

num_symbols_mod_3 := 0
have_seen_b := false
for each c in string
    num_symbols_mod_3 := (num_symbols_mod_3 + 1) mod 3
    if c <> 'a' and c <> 'b'
        REJECT
    if c == 'a' and have_seen_b
        REJECT
    if c == 'b'
        have_seen_b := true
if num_symbols_mod_3 == 0
    ACCEPT
else
    REJECT

Now, num_symbols_mod_3 has only 3 possible values at each step (0, 1, or 2), and have_seen_b has only 2 possible values (true or false). Therefore, there are only 6 possible states overall, and by considering the pseudocode within the loop it should be easy to determine the transitions between these states. Also, from the initialization section you can directly read the initial state; and from the final section you can determine which states are accepting.

Answer 4

DFA with $7$ states $s_0, \cdots, s_6$, initial state $s_0$, accepting states $s_0$ and $s_3$ and transition function $\delta$:

$$\begin{array}{cc} \delta(s_0, b)=s_1, & \delta(s_0, a)=s_5\\ \delta(s_1, b)=s_2, & \delta(s_1, a)=s_4\\ \delta(s_2, b)=s_3,& \delta(s_2, a)=s_4\\ \delta(s_3, b)=s_1,& \delta(s_3, a)=s_4\\ \delta(s_4, b)=s_4,& \delta(s_4, a)=s_4\\ \delta(s_5, b)=s_1, &\delta(s_5, a)=s_6\\ \delta(s_6, b)=s_2&\delta(s_6, a)=s_0 \end{array}$$