Construct DFA for L = {(na(w)-nb(w)) mod 3>0}

Question

As per the title:

L = {(n_a(w)-n_b(w)) mod 3>0}

Alphabet = {a,b}

I found two answers to this problem:

In this solution, our language is accepted.

However,

w = b

is accepted as well.

In the next solution:

Our problem of

w = b

is solved here but

w = aaab

is not accepted.

How do I approach this problem? I couldn't find a suitable answer for it on the internet.

Answer 1

Assume we have the following definition of mod:

x mod y = {       x,       if 0 <= x < y
            (x - y) mod y, if 0 <  y <= x
                  x,       if -y < x < 0
            (x + y) mod y, if x <= -y < 0
            -(-x mod -y)   if y < 0
          }

So our modulus works like this:

3 mod 5 = 3
6 mod 5 = 6-5 mod 5 = 1 mod 5 = 1
-3 mod 5 = -3
-6 mod 5 = -6+5 mod 5 = -1 mod 5 = -1
-6 mod -5 = -(6 mod 5) = -1
6 mod -5 = -(-6 mod 5) = -(-1) = 1

Our language is L = {(n_a(w) - n_b(w)) mod 3 > 0}

Let's define A := n_a(w) and B := n_b(w). So we need to solve (A - B) mod 3 > 0 using our definition of mod. We have five cases:

1. if 0 <= A - B < 3, meaning B <= A < B + 3, then (A - B) mod 3 = A - B. By hypothesis it is at least zero, and can only be zero then if A = B. We can confirm that when A = B we are always in case #1 and we always have (A - B) mod 3 > 0 false, so we can throw that possibility out.

2. if 0 < 3 <= A - B, meaning B < 3 + B <= A or simply A >= 3 + B, then (A - B) mod 3 = (A - B - 3) mod 3. By the hypothesis, A - B - 3 >= 3 + B - B - 3 >= 0, so we are still in either case 1 or 2. If we remain in case 2, we can repeat this until we eventually reach case 1, and we will see that we cannot have A - B - 3k = 0; that is, it cannot be that A = B + 3k for any positive k.

3. if -3 < A - B < 0, or B - 3 < A < B, then (A - B) mod 3 = A - B. By the hypothesis it is less than zero, and so we must throw out all of these possibilities.

4. if A - B <= -3 < 0, meaning A <= B - 3 < B or simply A <= B - 3 then (A - B) mod 3 = (A - B + 3) mod 3. By the hypothesis, A - B + 3 <= B - 3 - B + 3 = 0, so we are still in either case 3 or 4. If we remain in case 4, we can repeat this until we eventually reach case 3, and we will see nothing remains.

5. We cannot be in this case since 3 > 0.

We had to throw out the following strings from our language:

• A = B
• A = B + 3k
• A < B.

So we keep only strings with more a's than b's where A - B is not divisible by 3. Suppose this language were regular. Consider the string (b^p)(a^(p+1)) in the language. By the pumping lemma, we should be able to pump the number of bs; but then we could get more bs than as. So the language cannot be regular.

If we take what is maybe a more usual definition for x mod y (not more correct, necessarily):

x mod y = {        x       , if 0 <= x < y
                (x - y)    , if 0 < y <= x
            (x + y) mod y  , if -y < x < 0
            -(-x mod -y)   , if y < 0
          }

By this definition:

1. in case 1, we throw out A = B
2. in case 2, we throw out A = B + 3k
3. in case 3, we throw out A = B - 3k
4. since 3 > 0, case 4 doesn't apply

Now we have only thrown out the cases where A mod B = 0 (mod 3). This language is regular and has DFA:

    +------------a-------------+
    |                          |
    |  +---b----+  +---b----+  |
    |  |        |  |        |  |
    V  V        |  V        |  |
    (q0)---a--->(q1)---a--->(q2)
--->(q0)
    (q0)---b--->(q3)---b--->(q4)
    ^  ^        |  ^        |  |
    |  |        |  |        |  |
    |  +---a----+  +---a----+  |
    |                          |
    +------------b-------------+