1

こんな簡単な質問をここに投稿しているような気がしますが、このサイトの知識ベースはすごいです。わかってくれてありがとう。

正規表現の最小ポンピング長(正規言語のポンピング補題に関する)を見つけることに関する質問について:

正規表現R=1011(アルファベット{0,1}上)

この文字列ε(空の文字列)と1011に一致するのはそれだけではありませんか?

編集-私はあまりにも多くのクリーネ閉包を見つめてきました。空の文字列εはこの言語ではありません。

正規言語のプロパティは、言語が有限オートマトン(または正規表現)で表現できる場合、それは正規であり、確かにこれは両方で表現できると述べています。(そして、質問は明らかに私にその言語が正規言語であると信じさせる)

しかし一方で、(非公式に)ポンピング補題は、すべての正規言語にはポンピング長があり、少なくともこの長さのすべての文字列をxyzに分割して、結果に影響を与えることなくyを繰り返すことができると述べています。εは定義上ポンピングできず、1011はポンピングできません(これは問題ではないと思います)。他の文字列が一致しないため、yのインスタンスを削除または追加すると、文字列が受け入れられなくなります/一致しました。

私のロジックのエラーはどこにありますか?

2番目の編集-任意のp>4の答えは、x、y、またはzをϕ(ヌルセット)に設定することで言語をポンピングできます。これを何かと連結すると、ヌルセットになりますか?

4

1 に答える 1

1

ポンピング補題は、有限言語にはあまり役立ちません。すべてのfiniate言語は通常です。たとえば、あなたの場合、「ポンピング長さ」を4に設定できます。空の意味では、その長さを超えるすべての単語をポンピングできます。:)

于 2010-09-15T16:33:36.877 に答える