抽吸引理顯示`{a^n b^m | n = K中的公里數N}`不規則

Question

我該如何證明L={a^n b^m | n=km for k in N}不是使用泵引理的常規語言？

我開始在N採取字w在L，w=a^n b^m與n=km一些k。 有三種可能的分解爲w：

1. a^i * a^j * a^(n-i-j) b^m
2. a^i * a^(n-i) b^j * b^(m-j)
3. a^n b^i * b^j * b^(m-i-j)

抽水在點2的中間部分）將導致一個混合起來字，這顯然是不在L，但我不明白爲什麼1）不能給你一個很好的分解：

假設你泵a^jx次。那麼新單詞中的a的數量將是i+xj+n-i-j = n+(x-1)j。我們知道一些mn=km。我們必須證明存在x，這樣新的單詞不在L中。但我們假設j=m（這肯定是可能的，因爲n=km總是有足夠數量的a，除非當k=0，但是然後我們得到一個平凡的情況）。然後n+(x-1)j = km+(x-1)m = m(n+x-1)其形式爲{a^n b^m | n=km for k in N}，全部爲x。因此，對於每個w，我們有一個分解uvz，使得u v^i z在L中對於所有i。因此，通過抽象引理，L是規則的。

我錯過了什麼？

編輯：鑑於泵引理的配方：

讓L是由DFA與k成員國接受了正規語言。令w爲L中的任何字，長度爲>= k。然後w可以L寫成u v z與|uv| <=k，v>0和u v^i z所有i>=0

Answer 1

一個也許更簡單的方式來證明這是第一次修改的語言。

由於常規語言是已關閉補充和與另一個正則表達式的交集。

這意味着，你可以證明L是不是證明complement(L)一個普通的語言是不是一個正規的語言，因爲如果L'是一個普通的語言，L越高，反之亦然。這個交點也是一樣。

這足以證明L」不正規以及：

L' = intersection(complement(L),a*b*}) 

因此

L'={a^nb^m|n != k*m, for any k in N} 

然後證明變得比較容易的方式，因爲你可以顯示你使用任何部分作爲抽吸引理，如果它的長度爲l，則可以抽取足夠多次以達到倍數。