抽象引理是什麼，你如何做？

Question

所以我有一個抽吸引理問題A{www|w ∈ {a,b}*} 我有正確的答案，但我不完全確定它是如何工作的。我給的答案只是讓人們知道我會與

假設A是REG 設P爲抽長 x ∈ A, x=a^p b, a^p b, a^p b .... |s|=3p+3 其中每個a^p b是AW

令S = XYZ使得 1分裂）sum of i>=0s'=xy'z ∈ A 2）|x|>0，3）|xy| <=p

通過（3）Y只包含的和由（2）Y含有至少1。 讓s'= xyyz，那麼s=a^+ ba^p ba^p b,

1）s'∈A，因爲它包含矛盾t> p 即。 REG的不是一個元素

Answer 1

我不認爲你會得到cs.stackexchange更好的答案，但這裏的基本概況：

的泵引理（普通語言;還有的對上下文更復雜的一個語言）是關於常規語言的一個結果，它說「如果L是常規語言，那麼就有一個整數p，這樣L中至少和p一樣長的每個單詞可以分成x，y和z三個部分，這樣xz∈L，xyz∈L，xyyz∈L，xyyyz∈L等。「 （還有一些細節，如y的長度至少爲1，xy的長度爲< = p，因此請查看維基百科的正式聲明）。「p」通常被稱爲語言的「抽長」。

這個結果通常被用作一種方式來證明一個語言不是正規 - 這些證據說類似工作：

1. 如果我是定期的，那麼它將有一個抽水長度P作爲抽水引理。

2. 構造比字母長的字符串。通常這個字符串最終會比p個字母長很多，但是在開始時會有一些字母很長的部分，以使下一步更容易。

3. 表明，當你「泵」這個字符串（也就是，當你重複的部分「Y」一些多次），你得到的東西，是不是在語言L.

4. 因此，抽水引理不適用於L，因此L不規則。

請注意，您不能反向使用此證明語言是正常的！你只能用它來證明一種語言是不規則的，偶爾它可以用來證明一種常規語言包含某些類型的字符串。

示例證明遵循該格式。下面是另一個證明，從最近的計算器問題採取：

L = {w ∈ {0,1}* | w has an odd length and the middle character is 0} 

現在，證明L不是常規：

如果我是普通，它會泵送長度P。考慮字符串s ='1'* p +'0'+'1'* p - 該字符串在L中且長於p個字符。因此，由抽吸引理可以將x，y，z分成三部分，即| xy | < = p，| y |> 0，並且像xyyyz這樣的字符串在L.

但是由於s的構造方式，我們知道y部分只包含'1'個字符，字符串xyyyz只有一個'0'字符，並且'0'左側的'1'字符比右側更多，所以xyyyz不在L.

因此，L不規則。