regular-language - 言語 L のすべての部分集合が規則的である場合、L は規則的ですか?

Question

上記の定理の逆が正しくないことはわかっています。つまり、L が正則である場合、L のすべての部分集合が正則である必要はありません。

Answer 1

だけでなく

言語 L のすべてのサブセットが正則である場合、L は正則です

だけでなく、

言語 L のすべての適切な部分集合が正則である場合、L は有限です。

証拠：

これは次のステートメントと同等です。

言語Lが無限である場合、通常の言語ではないサブセットが含まれます。

正規言語のポンピング補題は、「その言語lの単語wが よりも長い場合、空ではない単語lが 3 つ存在し、すべてがその言語に存在するような長さが存在する」と述べています。x,y,zyxyz == wxy^nz

言語が無限かつ規則的である場合、任意の長さよりも長い単語が含まれます。したがって、この言語には必ず 3 つの単語が存在x,y,zし、everyxy^nzが含まれます。

さて、 のすべての適切な部分集合{xy^nz; n in N}は の適切な部分集合ですL。現在、規則的ではない適切なサブセットが確実に存在しますxy^nz*。したがって、すべての正規の無限言語には、正規ではない適切なサブセットがあります。

言語が無限で規則的でない場合は、適切な無限サブセットのいずれかを検討してください。サブセットが規則的でない場合、その言語は反例ではありません。サブセットが規則的である場合は、前の段落を使用して、規則的ではない適切なサブセットを見つけます。固有部分集合であることは推移的であるため、この部分集合は元の言語の固有部分集合であり、その言語は反例ではありません。

したがって、すべての無限言語には、規則的ではない適切なサブセットがあります。

したがって、言語のすべての適切な部分集合が規則的である場合、その言語は有限 (したがって規則的) です。

QED

*たとえば、集合{xy^{n^2}z; n in N}は の適切な部分集合であり、 Myhill-Nerode の定理{xy^nz; n in N}で示されるように規則的ではありません。