为 L = {(na(w)-nb(w)) mod 3>0} 构造 DFA

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
          }

所以我们的 modulus 是这样工作的：

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)。所以我们需要使用我们对 mod 的定义来解决 (A - B) mod 3 > 0。我们有五个案例：

if 0 <= A - B < 3, 意思是B <= A < B + 3, then (A - B) mod 3 = A - B. 假设它至少为零，并且如果 A = B 则只能为零。我们可以确认，当 A = B 时，我们总是在情况 #1 中并且我们总是有 (A - B) mod 3 > 0 false，所以我们可以排除这种可能性。
如果 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。
if -3 < A - B < 0, or B - 3 < A < B, then (A - B) mod 3 = A - B. 由假设它小于零，所以我们必须排除所有这些可能性。
如果 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，然后我们将什么都看不到。
我们不能在这种情况下，因为 3 > 0。

我们不得不从我们的语言中剔除以下字符串：

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

所以我们只保留 a 多于 b 的字符串，其中 A - B 不能被 3 整除。假设这种语言是正则的。考虑语言中的字符串 (b^p)(a^(p+1)) 。通过泵引理，我们应该能够泵出 bs 的数量；但是我们可以得到比 as 更多的 bs。所以语言不能正则

如果我们采用 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 中，我们抛出 A = B
在情况 2 中，我们抛出 A = B + 3k
在情况 3 中，我们抛出 A = B - 3k
因为 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-------------+

为 L = {(na(w)-nb(w)) mod 3>0} 构造 DFA

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

automata

finite-automata

dfa