上下文无关语法问题
对于初学者来说，这是一个家庭作业问题。我有一个想法，但我仍然无法得到正确的答案。我不是在寻求答案，我只是寻求帮助来回答问题。
我目前正在尝试为该语言编写上下文无关语法
a(iterated i times)db(iterated j times), for i and j>=0, and j = 2 * i.
所以基本上 a 的数量是 b 的两倍，并且两者之间的 ad 数量。例如：
d, adbb, aadbbbb, ……
这是关于我所拥有的，我没有太多...我理解这些 CFG 的概念我只是不确定这个问题的逻辑。我不确定我是否走在正确的方向...
S -> AdB
A -> EMPTY
A -> aAB
B -> DD
谢谢。
For starters this is a homework question. I have an idea but I am still not able to get the correct answer. I'm not asking for the answer I am just asking for help to answer the question.
I am currently trying to write a context free grammar for the language
a(iterated i times)db(iterated j times), for i and j>=0, and j = 2 * i.
So basically there are twice as many a's as b's and a d in between the 2. For example:
d, adbb, aadbbbb, ……
Here is about what I have, I don't have much... I understand the concept of these CFG's I am just not sure about the logic for this question. I am not sure If i am even going the right direction...
S -> AdB
A -> EMPTY
A -> aAB
B -> DD
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
每当你有一种语言时，你都可以像这样列出，其中每个字符串都是后面字符串的子字符串，编写一个简单的递归语法相当简单。您需要一个规则来创建第一个（最短）字符串，并需要一个规则来从前一个字符串创建每个较长的字符串。
Whenever you have a language you can list out like this, where each string in a substring of the following string, its fairly trivial to write a simple recursive grammar. You need a rule to make the first (shortest) string, and a rule to make each longer string from the previous string.
我想我会先说你只需要 2 个语句来解决这个问题。不过，如果我要给你更多的东西，我宁愿看到你的一些工作（即使方向错误！）。
编辑
感谢您发布您所拥有的内容。这里有一些思考练习，希望能让你朝着正确的方向前进：
如果您仍然遇到困难，维基百科关于 CFG 的文章对此有一些帮助。
当你得到最后一个时，你会看到一些简单的补充来了解你的语法。
I guess I'll start off hints by saying that you only need 2 statements to solve this. I'd rather see some of your work (even in the wrong direction!) if I'm to give you any more, though.
EDIT
Thanks for posting what you've got. Here's a couple thought exercises that will hopefully get you moving in the right direction:
Wikipedia's article on CFG's has some help on this if you're still stuck.
When you get that last one, you'll see the trivial addition to get to your grammar.