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

Question

根据标题:

L = {(na(w)-nb(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 的定义.我们有五种情况:

如果 0 <= A - B < 3，意味着 B <= A < B + 3，则 (A - B) mod 3 = A - B。根据假设它至少为零，并且只能为零，如果 A = B. 我们可以确认，当 A = B 时，我们总是处于情况 #1 并且我们总是有 (A - B) mod 3 > 0 假，所以我们可以排除这种可能性。

如果 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 < A - B < 0，或 B - 3 < A < B，则 (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))。由抽引引理，我们应该可以抽到b的数量。 s;但是我们可以得到更多 b比a 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 中，我们抛出 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-------------+