CFLポンピング補題の正しい適用
私はその言語を示すことについてこの質問に出くわしました $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$文脈自由ですが、ピーター・リンツの本では直線的ではありません。これは、線形言語の個別のポンピング補題（リンツの本に記載されている）によって簡単に実行できますが、私の質問は異なります。
明らかにこれはCFLであり、プッシュダウンオートマトンを構築できます。しかし、CFLにポンピング補題を適用すると、その言語に属していない文字列をポンピングできることがわかります。つまり、その言語はCFLではありません。明らかに私は何か間違ったことをしている。
リンツで与えられた「ゲームのような」フォーマットで行く、あなたが選ぶと言う $w = a^mb^mc^{2m}$、 $|w| \ge m$。敵はいくつかの分解を選択できます$w = uvxyz$、次のようになります-：
- $v = a^k, y = a^l$：場合 $|vxy|$ 内に含まれています $a$文字列の。ポンプ$i = 0$、 その後 $w_0 = a^{m – (k + l)}b^mc^{2m}$ 平等がもはや成り立たないので、言語であることができません。
- $v = a^k, y = b^l$：場合 $v$ の中に $a$ セクション、 $x$ にまたがる $a$'砂 $b$'砂 $y$ の中に $b$セクション。繰り返しますが、ポンプ$i = 0$。 $w_0 = a^{m – k}b^{m – l}c^{2m}$ その言語にすることはできません。
このようなケースは他にもあります。CFL PLの適用でどこが間違っているのですか？
回答
CFLのポンピング補題は、 $L$ はCFLであり、定数が存在します $N \ge 1$ すべての人のために $\omega \in L$ と $\lvert \omega \rvert \ge N$ 分裂があります $\sigma = u v w x y$ と $\lvert v w x \rvert \le N$ そして $v x \ne \varepsilon$ そのような $u v^k w x^k y \in L$ すべてのために $k \ge 0$。
（正規言語のポンピング補題も同様です。以下の説明は、わずかな変更を加えて適用されます）。
あなたは矛盾によってそれを証明したい $L$CFLではありません。だからあなたは仮定します$L$はCFLであり、見出語と矛盾します。これは、詳細に次のことを意味します。
- なので $L$はCFLであり、見出語を満たします。特に、定数があります$N$ そのような...
- 補題がすべての長い文字列を述べているように$L$ 分割できるので、扱いやすいものを自由に選ぶことができます。
- 補題は、いくつかの分割があると述べています$\omega$そのような....すべてのために $k \ge 0$...; 見出語と矛盾するには、除算が機能しないことを証明する必要があります。実際には、あなたはあなたの与えられた除算を取ります$\omega$（任意の部門）そしてそれのためにいくつかを選ぶ$k$その言語で文字列を与えないので。これをケースに分割する必要があるかもしれません。
言語に属していない文字列、またはより短い文字列はどうなりますか $N$、完全に無関係です。一部の文字列をポンピングできる可能性があります。$k$すべての文字列で機能します...重要なのは1つの文字列でそれです$\omega$（あなたが選んだもの）除算は1つの値で機能しません$k$（繰り返しますが、あなたが選んだもの）。見出語が主張するように、それはすべての十分な長さの文字列に対して機能し、すべてに対していくつかの除算があります $k$、1つの反例で十分です。無限の例は何も証明しません。