通常の言語であるa * b *の場合、その正規のスーパーセットは非正規ですか？

Question

言語A = a*b*は絶対的な正規表現です。 しかし、私はそれのスーパーセットが不規則な言語であるかどうか疑問に思っていますか？また、スーパーセットは同じアルファベットを使用する必要があります。{a、b}

Answer 1

はい、あります。 B = b ⁿ ab ⁿ（n> 0）、すなわち、bで始まり、真ん中にaという文字が含まれている、パリンドロームの言語です。この言語はpumping lemmaが適用されないため、非正規です。 Bのすべての語句には部分文字列が含まれており、Aの語句は含まれていないため、Aと完全に矛盾しています。

AとBの和集合はAの非正規スーパーセットです。

また、すべての通常の言語をこのように拡張できるわけではないことを証明することも容易です。同じアルファベットに対してこの言語の重要ではないスーパーセットを定式化する方法がないため、与えられたアルファベットに対する "Kleene star"言語のすべてのスーパーセットも規則正しくなります。 C とそのすべてのサブセットが定義によるものであるので、

より一般的には、その補完言語（C =Σ^* \ A）が有限である任意の言語のAは、非正規スーパーセットを持っていません。通常（有限言語は常に規則的）であるため、Aとの和集合も（2つの正規言語の和集合は規則的です）です。