automata - PDA と CFL のポンピング補題

Question

私は完全に立ち往生しているポンピングレンマの質問があります...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

それはCFLですか？

これらの条件をすべて記憶するには、1 つのスタックだけでは十分ではないため、CFL ではないと考えています。na (w) < nb (w) または na (w)< nc (w),nb (w) < nc (w) であることを思い出すことができますが、na (w) < nb (w) < nc (w) ではありません。さらに、言語が a^pb^2pc^3p の場合と、|vy| の場合よりも p 回 L は CF ではありませんが、p 回ポンプアップすることは可能ですか?

または解決策のアイデアはありますか？

Answer 1

ポンピング補題では、 L内のすべての文字列がポンピング後にLに留まる必要があることに注意してください。したがって、 L内の特定の形式の文字列についても矛盾が発生するだけで十分です。

a ^p b ^2p c ^3pは良い例ですが、より短いa ^p b ^p+1 c ^p+2を試すことをお勧めします。

理由は Wikipedia の記事Pumping lemma:Usageとほぼ同じです。同じ 5 つのケースがあり、それぞれに矛盾が生じるのは非常に簡単です。