こんな簡単な質問をここに投稿しているような気がしますが、このサイトの知識ベースはすごいです。わかってくれてありがとう。
正規表現の最小ポンピング長(正規言語のポンピング補題に関する)を見つけることに関する質問について:
正規表現R=1011(アルファベット{0,1}上)
この文字列ε(空の文字列)と1011に一致するのはそれだけではありませんか?
編集-私はあまりにも多くのクリーネ閉包を見つめてきました。空の文字列εはこの言語ではありません。
正規言語のプロパティは、言語が有限オートマトン(または正規表現)で表現できる場合、それは正規であり、確かにこれは両方で表現できると述べています。(そして、質問は明らかに私にその言語が正規言語であると信じさせる)
しかし一方で、(非公式に)ポンピング補題は、すべての正規言語にはポンピング長があり、少なくともこの長さのすべての文字列をxyzに分割して、結果に影響を与えることなくyを繰り返すことができると述べています。εは定義上ポンピングできず、1011はポンピングできません(これは問題ではないと思います)。他の文字列が一致しないため、yのインスタンスを削除または追加すると、文字列が受け入れられなくなります/一致しました。
私のロジックのエラーはどこにありますか?
2番目の編集-任意のp>4の答えは、x、y、またはzをϕ(ヌルセット)に設定することで言語をポンピングできます。これを何かと連結すると、ヌルセットになりますか?