-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Feb 22 '16 at 5:39
  • $\begingroup$ Also, please ask only one question per post. You've been given this feedback before: 1, 2, 3. See our help center if you'd like to learn more about expectations regarding this site. Thank you. $\endgroup$ – D.W. Feb 22 '16 at 5:44
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In Q.1 , if mod 3 was considered to yield 0,1,2, like $|n_a(w)–n_b(w))\text{mod 3}|>0$, then states $12$ and $02$ should also be final states. Right? Just like $01$ is specified as accepting state by the slide. In Q.2 I didnt get your point. Even I follow what you said, the answer does not seem to change. And even by slide's states labeling, I feel $12$ which corresponds to $11$ in my states labeling, $22$ which corresponds to $21$ in my states labeling & $21$ which corresponds to $22$ in my states labeling should also be accepting states. $\endgroup$ – anir123 Feb 21 '16 at 15:59
  • $\begingroup$ In Q1, all states other than 00,11,22 should be final states. In Q2, there are many ways of labelling the states. Perhaps you and the scribd file are using different labelling conventions. Don't dwell too much on it. $\endgroup$ – Yuval Filmus Feb 21 '16 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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