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

发布于 2024-10-07 08:11:35 字数 507 浏览 3 评论 0原文

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

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

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

原文

I am studying for my finals & I was reading context free grammars article from wikipedia and came across following example.

S → SS- (1st production rule)

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

S → () - (3rd production rule)

I am well aware of left and right derivation. When I tried to solve this problem I start with start symbol

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

but when I looked the answer, it was like this

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

I am not sure what goes wrong with my answer? Is it necessary to use first production rule twice? Could anybody help me with this.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

故人爱我别走 2024-10-14 08:11:35

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

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

回复收藏 0 原文

只为一人 2024-10-14 08:11:35

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

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

<前><代码>S-> SS-> (S)S-> ()S-> ()(S)-> ()()

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

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

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

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

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

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

您可以根据需要多次应用产生式规则（当然假设您要替换的非终结符存在于术语中）并按您想要的任何顺序。这完全取决于您想要派生哪个词。

When I tried to solve this problem I start with start symbol

What problem? The wikipedia article doesn't pose any problem. It just shows a grammar describing the language of well-matched parentheses and gives an example of a word in that language and how to derive it.

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

That's a perfectly valid derivation.

but when I looked the answer, it was like this

That's not the answer (there was no question). It's just an example.

I am not sure what goes wrong with my answer?

There's nothing wrong with your derivation. Both ()() and ((()()))()(()) are valid words in the language.

Is it necessary to use first production rule twice?

You can apply the production rules as often as you want (assuming of course the non-terminal you want to replace is present in the term) and in any order you want. It all just depends on which word you want to derive.

回复收藏 0 原文