Pumping引理援助

Question

我最近有一項任務，我被要求用抽象引理來表明一種語言不規律，不幸的是得到了錯誤的答案。

證明該語言是非正規如下： L = {A ^我 b ^ĴÇ^ķ：ⅰ= j的或j = K}

泵送的定義我給出引理如下：

1. 對手拿起米
2. 我要挑w至頂撞抽水引理。用m選擇一個字符串w∈L其中| w | ≥m
3. 對手挑選w受限制的分解。
4. 我儘量挑一個我，使泵送列W _我∉L.如果找到，L是不正規

這個主題已經被證明是非常困難的，我聽不懂，我覺得因爲它是一個完整的空氣頭，所以我將不勝感激如何詳細解釋如何正確應用抽吸引理。

Answer 1

直觀上，抽吸引理指出，用正則語言L足夠長的單詞（長度僅取決於語言L）必須包含一個長度大於0的部分，這個部分可以根據需要經常重複。重複該部分（'抽取'原始單詞）任意數量的時間導致一些更長的單詞也是語言L.

該單詞的最小長度是上述定義的第一步中的m;該部分重複的次數是上述定義的第4步中的i。

抽吸引理通常用於表明語言L不規則。這是一個矛盾的證明：假設L是有規律的，因此L的正則語言的抽象引理對於L是真的。然後選擇一個長度足夠長的L，並且表明不管它是如何分解的*一些抽取的單詞不在語言中。這與抽吸引理相矛盾 - 我們知道這是真實的。因此，我們假設語言是正常的是錯誤的，因此語言是不規則的。用*標記的部分不能被選擇來使事情變得簡單 - 這就是爲什麼在步驟1和3中「對手」選擇它們。

單詞w被重寫爲w = x y z，其中| y | > 0和| x y | < = m。 x和z的長度都可以是0.

通常的做法是將xy選爲由相同字母組成的字符串，使得具有更多相同字母（泵送後）導致字不在L

對帖子中的語言L中的i或k沒有限制，因此假定允許i = 0，合適的詞可能是b^mc^m（即m bs後跟m CS）。現在無論對手選擇何種分解，y總是由一些bs組成。重複那些bs導致一個單詞比bs更多而不是cs，因此i！= j和j！= k並且該單詞不在該語言中。