这个上下文无关语法是否有歧义？

Question

我想知道下面的上下文无关文法是否有歧义。

S -> 0S |一个 | 0
一个 -> 1A | 1

我相当确信它是明确的，但有人告诉我它是模棱两可的。有人可以帮我吗？

谢谢。

Answer 1

语法没有歧义。

首先，我们可以证明文法的语言是0*(0 + 1*1)；也就是说，任意数量的 0 的语言，后跟单个 0 或任何非空的 1 字符串。请注意，任何此类字符串都可以通过以下方式获得：

如果字符串 0^k k > 0: S -> 0S (k-1) 次，那么 S -> 0 一次。
如果字符串是 0^i 1^k，i >= 0 和 k > 0，则：S -> 0S i 次，然后是 S -> A 一次，然后是 A -> 1A (k-1) 次和 A -> 1 一次。

另请注意，语法只能生成以下字符串：

所有 0 出现在任何 1 之前
任何没有 1 的字符串必须至少有一个 0.

现在的问题是对于任何生成的字符串是否存在不同的解析树。我们可以证明没有很简单的用例：

如果字符串是 0^k 且 k > 0：只有两个产生式引入 0s：S -> S0 和 S -> 0。为了获得 0 的 k 个实例，我们被迫首先使用生产 S -> S0 (k-1) 次，然后使用 S -> 0 否则我们将在获得字符串之前终止中间形式长度 k.
如果字符串是 0^i 1^k 且 i >= 0 且 k > 0：我们被迫使用生产 S -> 0 i 次来获得 0^i 因为没有其他产生式序列会给我们一个以 i 0s 开头的未终止的中间形式。然后，我们被迫使用 S -> A，因为任何其他选择都会添加额外的 0。接下来，我们被迫使用 A -> 1A 的次数等于 (k - 1)，否则我们会在到达所需的 1 的 k 实例之前终止字符串，因为唯一剩下的产品是 A -> 1 ，它消除了最后一个非终结符。最后，我们被迫使用A -> 1来终止字符串。

因此，在这两种情况下，我们对作品的选择都取决于 0 和 1 的数量；我们从来没有随意选择使用哪种产品。事实上，由于所有中间形式都只包含一个非终结符，我们甚至从来没有选择使用产生式的顺序：不仅每个字符串都有一个解析树，而且文法可以派生字符串的顺序也只有一种。存在明确的语法，即使是这种强条件也不成立；考虑

S -> AB
A -> a
B -> b

即使字符串 ab:

有两个推导，这也是明确的

S -> AB -> aB -> ab
S -> AB -> Ab -> ab

在这两种情况下，树是相同的：

  A - a
 /
S
 \
  B - b

这个上下文无关语法是否有歧义？

Is this context free grammar ambiguous?

context-free-grammar

ambiguous-grammar