問題タブ [pumping-lemma]

私はこの質問を見て、ポンピング補題が何であるかについて興味がありました（ウィキペディアはあまり役に立ちませんでした）。

基本的に、言語が特定のクラスに属するためには真実でなければならない理論的証明であることは理解していますが、それ以上はよくわかりません。

非数学者/計算科学博士が理解できる方法で、かなり細かいレベルでそれを説明しようとする人はいますか?

私の質問は：

L = {x in {a,b}* | x は a と b の数が等しい}

文法を作成できるので、これが文脈自由言語であることはわかっています (e はイプシロン):

通常の言語と交差する文脈自由言語は文脈自由であるという事実を使用して、それが文脈自由であることを証明することもできます。

これは文脈自由言語であるため、CFL のポンピング レンマによれば、ポンピング長 p よりも長い任意の文字列をポンピングできるはずです。ただし、文字列 s = a^pb^pa^pb^p を選択した場合、この文字列はポンピングできないため、言語は文脈自由であってはなりません。

どこが間違っていますか？

ほとんどの UNIX 正規表現には、通常の**, +,?*演算子の他に、最後の括弧内のものと一致するバックスラッシュ演算子がある\1,\2,...ため、たとえば*L=(a*)b\1*(非正規の) language と一致します*a^n b a^n*。

一方で、スタックオートマトンでも認識できない(a*)b\1b\1言語に合わせて作成できるため、これはかなり強力に思えます。*a^n b a^n b a^n*一方で、*a^n b^n*このように表現することはできないと確信しています。

2 つの質問があります。

1. この言語ファミリーに関する文献はありますか (UNIX-y レギュラー)。特に、これらのポンピング補題のバージョンはありますか?
2. *a^n b^n*このように表現できないことを誰かが証明または反証できますか?

私は次の問題を抱えています：

言語L1={a ^ n * b ^ n：n>=0}およびL2={b ^ n * a ^ n：n> = 0}は文脈自由言語であるため、L1L2の下で閉じられ、L = {a ^ n * b ^ 2n A ^ n：n> = 0}は、クロージャプロパティによって生成されるため、コンテキストフリーである必要があります。

これが本当かどうかを証明しなければなりません。それで私はL言語をチェックしました、そしてそれが文脈自由であるとは思わない、そして私はまたL2がちょうどL1が逆になっているのを見ました。

L1、L2が決定論的であるかどうかを確認する必要がありますか？

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

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

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

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

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

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

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

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

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

A が文脈自由でないことを示す必要があります。これには Pumping Lemma を使用する必要があると思いますが、どうすればよいでしょうか?

私は{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 、m文字列が

次に、文字列が空にならない(z =) uvwxyように分割され 、「」を選択すると混乱します。私が選ぶとしたら、私が持っているとしましょう： そして、私には言語にあるvwxを選ぶことができるように見えるので、そこからどこへ行くべきか完全にはわかりません。vx#(vwx)<=mii=1uv^1wx^1y

助言がありますか？

正規言語のポンピング補題について 1 つ小さな質問があります。言語 L に属する特定の文字列をポンピングできない場合、その言語は不規則であることを示すのに十分でしょうか? たとえば、a^nb^n (ab、aabb、aaabbb ...) という形式の言語 L1 を選択し、文字列 aabb をポンピングできず、依然として L1 の一部であることを示した場合、それはL1が不規則であるとすぐに結論付けるのは正しいですか?

乾杯。

私はオートマトン理論の授業を受けており、今はポンピング補題を学んでいます。「L もその補集合も無限の正規部分集合を持たないように言語 L を設計しますか?」という演習問題があります。しかし、私は質問を理解していません。無限正部分集合とは? この要件を満たす言語を見つけるにはどうすればよいですか?

誰でもこの質問に光を当てることができますか?

ありがとう！

私の試験では、すべての反復補題条件を書くことになっていた。それはまさに私がしたことです：

友人からエラーがあると言われましたが、見つかりません...誰か助けてもらえますか？エラーとその理由は何ですか？