context-free-grammar - 为什么无法使用下推自动机 (PDA) 定义以下语言？

Question

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

是否可以为这种语言设计 PDA？

我认为答案是否定的，它只能使用至少一个上下文无关语法来定义。

但是，我不知道为什么。我需要对此进行一些讨论和解释。

Answer 1

答案是不。实际上，这种语言既没有 CFG 也没有 NPDA。可以使用上下文无关语言的泵引理来建立证明。