非确定性下推自动机能识别任何上下文无关文法吗？

Question

非确定性下推自动机能识别任何上下文无关文法吗？我真的不确定这一点，我认为上下文无关的文法可以

Answer 1

下推自动机不识别上下文无关的语法，而是识别上下文无关的语言。然而，任何上下文无关文法的语言都可以被一些不确定的下推自动机识别。这可能就是您想问的问题。

要了解这一点，可以想象一个不确定的下推自动机，其功能如下。它首先将语法的开始符号压入堆栈。然后，它弹出最上面的符号，并通过选择一些可用的产生式规则来非确定性地替换非终端符号。如果它弹出一个终止符号，它将从输入流中使用该符号。如果堆栈为空且输入耗尽，它将接受。

刚才描述的非确定性PDA根据语言的语法为任何输入字符串推送该字符串的派生(如果有的话)。这应该表明非确定性PDA可以接受由CFG生成的任何语言。