DFA for $L_1={w:(n_a(w)+2n_b(w)) mod 3<2}$ and $L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$

Question

I stumbled upon this file on scribd, which gave some interesting problems on constructing DFA. So I went on solving them, until I came across one for which result DFA is not drawn but are described in words and I feel the description is incorrect.

The first language reads like this:

$L_1=\{w:(n_a(w)–n_b(w)) \text{mod 3} > 0 \}$

The solution goes like this:

• DFA states have meaning.
• There will be three states counting number of a's occurred till now in the input string mod 3. Similarly there will be three states counting number of b's occurred till now in the input string mod 3.
• So total states will be $3\times 3=9$. Say state $01$ means $n_a(w)\text{mod 3}=0$ and $n_b(w)\text{mod 3}=1$.
• The slides say that states with label $10, 20, 01$ and $21$ will be final states.

Q.1 However, I feel state $01$ should not be the final state, simply because $0-1\text{ mod 3}=-1\text{mod 3}=-1\not\gt0$. Am I correct?

Similarly, the second language is:

$L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$

The slide explains this as follows:

• The DFA will have similar states and transitions as in case of above language, with below changes.
• As $b$'s go in the sequence: 0, 1, 2, 0, ...; $2b$ goes in the sequence: 0, 2, 1, 0,...
• So change the label 01 with 02, 11 with 12, 21 with 22, 02 with 01, 12 with 11 and 22 with 21.
• Change accepting states in above language to 00, 10 and 01.

Q.2 However I feel this is incorrect interpretation of the language. I interpreted as follows:

State n_a(w)    n_b (w) (n_a(w)+2n_b(w))mod 3       Is final state?
00    0         0       (0+0) mod 3 = 0 < 2         Yes
01    0         1       (0+2) mod 3 = 2             No
02    0         2       (0+4) mod 3 = 1 < 2         Yes
10    1         0       (1+0) mod 3 = 1 < 2         Yes
11    1         1       (1+2) mod 3 = 0 < 2         Yes
12    1         2       (1+4) mod 3 = 2             No
20    2         0       (2+0) mod 3 = 2             No
21    2         1       (2+2) mod 3 = 1 < 2         Yes
22    2         2       (2+4) mod 3 = 0 < 2         Yes

where n_a(w) means "number of a's encountered so far in the input string" and n_b(w) means "number of b's encountered so far in the input string"

Am I correct with this?

Answer 1

As Yuval noted, you can do this with three states. Since the behavior of the FA depends only on $(n_a(w)-n_b(w)) \mod 3$, if we interpret the question as $(.)\mod 3$ can be only 0, 1, or 2, then we'll have three states: $q_0, q_1, q_2$ where $q_i$ will represent having seen a number of $a$s and $b$s so far such that $(n_a(w)-n_b(w))\mod 3 = i$.

Now consider being in state $q_0$. That means that $(n_a(w)-n_b(w))\mod 3 = 0$, so if we encounter an $a$, we'll have seen input $w'=wa$ and so we'll then have $n_a(w')=n_a(w)+1$ so $n_a(w')-n_b(w')=n_a(w)-n_b(w)+1\equiv (0+1)\pmod 3$ so we'll change to state $q_1$. In a similar way, seeing a $b$ will take us from $q_0$ to $q_2$. Doing this for the other two states will yield the transition table $$ \begin{array}{c|cc} & a & b \\ \hline q_0 & q_1 & q_2 \\ q_1 & q_2 & q_0 \\ q_2 & q_0 & q_1 \end{array} $$ with start state $q_0$ and final states $q_0$ and $q_1$.

Answer 2

For your first question, the mod 3 operation is understood to yield a result in 0,1,2. If you consider instead the "arithmetic modulo" operation which returns a signed result, then the language $L_1$ is no longer regular.

For your second question, $a-b$ and $a+2b$ are the same modulo 3. Draw your own conclusions.

For both questions, the minimal DFAs actually consist of only 3 states.