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)
→ ((()()))()(())

我不确定我的回答出了什么问题？是否需要两次使用第一个生产规则？任何人都可以帮我解决这个问题。

score 2 · Accepted Answer

您的方法没有任何“错误” - 您刚刚为 Wikipedia 文章派生了不同的符号序列。

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

score 1 · Accepted Answer

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

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

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

这是一个完全有效的推导。

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

那不是答案（没有问题）。这只是一个例子。

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

你的推导没有错。两者都是语言()()中((()()))()(())的有效词。

是否需要两次使用第一个生产规则？

您可以根据需要经常应用生产规则（当然假设您要替换的非终端存在于术语中）并且以您想要的任何顺序。这一切都取决于你想派生哪个词。

score 1 · Accepted Answer

这篇文章只是给出了一个可以使用该语法表示的可能字符串......您正在给出另一个可能的字符串。您可以使用推导来证明这些字符串根据语法是有效的（即反向进行）。

编辑：被打败了：P

3 回答 3