context-free-grammar - Pushdown Automata (PDA) を使用して次の言語を定義できないのはなぜですか?

Question

{0 ⁱ 1 ^j 2 ^k | 0 <= i <= j <= k }

この言語用の PDA を設計することは可能ですか?

答えはノーだと思います。少なくとも文脈自由文法を使用してのみ定義できます。

しかし、その理由はわかりません。これについては、議論と説明が必要です。

Answer 1

答えはノーだ。実際、この言語には CFG も NPDA もありません。証明は、文脈自由言語のポンピング補題を使用して確立できます。