上下文免费语法设计

Question

我正在学习Context Free Grammars，到目前为止我一直在理解它们，但这个问题让我头晕目眩。

我有以下规则：

S --> aSb | bB | epsilon
B --> bbB | bB | epsilon

我几乎可以肯定他们是不正确的。我理解如何只用<= j而不是实际的语言，但是j <= 3i的想法对我来说真的很难理解，我真的不明白我应该如何在CFG中代表它。

我已经在这里阅读了一些有关设计CFG的问题和线索，但它们并没有真正帮助我制定确定答案的策略。

在此先感谢您的帮助！

Answer 1

对于字符串中的任何a，您必须在字符串中包含1,2或3个bs。

bs必须遵循as。

你可以有零as。

S = A S B | e
A = a
B = b | bb | bbb

零as意味着没有bs。

一个a允许1个，2个或3个bs。

通过S的递归你可以有任意数量的as。

Answer 2

您的解决方案确实不正确，因为不遵守条件j <= 3i。

比Björn更接近您的意图的解决方案，并且使用更少的非终端：

S -> aSb | aSbb | aSbbb | epsilon