是（a^p）（b^q）常規語言

Question

我在某處讀到{（a^p）（b^q）：p，Q屬於N}是一種常規語言。但是，我不認爲這是正確的。這可以用抽象引理證明。只是想驗證我的解決方案是否正確

讓y是ab。因此，x（y^n）z不屬於L，因爲當n> = 1時，在a之前會有一些b。但是，表達式不允許這樣做。因此，（一^ P）（B^Q）是不是一個RL

Answer 1

這是前一段時間我用泵引理，但一個^p b ^q絕對是一個正規語言。爲它寫一個正則表達式甚至是微不足道的！ 一個 * b *

外觀相似一個^p b ^p是不正規，但因爲開始消耗b -symbols時，你需要記住多少一個你消耗的符號，有限自動機不能「記住」任意數字。這對你的情況不是問題！

Answer 2

抽吸引理說： 如果一個語言A是規則=>有一個數字p（抽長度），如果s是L中的任何字符串，使得| s | > = p，則S可以被分成三件S = XYZ，滿足以下條件：

1. XY ^我 z爲以L對於每個i> = 0
2. | Y |> = 0
3. p> = | xy |

表明某種語言L不規則的正確方法是假定L規則並嘗試達成矛盾。

如果您試圖假設您的語言不規則，您應該首先搜索代表該語言不規則性的字符串類型。 讓我們試試^p b ⁿ n> = 0。

我們可以對這個字符串做一些假設：因爲| xy | < = p我們知道y只由a組成。此時，您可以根據需要抽多次，但xy ⁱ z是每個i> = 0時您的語言的成員。

以類似的方式，如果您選擇ⁿ b ^p n> = 0，您將不會達成矛盾。

L = {a ⁿ b ⁿ | n> = 0}是不規則的，但是你對p和q沒有約束（我的意思是，不需要計算a和b的出現次數）。

但是，語言是規則的，當且僅當它可以用正則表達式表示。在這種情況下，你可以這樣做：a * b *。所以你可以得出結論，這種語言是經常性的。

編輯： 對於p < = q語言不規則，但您正在考慮任何p和q。