上下文无关文法.计算理论

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

当我试图解决这个问题时，我从开始符号开始

什么问题？维基百科的文章没有提出任何问题。它只是展示了一种描述良好匹配括号语言的语法，并给出了该语言中的一个单词的示例以及如何派生该单词。

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

这是一个非常有效的推导。

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

这不是答案(没有问题)。这只是一个例子。

我不确定我的答案出了什么问题？

你的推导没有任何问题。()()和((()()))()(())都是该语言中的有效单词。

第一产生式规则是否有必要使用两次？

您可以随心所欲地应用产生式规则(当然，假设您想要替换的非终端出现在术语中)，并且可以按照您想要的顺序应用。这完全取决于你想要派生出哪个单词。

Answer 2

你的方法没有什么“错误”--你只是给维基百科的文章派生了一个不同的符号序列。

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

Answer 3

这篇文章只是给出了一个可能的字符串，它可以用这种语法来表示……您给出的是另一个可能的字符串。您可以使用派生来证明这些字符串根据语法是有效的(即，在相反的方向)。

编辑:精打细算:P