这个CFG怎么写？

Question

问题是构建一个生成语言的CFG。

​

​

我的解决方案是：S -> aSb | aS | bS | a | b，然而，这个语法也可以生成像aabb这样的字符串，那么如何做呢？

谢谢你帮忙。

Answer 1

因此，您需要一个a的字符串，然后是b的字符串，a和b的数目不等。首先，让我们忽略相等的条件。然后：

S -> aSb | 0

将生成以a和b开头的所有字符串。该规则保证a和b的字符串或空字符串的数量相等。现在我们想要的要么是更多的a，要么是更多的b，但不是两者兼而有之。因为如果我们想要多一个a和一个b，我们就会再次应用S。因此，我们添加了两个新规则：

A -> aA 
B -> bB

并将S更新为：

S -> aSb | A | B

因此，现在我们可以添加相同数量的a和b，或者添加更多的a，或者添加更多的b，但两者都不能。这保证了不平等，所以我们几乎完成了。如果不需要空字符串，就可以在这里停止。对于空字符串，我们不能：

S -> aSb | A | B | 0，

因为这可能导致S -> aSb -> a0b -> ab，这违反了条件。我们也做不到：

A -> aA | 0，

因为这样可以产生S -> aSb -> aAb -> a0b -> ab。那么我们该怎么办呢？诀窍是迫使S以后的扩展至少有一个a或b，如下所示：

S -> aSb | aA | bB
A -> aA | 0
B -> bB | 0

这就是你的解决方案。