使用抽吸引理證明語言不規則

Question

我試圖證明以下語言不是經常使用抽象引理。

L = {A ^ķ b ^3升一個^升 | ķ≥ 1,1 ≥ 0}

我已決定選擇w = A B ^3P一個^p，則| W | = 4p + 1 ≥ p

任何提示？

謝謝！

Answer 1

我不確定您使用的抽吸引理的確切形式。無論如何，這是一個相當棘手的情況，因爲像wikipedia這樣的標準公式只能讓你在固定長度前綴的某個地方抽水。但是，您的初始塊允許在任何地方進行抽吸，並且可以任意長。因此你必須使用一些附加屬性。我建議兩條：

• 正常語言在逆轉時關閉。因此，你可以看看$ L^R = {a^l b^{3l} a^k} $。現在，任何抽到a的最初塊都會導出語言。
• 正常語言在相交處關閉。如果你用b + a +交點，你最終會得到$ {a b^{3l} a^k} $，現在泵入b塊將會把你帶出語言。