L（G）是由上下文无关文法G生成的语言。以下判定问题可判定吗？ L（G）是否为确定性上下文无关语言？
我理解了为什么从[link]无法确定上述问题，但我对此表示怀疑。我们知道CFL和PDA等效（reference），即，对于每个CFL，G，都有一个PDA M，使得L（G）= L（M），反之亦然。上下文无关的语言是否可以被DPDA接受是确定性的。确定性PDA是一种基于当前输入从任何状态最多存在一种可能转换的PDA。因为我们可以为每个CFL创建一个PDA并区分PDA是否具有确定性，所以可以说L（G）是否是确定性上下文无关语言的问题是可以确定的吗？还是我错过了什么？
您丢失了一些东西。你说：
上下文无关语言是确定性的，如果它可以被DPDA接受。
和
我们可以为每个CFL创建一个PDA
和
[[我们可以]区分PDA是否具有确定性
问题是，即使语言是确定性的，您为CFL获得的PDA也可能是不确定性的。虽然每个确定性CFL都有接受它的DPDA是正确的，但并不是每个DPDA仅接受每个确定性CFL都是不正确的。的确，每一个确定性CFL都被许多不确定性PDA所接受……不难看出，通过添加不导致接受任何东西的新状态和分支，可以将任何DPDA转换为等效的不确定性PDA。