是否存在本质上模糊且确定性的上下文无关语言？

Question

当且仅当它可以被确定性下推自动机接受时，我们称上下文无关语言为确定性语言，否则为非确定性语言。

当且仅当生成该语言的所有上下文无关语法都是二义性的时，我们称上下文无关语言本质上是二义性的，否则是明确的。

确定性、明确语言的一个例子是：$$ {a^{n} b^{n} in {a，b }^{*} | n ge 0 } $$一个非确定性，明确语言的示例是语言：$$ {w in {a，b }^{*} | w = w^{r} } $$

从 维基百科, ，本质上不明确的上下文无关语言的一个例子是以下上下文无关语言的并集，它也必须是上下文无关的：$$ l = {a^{n} b^{m} c^{m} d^{n} in {a，b，c，d }^{*} | n，m ge 0 } cup {a^{n} b^{n} c^{m} d^{m} {m} in in {a，b，c，c，d }^{*} {*} | n，m ge 0 } $$

现在回答问题：

1. 是否知道是否存在一种确定性的、本质上模糊的上下文无关语言？如果是这样，有一个（简单的）例子吗？
2. 是否知道是否存在一种非确定性的、本质上模糊的上下文无关语言？如果是这样，有一个（简单的）例子吗？

显然，由于存在一种本质上模糊的上下文无关语言（$L$ 是一个例子），如果知道 $L$ 是确定性的还是非确定性的，那么这些问题之一的答案很容易。我还假设，如果存在确定性的，那么也必然存在非确定性的……但我之前就很惊讶过。感谢参考，如果这是一个众所周知的、值得庆祝的结果，请提前道歉（在这种情况下，我完全不知道）。

Answer 1

如果语言$ l $是确定性的，那么它被某些确定性的按下自动机所接受，这又意味着有一些LR（1）语法描述语言，并且每个LR（1）语法都是明确的，这意味着这意味着这意味着$ l $不能天生模棱两可。诺斯在他的论文中证明了这一点，他介绍了LR（1）（1）（关于从左到右的语言翻译).

当且仅当某些非确定自动机识别时，就可以通过某些无上下文的语法来描述一种语言。作为这种特殊情况，某些非确定性自动机可以解析固有的无上下文语法。

最后，任何确定性的推动自动机也是无确定的（几乎所有可能是无确定性的情况，对于非确定性的合理定义）。

Answer 2

阅读维基百科和答案以及您对它的评论，重新（Q2）明确指出，所有本质上不明确的 CFL 在 std defn 下都必须是不确定的（包括您自己的示例！）。遇到了这个裁判

• 一些本质上不明确的上下文无关语言 / Shamir 和可能的其他人在文献中进行了研究。