證明不規範

Question

假設我有一個語言L = {wxwR}其中wR是w的倒數，w和x的最小長度爲1，w可以由0或1組成，而x只能由1組成。

如何證明此語言不正規？除了使用抽象引理之外還有別的方法嗎？如果使用抽象引理，我仍然計算出我應該爲字符串s = xyz選擇什麼x，y和z，如果給我任何提示，我會很感激。

謝謝！

Answer 1

你應該再看看如何使用抽象引理。您必須選擇一個字符串s，以便對於每個分區x,y,z，泵浦引理條件之一被違反。

因此，讓n是「抽 - 引理數」。選擇s= 0^n 1 0^n。 從1）你知道|xy| <= n。從2）你知道|y|>=1。因此y只包含0s。

以下3）uv^2w也必須在L，但0s的第一個塊比第二塊長。這意味着3）被違反，因此L是不規則的。