构造L的DFA = {（（na（w）-nb（w））mod 3> 0}

Question

按照标题：

L = {（（n _a（w）-n _b（w））mod 3> 0}

字母= {a，b}

我找到了这个问题的两个答案：

在此解决方案中，我们的语言被接受。

然而，

w = b

也被接受。

在下一个解决方案中：

我们的问题

w = b

在这里解决了，但是

w = aaab

不被接受。

我该如何解决这个问题？我在互联网上找不到合适的答案。

Answer 1

假设我们具有以下定义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
          }

所以我们的模数是这样的：

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

我们的语言是L = {（（n_a（w）-n_b（w））mod 3> 0}

让我们定义A := n_a(w)和B := n_b(w)。因此，我们需要(A - B) mod 3 > 0使用的定义进行求解mod。我们有五种情况：

1. 如果0 <= A-B <3，意味着B <= A <B + 3，则（A-B）mod 3 = A-B。通过假设，它至少为零，并且只能为零，则如果A = B.我们可以确认，当A = B时，总是情况为＃1，并且总是（mod-3）mod 3> 0 false，因此可以排除这种可能性。

2. 如果0 <3 <= A-B，意味着B <3 + B <= A或简单地A> = 3 + B，则（A-B）mod 3 =（A-B-3）mod 3。 ，A-B-3> = 3 + B-B-3> = 0，所以我们仍然处于情况1或2。如果我们仍然处于情况2，则可以重复此操作，直到最终达到情况1，然后将看到我们不能有A-B-3k = 0; 也就是说，对于任何正数k都不能为A = B + 3k。

3. 如果-3 <A-B <0或B-3 <A <B，则（A-B）mod 3 = A-B。根据假设，它小于零，因此我们必须排除所有这些可能性。

4. 如果A-B <= -3 <0，表示A <= B-3 <B或简单地A <= B-3，则（A-B）mod 3 =（A-B + 3）mod 3。 ，A-B + 3 <= B-3-B + 3 = 0，所以我们仍然处于情况3或4。如果我们仍然处于情况4，则可以重复此操作，直到最终到达情况3，我们将看到什么都没有。

5. 因为3> 0，所以我们不能在这种情况下。

我们不得不从我们的语言中抛出以下字符串：

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

因此，我们只保留a大于b的字符串，其中A-B不能被3整除。假设该语言是常规的。考虑该语言中的字符串（b ^ p）（a ^（p + 1））。通过抽引引理，我们应该能够抽出bs 个数；但是我们可以得到b比as 多的s。因此语言不可能是正规的。

如果我们采用更常见的定义x mod y（不一定更正确，则必定）：

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
          }

通过这个定义：

1. 在情况1中，我们抛出A = B
2. 在情况2中，我们抛出A = B + 3k
3. 在情况3中，我们抛出A = B-3k
4. 由于3> 0，因此情况4不适用

现在我们仅排除了A mod B = 0（mod 3）的情况。该语言是常规语言，具有DFA：

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