DFA構造爲L = {（NA（w）的-nb（W））模3> 0}

Question

作爲每標題：

L = {（N _一個（W）-n _b （W））模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)。所以我們需要使用我們的定義mod來解決(A - B) mod 3 > 0。我們有五個情況：

1. 如果0 < = A - B < 3，意思是乙< = A < B + 3，則（A - B）模3 = A - B.通過假設它是在如果A = B，我們可以確定當A = B時，我們總是遇到＃1，並且我們總是（A - B）mod 3> 0爲假，所以我們可以拋出這種可能性出。

2. 如果0 = A - B，這意味着乙< 3 + B < = A或簡稱A> = 3 + B，則（A - B）模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 - 乙< 0，或B - 3 <甲< B，則（A - B）模3 = A - B.通過將假設它小於零，所以我們必須拋出所有這些可能性。

4. 如果A - B < = -3 < 0，意味着甲< = B - 3 < B或簡單地阿< = B - 3然後（A - B）模3 =（A - B + 3）MOD根據假設，A - B + 3 < = B - 3 - B + 3 = 0，所以我們仍然處於3或4的情況。如果我們仍然處於第四種情況，我們可以重複這一點，直到我們最終到達案例3，我們什麼也看不到。

5. 我們不能在這種情況下，由於3> 0

我們不得不把從我們的語言以下字符串：

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

所以我們只保留比a更多的字符串，而A不能被3整除。假設這種語言是規則的。考慮語言中的字符串（b^p）（a ^（p + 1））。通過抽象引理，我們應該能夠抽取數字b;但那麼我們可以得到比a更多的b。所以語言不可能是常規的。

如果我們採取什麼是可能的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 =乙
2. 在情況2中，我們扔掉A = B + 3K
3. 在情況3中，我們扔掉A = B - 3K
4. 自3> 0，case 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-------------+