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

Question

Let L(G) be the language generated by a context free grammar G. Is the following decision problem decidable ?
Whether L(G) is deterministic context free language ?

从这个link我明白了为什么上面的问题是不可判定的，但是我有一个疑问
我们知道 CFL 和 PDA 是等价的 (reference)，即对于每个 CFL，G，都有一个 PDA M，使得 L(G) = L(M)，反之亦然。
如果自由语言可以被 DPDA 接受，则它是确定性的。
确定性 PDA 是一种基于当前输入从任何状态至多有一种可能的转换。

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

Answer 1

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

A context free language is deterministic if it can be accepted by a DPDA.

和

we can create a PDA for every CFL

和

[we can] distinguish between PDA's being deterministic or not

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