context-free-grammar - 上下文无关语法模棱两可？

Question

对于以下上下文无关语法：

S --> (S) | SS | A

A --> a | A,A | E        (E is the empty string)

正式的定义是：

G=(V,T,P,S)

V={A,S}

T={E;a; ( ; ) ; , }

S=S

P:
S --> (S)
S --> SS
S --> A
A -->a

A -->A,A

A --> E    (E is the empty string)

我怎么知道这个语法是否模棱两可？谢谢你。

Answer 1

如果它是模棱两可的，那么您找到一个以多种不同方式解析的单词就足够了。为了证明它没有歧义，您可以使用更一般的证明并证明这是一种特殊情况，您可以根据生成的单词集的某些属性通过归纳建立证明。

请参阅此处的（尽管很复杂）示例。