上下文无关语法和反转
我正在设计一个上下文无关语法来生成这种语言：
{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* }
我将前两个字符串定义为：
U -> aU | bU | _
V -> aV | bV | _
然后将它们组合起来：
S -> UV
但是如何将反转表达为上下文无关语法？
I'm designing a context-free grammar to generate this language:
{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* }
I would define the first two strings as:
U -> aU | bU | _
V -> aV | bV | _
And then combine those:
S -> UV
But how do I express the reversal as context-free grammar?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您需要利用语法的上下文无关性（到目前为止您所呈现的只是常规语法）：
将匹配“ababa”和“aabaa”等内容，但不匹配“aabba”。
我将让您根据需要进行更改 - 但请记住，您指定的语言有可能
u为空字符串，因此它会生成{a 中的所有字符串,b}*。You need to make use of the context-free-ness of the grammar (what you're presenting so far is just a regular grammar):
Will match things like "ababa" and "aabaa", but not "aabba".
I'll leave it to you to alter this to your needs - but keep in mind that your specified language has the possibility of
ubeing the empty string, hence it generates all strings in{a,b}*.