1

我想知道以下上下文无关语法是否模棱两可。

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

我相当确信它是明确的，但我被告知它是模糊的。有人可以帮我吗？

谢谢你。

4

1 回答 1

0

语法是明确的。

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

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

另请注意，语法只能生成此类字符串：

  1. 所有0s 都在任何1s之前
  2. 任何没有1s 的字符串必须至少有一个0。

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

  1. 如果字符串是0^kk > 0: 只有两个产生式引入0s:S -> S0和S -> 0. 要获得 k 个实例，0我们必须首先使用产生S -> S0式 (k-1) 次，然后再使用S -> 0，否则我们将在获得长度为 k 的字符串之前终止中间形式。

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

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

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

即使字符串有两个派生，这也是明确的ab：

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

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

  A - a
 /
S
 \
  B - b
于 2020-07-15T12:57:31.367 回答