context-free-grammar - 为什么这是一个模棱两可的语法？

Question

我有以下练习：

说明这个语法有歧义：

S-> bA | aB
A-> a | aS | bAA
B-> b | bS | aBB

根据我读过的语法的理论，如果：

1) A string W ∈ L(G), generates two differents trees 
2) Makes 2 or more left/right derivations

所以，我无法确定一个确认的字符串1)，所以我试过了2)。据我所知，只需要2个反身推导就可以让我的语法模棱两可？

例如：

w=bbaa S->bA->bbAA->bbaA->bbaa 
                ^^--here i made two reflexive/recursive derivation

正如我所描述的那样，这是正确的还是需要更详细的信息？

PD：有没有什么技巧可以让生成两个三的字符串？

score 1 · Accepted Answer

不，这不是模棱两可的正确证明。

您对第 2 点的理解是有缺陷的。如果 L(G) 中的某个 w 具有多个最左（或最右）推导，则文法 G 是不明确的。您已经展示了 w=bbaa 的一个最左推导，因此如果您可以展示另一个（即，同一字符串的不同最左推导），那将证明模棱两可。但是，似乎没有，因此您必须选择不同的字符串。

请注意，这与推导是否涉及递归/自反产生式的应用无关。

1 回答 1