Ppumping Lemma について書いています。私は言語 L = { a^nb^n| を知っています。n ≥ 0 } は文脈自由です。しかし、この言語がポンピング補題の条件をどのように満たしているのかわかりません (文脈自由言語の場合) ?

文字列 s = a^pb^p, |s| を選択すると、> p , |vxy| < p と |vy| > 0。

私たちがそれをポンピングするとき（ポンプアップまたはポンプダウンするとき）、それは言語外になるか、私が欠けているものがあるようです.

どんな説明でも役に立ちます。

編集:ポンピング補題を a^nb^n に適用していますが、すべてのケースで言語にとどまりません。では、なぜコンテキストフリーなのでしょうか?

この言語がポンピング補題の条件を満たすことを確認したかっただけです。しかし、s = uv^2xy^2zを汲み上げると失敗するようです

この式は決定論的有限自動化によって受け入れられますが、この式にポンピング レンマを適用すると、ポンピング レンマが失敗します。また、この式は有限の状態を持ちますが、停止して継続的に実行されず、エッジは自己ループを b/w で作成し続けます。 i が大きくなる傾向があり、無限大になる傾向がある場合、それは停止するはずがないと述べています。したがって、この式では DFA を描くことができますが、レンマと TM のポンピングは失敗します。では、これが通常の文法かどうか教えてください。

YouTube で Coderisland の有限状態マシン、DFA、および NFA に関する講義を見てきました。あるディスカッションで、彼はポンピング補題を使用して言語が規則的でないことを示す方法について話しています。レンマを適用する方法がよくわからないので、正しく行っているかどうかを理解したい. 私が次のようなものを持っていたら：

w = {a ⁿ b ^k , n =/= k}

私は次のように言うことができるという点で正しいですか：

h = {a ⁿ b ^{n + r} , r > 0} はwのサブセットであるため、 hが正則でないことを補題によって示すと、hはwのサブセットであるため、 wは正則であってはなりません。

これを示す方法は次のとおりです。

1. h = xyz
2. |xy| <= n
3. x = ^n-r
4. y = a ^r
5. z = b ^{n + r}
6. xyz = a ^n-r a ^r b ^{n + r}
7. xy ² z = a ^n-r a ^2r b ^{n + r} = a ^{n + r} b ^{n + r}

したがって、a ^{n + r} b ^{n + r}は {a ⁿ b ^{n + r} , r > 0} の形式ではないため、hは規則的ではありません。また、 hは規則的ではないため、 hは次の要素であるため、 wは規則的であってはなりません。w。

私はそれを正しく適用しましたか？^{{a n} b ⁿ }のような簡単な言語に適用する方法は理解できます。なぜなら、この補題をこの言語に直接適用できるからです。 、それに補題を適用します。

私がそれを正しく適用していない場合、私の言語が規則的 (または規則的) ではないこと、別のレンマを使用すること、またはクロージャー プロパティを使用することを示す方法はありますか?

これは本当に素晴らしいトピックです。ポンピングの補題を完全には理解していなくても、さらに詳しく調べることに興奮しています!

私は、ポンピング補題が確実に規則的な言語にどのように適用されるかを示そうとしています。1 が偶数の {0, 1} 以上の言語があります。この言語は、2 つの状態を持つ DFA で表すことができます。

ここでのポンピング長は 2 ですね。ポンピング補題は、「もし s が長さが少なくとも p の A 内の任意の文字列である場合」、3 PL 条件が真になるように xyz に分割できると述べています。たとえば、文字列 '000110' を選択し、それが |xy| となるように xyz に分割できることを示したいとします。<= p (および |y| > 0、および x(y^i)z は L 内)。

この場合、y は '11' でなければならないので、繰り返しても偶数になります... これは x = '000' になりますよね? これにより、|xy| が作成されます。= 5、これは p よりも大きい。

|xy| になるように指定された文字列を分割する他の方法は見当たりません。< p. ここで何が欠けていますか？どうもありがとう。

1. ごとi ≥ 0に、uv^ixy^iz ∈ A,
2. |vy| > 0、 と
3. |vxy| ≤ p.

2 の場合、uvxyz をポンプ ダウンすると uxz が得られますが、2 に違反します。= 0。

私はこれを多くの場所で例として見ましたが、どこで間違って理解しましたか?

L={a ⁿ b ^m c ^o | n < m < o, n natural}
ポンピング補題を使用して、次のように選択しました: z = uvwxy = a ⁿ b ⁿ⁺¹ c ⁿ⁺²
|uv|<=n and |v|>0
=> uv ² wx ² y
If vwx が a および/または b であることは問題ありません。c よりも a および/または b の方が多いでしょう。しかし、vwx に c のみが含まれている場合、それは L の要素になります。
私が理解している限り、すべての新しい単語は要素ではない必要があります。 CFL ではないことを示す L の。どうすればいいですか？

決勝に向けて教科書からいくつかの問題を解いていましたが、よくわからない問題に出くわしました。基本的には

L = {w | w には 1 よりも多くの 0 が含まれています}

そして、通常の言語のポンピング補題が役立つはずだとヒントとして述べています。

ポンピングによってパターンを破ることができるため、最初に 0 の後に 1 が続く、または回文などのパターンがある場合、言語が非正規であることを証明するのは簡単ですが、ここでの唯一の要件は、0 と 1 を含むことができる単語が任意の順序で、より多くの 0 があります。

私はいくつかのケースを考えようとしていました.y = 0の場合、1よりも0が多くなるまでyをポンピングできます。しかし、ポンピング補題が偽であることを証明するには、考えられるすべてのケースを考慮する必要があり、y は |xy| である限り任意の文字列になり得るようです。< p (p はポンピング長)。y には、0 と 1、または 1 のみを含めることができます。ここで明らかな何かが欠けていますか？ありがとうございます。

偶数のゼロを含む文字列が a) 文脈自由 b) 通常かどうかを調べる

^{a) CFL のポンピング補題を使用すると、e(0 n} )e(0 ⁿ )eと表すことができます。だから、それはCFLです。

(00)*b)正規表現のように表すことができます。だから、正規語だと思います。しかし、正規言語のポンピング補題を使用して同じことを証明することはできません

どんな助けでも大歓迎です。ありがとう！！