构造语言为{a，b}的语法
{a^m b^n | 0 <= n <= m <= 3n}
我不知道如何解决这个问题，我开始做了
n >= 0
m >= n
3n >= m
S -> a S b | a S bb
那非常接近。有一些问题：
bs比as更多。但是bs（n）的数量小于或等于as（m）的数量。没有更多的bs。而不是为每个b添加一个或两个as，你需要为每个a添加一个或两个bs。 （但见下文。）a与一个或两个bs配对的情况，如上所述应该被颠倒，以便额外的b与一些as配对。但是语言描述说m≤3* n *，而不是m≤2* n *;另外一个b可与多达三个as配对。我发现从语言中最短的字符串开始，然后尝试从那里进行推广是有帮助的。这种语言中最短的字符串是什么？我们可以选择n = 0和m = 0，因为0 <= 0 <= 0 <= 3x0，所以空字符串是我们的语言。因为空字符串是语言，我们必须在我们的语法中有S := e。
现在，我们如何在语言中获得更长的字符串？我们可以添加一些产品只是为了添加一个字符串，或者只是添加b;但是，这样的规则不能用于扩展我们的基本情况（S := e），因为在空字符串中添加only或b only将不会获得该语言中的字符串。这些作品可能会让我们用语言中的字符串，但它们不会以明显或简单的方式让我们走这条路。我们想要简单的语法制作，所以我们可以确信它是正确的。
分别添加a和b的替代方法是将它们添加到一起。请注意，如果您的语言中部分字符串彼此依赖，则通常（除了明显但非实际依赖性的情况除外）通常会发现产品必须与那些相关部分相关联;否则，在派生字符串期间可以“忘记”依赖性。我们假设我们的作品应该只将a和b加在一起并继续这个假设。
首先，我们可能会猜测生产S := aSb应该包含在我们的语法中。我们为什么猜这个？那么，基于我们的假设，我们知道我们需要将a和b加在一起，我们在这里做。此外，由于我们希望规则生成一般长度的字符串，我们理解生产必须涉及非终端，我们目前只有一个非终端（还记得我们正在努力在我们的基础案例上构建字符串，是由S生产的;所以使用这种非终结是自然的）。最后，我们知道所有a必须位于所有b的左侧，这是根据该模式生成字符串的三个符号的唯一排序。
这个产品允许我们生成什么字符串？我们可以得到S := e，S := aSb := ab，S := aSb := aaSbb := aabb，...，S := … := (a^n)(b^n)。我们观察到这些字符串是在语言中 - 因为0 <= n <= n <= 3n - 但是有一些字符串，这些字符本身就错过了。在这种情况下，生产是好的，应该保持;然而，我们错过了一些字符串表示我们需要找到其他产品来涵盖这些案例。
我们错过了哪些案例？我们错过了m严格大于n的情况。在我们猜测的制作中，我们使用相同数量的a和b，因此我们最终得到具有相同数字的字符串。按理说，如果我们想要的字符串多于b，那么我们需要的产品比b更多。根据我们的假设，我们仍然要求我们至少引入其中之一;我们已经介绍了一个，每个都有一个。下一个猜测的逻辑生产是S := aaSb。我们现在可以生成什么字符串？如果我们忽略生产S := aSb，这个新的生产允许我们用我们的语言生成(a^2n)(b^n)形式的字符串;但是当我们考虑所有三部作品时会发生什么？
考虑字符串(a^k)(b^n)，其中n <= k <= 2n。如果k = n那么我们可以使用生产S := aSb n次来获得字符串;同样，如果k = 2n，我们可以使用生产S := aaSb n次。怎么样n < k < 2n？假设k = n + j，其中0 <j <n。在那种情况下，我们可以使用生产S := aaSb恰好j次，并且生产S := aSb正好n - j次，以获得2j + n - j = n + j = k实例a和n个b实例。因此，这三个规则一起允许我们生成所有字符串，其中a的数量在b的数量和b的数量的两倍之间，包括在两端。
我们仍然无法生成字符串，其中a的数量是b的两倍以上;然而，基于我们上面的成功，我们可以猜测S := aaaSb并使用类似的推理来表明这四个产品一起给我们准确的语言产生。我们得到的语法如下：
S := e
S := aSb
S := aaSb
S := aaaSb
这种语言还有很多其他的语法，都是正确的，很多人使用完全不同于此的其他方法。不要将这些问题视为应用公式来获得预定答案。把这样的问题想象成它们是什么：编程问题。你得到了规范，只要你的东西有效，那就重要了。