2

对于初学者来说，这是一个家庭作业问题。我有一个想法，但我仍然无法得到正确的答案。我不是在寻求答案，我只是在寻求帮助来回答问题。

我目前正在尝试为该语言编写上下文无关语法

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

谢谢。

4

2 回答 2

1

我想我会先说你只需要 2 个语句来解决这个问题。不过，如果我要给你更多的话，我宁愿看看你的一些作品（即使是在错误的方向上！）。

编辑

感谢您发布您所拥有的。这里有一些思想练习，希望能让你朝着正确的方向前进：

写一个语法，表达n > 0 (ab, aabb, aaabbb, ... )

如果您仍然遇到困难，维基百科关于 CFG 的文章会对此有所帮助。

编写一个语法，表示 n > 0 时的n db n (adb, aadbb, aaadbbb, ...)

当你得到最后一个时，你会看到对语法的微不足道的补充。

于 2010-11-01T21:00:44.947 回答
1

每当您拥有一种语言时，您都可以像这样列出，其中每个字符串在以下字符串的子字符串中，编写简单的递归语法相当简单。您需要一个规则来制作第一个（最短的）字符串，以及一个规则来从前一个字符串中制作每个较长的字符串。

于 2010-11-01T21:02:26.380 回答