computation-theory - 上下文无关语言是否是确定性上下文无关语言

Question

令 L(G) 是由上下文无关文法 G 生成的语言。以下决策问题是可判定的吗？
L(G) 是否是确定性上下文无关语言？

我从这个链接中理解了为什么上述问题无法确定，但我有一个疑问。
我们知道 CFL 和 PDA 是等价的（参考），即对于每个 CFL G，都有一个 PDA M 使得 L(G) = L(M)，反之亦然。
如果 DPDA 可以接受上下文无关语言，则它是确定性的。
确定性 PDA 是一种基于当前输入的任何状态至多有一次可能的转换。

既然我们可以为每个 CFL 创建一个 PDA 并区分 PDA 是否是确定性的，我们是否可以说 L(G) 是否是确定性上下文无关语言的问题是可判定的？还是我错过了什么？

Answer 1

你错过了一些东西。你说：

如果 DPDA 可以接受上下文无关语言，则它是确定性的。

和

我们可以为每个 CFL 创建一个 PDA

和

[我们可以]区分 PDA 是否具有确定性

问题是即使语言是确定性的，你为 CFL 获得的 PDA 也可能是不确定的。虽然确实每个确定性 CFL 都有一个接受它的 DPDA，但并不是每个确定性 CFL 都只被 DPDA 接受。事实上，每个确定性 CFL 都被许多非确定性 PDA 接受……不难看出，任何 DPDA 都可以通过添加不会导致接受任何东西的新状态和分支转换为等效的非确定性 PDA。