1

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を汲み上げると失敗するようです

4

2 に答える 2

3

条件を満たす v,x,y の任意の選択を許可する必要があることを覚えておいてください。特に、いつでも選択できます

u=a^{n-1}, v=a, x=empty, y=b, z=b^{n-1}.

次に、 vxy は必要に応じて短くなりますが、ポンピングすると

uv^kxy^kz = a^{n-1} a^k empty b^k b^{n-1} = a^{n+k-1} b^{n+k-1},

それはまだ言語にあります。

于 2013-10-15T00:33:06.417 に答える