math - 是否存在 {0^i1^j 的上下文无关文法使得 1 <= i <= j <=2i }？

Question

我遇到了两个完全不同的答案。

一个人说：

是的，确实存在 的上下文无关文法，以下文法确保存在的 1 可以有一半或更少的 0：{0i1j | 1≤i≤j≤2i}

S -> 0S11 | 0S1 |  01

---

另一个：不，反证法：

情况1：

假设您将 i 0 压入堆栈。

弹出 j 1s。

您无法确定 j<=2i。

案例二：

假设您将 2i 0 压入堆栈。

弹出 j 1s。

您无法确定 j>=i。

压入堆栈的任何其他不等于 i 或 2i 的值都是相对于这两个值中的任何一个的值，因此适用相同的推理。

---

是否正确？非常感谢！

Answer 1

由于存在语法并且您可以非常清楚地检查它是否与整个语言匹配，因此该语言必须是上下文无关的。所以反证法是错误的。但为什么？

证明假设机器必须是确定性的。但是你需要一个不确定的下推自动机来识别一些上下文无关的语法。因此，所有第二个证明证明（如果它是正确的）是该语言不是确定性上下文无关语言，但它并没有表明它不是上下文无关语言。

事实上，如果你让机器是不确定的，那么基本上你压入 i 个 0，然后对于堆栈上的每个 0，非确定性地弹出 1 或 2 个 1。如果字符串是该语言，则其中一项计算将接受。