問題タブ [pumping-lemma]

ポンピング補題を使用して、言語が文脈自由かどうかを証明するテストが近づいています。練習問題を解こうとしているのですが、うまくいきません...

練習問題は、a)～j)について、次の言語が文脈自由かどうかを証明せよ。文脈自由であれば、それを生成する文脈自由文法を与えてください。

最初の 2 つは次のとおりです。

誰かがこれらの最初の 2 つを解決し、その方法を詳しく説明してくれれば、残り (c から j) を自分で理解できると確信しています。

特定の言語が非正規であることを証明するのに苦労しています。言語は次のように定義されます。

L _a = { wz : w,z ∈ {0,1}* および |w| > |z|}

これにアプローチする方法がわかりません。どの文字列を選択しても、常に w と z がターゲットを移動しているという問題に遭遇します。ポンピングまたは矛盾することができない文字列を作成できませんでした。これの正しい方向について何か考えはありますか？

文字列wをそのままにすると、規則により、文字列のみで構成されるa^mb^mことがわかります。ya|xy| <= m

を設定するとi=0、右側よりも左側の のww^R方が少なくなります。aしたがって、この言語が規則的でないことが証明されます。

しかし、私の教科書 (形式言語とオートマトンの紹介pg. 118 by Linz) は、もし私が を選択w = a^2mして任せたらy = aa、私は失敗するだろうと言っています。

しかし、どうしてですか？

私の考えでは、 ,が何xであれ、最初のものは 2 番目のものよりも数が少ないか多いかによって異なります。yza^2maia^2m

これは奇妙ですが、レンマをポンピングすることで、

L正規言語にしましょう。nsuch that のすべての文字列に対してw、Lthatにもある suchに|w| >= n割り込むことができるような定数が存在します。wxyzxy*zL

この補題は、すべての正規言語を主張するため、強力です。しかし、通常の言語の場合はどうなるL = aでしょうか? その中には 1 つの単語 ( a) しかありません。この場合、ポンピング補題はどのように機能しますか?

ポンピング補題を使用して、次の言語が正則でないことを証明しようとしています。

L = {a ^k b ^3l a ^l | k ≥ 1 , l ≥ 0}

w = ab ^3p a ^pを選択し、次に |w|を選択することにしました。= 4p+1 ≥ p

任意のヒント？

ありがとうございました！