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?