给定语言K={e^hf^i|2h>i>h}，我需要生成一个上下文无关的语法
我想出的一些生产规则是：S->eeTfff和T->eTff|õ
它们只在n=m+1时工作，但我不知道如何为2h>I>h中的每个组合生成任何规则。
首先，确定语言中最短的字符串。我们需要i>h，所以我们可以猜测h=0；然而，这没有任何结果，因为我们不能满足2h>i。我们遇到了与h-1相同的事情。如果选择h=2，则i的唯一选择是3。因此，该语言中最短的字符串是eefff。不能有任何其他长度为5的字符串。
为了得到更长的字符串，我们可以在前面加e或在后面加f。显然，如果我们在前面加一个e，我们必须在后面加至少一个f，永远不要超过两个f。我们可以确认e.eefff.f和e.eeff.ff都是我们的语言。这表明了一种语法：
S -> eefff | eSf | eSff
一旦你找到了一个候选人，你可以试着用数学归纳法来证明它。在我们的案例中：
基本情况：eefff语言中最短的字符串由产品S -> eefff给出。
归纳假设：假设语法生成语言中的所有字符串，并且语法生成的所有字符串都在语言中，对于长度不超过k的所有字符串。
归纳步骤：我们必须证明(1)语法生成的长度为k+1的字符串在语言中，(2)语言中长度为k+1的字符串由语法生成。
使用
S -> eSf或S -> eSff生成语法生成的长度为k+1的字符串。在第一种情况下，从RHS上的S导出的字符串具有长度k-1；在第二种情况下，它的长度为k-2。在这两种情况下，字符串都是根据归纳假设出现在语言中的。也就是说，h<i<2h。但是随后(h+1)<(i+1)<(i+2)<2(h+1)，所以在任何一种情况下，字符串仍然在该语言中。考虑语言中长度为
k+1的任何字符串。我们有h+i＝k+1，并且h<i<2h。任何这样的字符串都必须以一些e开头，以一些f结尾。考虑长度为k-1和k-2的子串。通过排除第一个e、最后一个和两个f而形成。前者是语言中的字符串，后者是。要了解这一点，请假设两者都不是。但是随后(h-1)<(i-1)<2(h-1)或(h-1"<(i-2)<2(h-1)。即：((i <= h) or (i >= 2h - 1))和((i<＝h+1)或(i>＝2h)
因为我们知道h<i<2小时，因为我们的字符串在L中，我们可以消除第1和第4个条件。剩下的永远不会满足。这表明至少有一个子字符串也在该语言中。根据归纳假设，这个字符串是由语法生成的。要从该字符串中获得长度为k+1的字符串，只需应用S -> eSf或S -> eSff，具体取决于语言中的子字符串(两者都可能)。