computer-science - 上下文无关语法-计算理论

Question

我正在准备期末考试，我正在阅读维基百科上的上下文无关语法文章，并发现了以下示例。

S → SS- (1st production rule)

S → (S) - (2nd production rule)

S → () - (3rd production rule)

我很了解左推导和右推导。当我尝试解决这个问题时，我从开始符号开始

S-> SS -> (S)S-> ()S-> ()(S) -> ()() 

但是当我查看答案时，它是这样的

S → SS → SSS → (S)SS → ((S))SS → ((SS))S(S)
→ ((()S))S(S) → ((()()))S(S) → ((()()))()(S)
→ ((()()))()(())

我不确定我的回答有什么问题？是否有必要使用第一个产生式规则两次？有人可以帮我解决这个问题吗？

Answer 1

您的方法没有任何“错误” - 您刚刚导出了与维基百科文章不同的符号序列。

关键的一点是，可以使用语法派生出任何匹配的嵌套括号序列，但不能派生出像 (() 或 )( )(。