构建CFG
如何为语言 x^ay^bz^2(a+b) 构造上下文无关语法，其中 a>=0，b>=0。 感谢您的帮助...
How can I construct a Context-Free Grammer for the language x^a y^b z^2(a+b) where a>=0, b>=0.
Thanks for helps...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这样想
所以
Think of it this way
Therefore
请注意，对于每个
x和每个y，您需要生成两个z，因为 2(a + b）。另外，请注意每个字符串都可以被视为y和z的“内部”部分，以及x< 的“外部”部分。 /code> 和z。由于对于每个
y，您需要两个z，因此内部部分可以通过（使用大写字母表示非终结符和[]对于空字符串）：现在以相同的方式为外部部分编写语法，但在基本情况中引用
I。Observe that for each
xand for eachy, you need to generate twoz's because of the 2(a + b). Also, observe that each string can be viewed as an "inside" part ofy's andz's, and an "outside" part ofx's andz's.Since for each
yyou need twoz's, the inside part can be described by (using capitals to denote non-terminal symbols and[]for the empty string):Now write a grammar for the outside part in the same way, but referring to
Iin the base case.本质上，您需要处理两种情况：
x，在这种情况下，您需要在以下位置添加两个z：结束。y，在这种情况下，您还需要在末尾添加两个z。尝试将这些描述简化为您知道解决方案的更简单的语法（例如
a^nb^n）。这个提示应该足以推断出生成语法。
There are essentially two cases that you need to treat:
xat the beginning of the string, in which case you need to add twoz’s at the end.yin the middle, in which case you also need to add twoz’s at the end.Try reducing either of these descriptions to a simpler grammer (e.g.
a^n b^n) for which you know the solution.This hint should be enough to deduce the generative grammer.