對於普通語言a * b *，是否有一個非正規的超集？

Question

語言A = a*b*絕對是一種常用語言。 但我想知道是否有超集是非常規語言？並且超集必須使用相同的字母表{a，b}

Answer 1

是的，有。以B = b ⁿ ab ⁿ（其中n> 0），即以b開始並且在中間包含單個a的迴文的語言。這種語言是非常規的，因爲pumping lemma不適用於它。它也與A完全脫節，因爲B中的每個單詞都包含ba子字符串，而A中沒有任何單詞。

因此A和B的聯合是A的非正則超集。

也很容易證明並非所有的常規語言都可以這樣擴展，因爲例如給定字母表上的每個可能的單詞的語言按照定義是規則的。由於沒有辦法在相同的字母表上制定這種語言的非平凡超集，因此給定字母表上的「Kleene星」語言的所有超集也將是規則的。

更一般地，任何語言，其補充語言（C _一個 =Σ^* \ A）是有限的不會有非正規的超集，因爲C _一個及其所有子集是通過定義常規（有限的語言總是有規律的），因此它們中的任何一個與A的聯合也是常規的（兩種常規語言的聯合是規則的）。