不能得到这个终结符串的替换：一个简单的例子是如果在第一步时使用产生式2，那么将会得到E?E＋E，而无论对这两个E再做任何替换都无法把E+E变成a?(a?b00)了。

我们可以通过使用关系符号?来简化推导过程：首先由基础可知E?E，然后反复使用归纳部分可以得到E?E?E，E?I?E等等，直到最终的E?a?(a?b00)。

递归推理和推导这两种观点是等价的。换句话说，能够推理出一个终结符号串w属于某个变元A的语言当且仅当A?w。然而，想要证明这件事还需要一些其它的工作，我们将放到后面的第5.2节再来完成。□

?????? CFG推导中的符号表示 在讨论CFG时，对不同符号的表示方法有许多约定俗成的惯例，比如： 1. 字母表中开头的几个小写字母如a, b等表示终结符号，数字和其它字符比如＋或括号总表示终结符号。 2. 字母表中开头的几个大写字母如A, B等表示变元。 3. 字母表中结尾的几个小写字母如w或z表示终结符号串。这种约定提示我们：在自动机中的输入符号和终结符号串是类似的。 4. 字母表中结尾的几个大写字母如X或Y可以表示终结符号或者变元。 5. 小写的希腊字母如α和β表示由终结符号和（或）变元构成的串。 其中没有只由变元构成的串，原因是这种串的意义不大。然而，一个名叫α或其它希腊字母的串可以只包含变元。

5.1.4 最左和最右推导

当推导一个串时，我们可通过如下的方法来限制可选推导的数目：在每一步推导中只将最左边的变元替换成该变元的某个产生式体，这种方式的推导叫做最左推导（Leftmost Derivation），用关系符号?和?分别来表示一步和多步的最左推导。如果文法G在推导

lm?lm中不是很清楚，那么也可以把它放到这两个符号中箭头的下边。

类似的，也可以每次只替换串中最右边的变元，这样的推导叫做最右（Rightmost）（推导），使用符号?和?分别来表示一步和多步的最右推导。同上，如果不是很清楚

rm?rm的话，相应文法的名字也可以写在箭头下边。

例5.6：例5.5中的推导实际上是一个最左推导，因此，我们也可以这样写：

E?E?E?I?E?a?E?lmlmlmlma?(E)?a?(E?E)?a?(I?E)?a?(a?E)?lmlmlmlm

a?(a?I)?a?(a?I0)?a?(a?I00)?a?(a?b00)lmlmlm我们也可以把上面的最左推导精简为E?a?(a?b00)，或者分多步来表达推导的过

lm?程，比如其中的某一步为E?E?a?(E)。

lm?如果采用最右推导，虽然对串中的每个变元实际上做了同样的替换，但替换的次序不同。具体写出来就是：

E?E?E?E?(E)?E?(E?E)?rmrmrmrmE?(E?I)?E?(E?I0)?E?(E?I00)?E?(E?b00)?

rmrmrmrmE?(I?b00)?E?(a?b00)?I?(a?b00)?a?(a?b00)rmrmrm这个推导的精简表示是E?a?(a?b00)。

rm?任何推导都有等价的最左和最右推导。也就是说，如果w是一个终结符号串，A是一个变元，那么A?w当且仅当A?w，也当且仅当A?w，具体的证明将在第5.2节中给

lmrm???出。

5.1.5 文法的语言

如果G ＝ (V, T, P, S)是一个CFG，那么G的语言（language）（记做L(G)）是指能从开始符号推导出的所有终结符号的集合。也就是：

L(G)?{w in T|S?w}

G?如果一个语言L是某个上下文无关文法的语言，那么L就叫做上下文无关语言，或者CFL。例如，我们断定图5.1中的文法定义了字母表为{0, 1}上的回文的语言，因此，这些回文的集合就是一个上下文无关语言。具体的证明如下：

定理5.7：L(Gpal)是字母表为{0, 1}上的回文的集合，其中Gpal是例5.1中的文法。 证明：我们将要证明一个{0, 1}*中的串w在L(Gpal)中当且仅当它是一个回文，即w = wR 。 （充分性）假定w是一个回文，我们使用数学归纳法通过对|w|进行归纳来证明w在L(Gpal)中。

基础：长度0和1为归纳基础。如果|w|是0和1，那么w一定是ε，0或1，由于有产生式P?ε，P? 0和P? 1，因此在上面任何一种情况下都有P?w。

?归纳：假定|w|≥2。因为w = wR，所以w的开头和结尾一定是同一个字符，即w=0x0或w=1x1，并且x也一定是一个回文，即x = xR。注意：为了说明w的两端确实有两个字符，需要用到|w|≥2的假定。

如果w=0x0，则根据归纳假设有P?x，继而可以得到从P到w的推导

?P?0P0?0x0?w。如果w=1x1情况类似，只是第一步推导所需的产生式是P?1P1。在这两种情况下都可以得出w在L(Gpal)中，证毕。

（必要性）现在假定w在L(Gpal)中，即P?w，要证明的是w是一个回文。证明的过程是对从P到w的推导过程的步数进行归纳。

基础：如果该推导是一步完成的，那么它一定使用了三个在体中不包含P的产生式之一，即该推导为P?ε，P?0或P?1。因为ε，0和1都是回文，因而基础得证。

归纳：现在，假定该推导共包含n + 1步，其中n≥1，并且对于任何n步完成的推导上述结论都成立——也就是说，如果P?x可在n步完成，那么x一定是回文。

考虑一个w的(n + 1)-步推导，它一定是如下形式：

???P?0P0?0x0?w

或者P?1P1?1x1?w，原因是n + 1步其实最少是两步，而且能够增加推导步数的产生式只有P?0P0和P?1P1。注意在这两种情况中的P?x都能在n步完成。 根据归纳假设可知x是回文，即x = xR，但是如果这样的话就有0x0和1x1也都是回文，比如(0x0)R = 0x R 0 = 0x0。由此可知w也是回文，证毕。□

??? 文法证明的形式 定理5.7是一个典型的例子，它证明了某个文法确实定义了某个已经非形式化定义好的特定的语言。首先要给出一个归纳假设，用它来描述每个变元所推导出的串都要满足的性质。在这个例中只有一个变元P，因此只要声明它所代表的串就是回文串即可。 然后证明“充分性”这部分：即如果一个串w满足某一个变元A的串所应该有的非形式化陈述了的性质，那么就应该有A?w。在这个例中，因为P是开始符号，因此?P?w就意味着w在这个文法的语言中。通常我们用数学归纳法，通过对w的长度进行归纳来证明“充分性”这部分。如果有k个变元的话，那么可以证明归纳陈述应该包含k个部分，并且它们之间应该能被证明是互归纳的关系。 接着要证明“必要性”这部分，即如果A?w，那么w应该满足A所能推导出的串所应该有的非形式化陈述了的性质。同样，在这个的例中，只有开始符号P需要证明，并且认为w在Gpal的语言里和P?w是等价的。这部分的证明通常需要对推导的步数进行归纳。如果该文法有这种类型的产生式：该产生式所推导出的串中可能包含两个或更多的变元，那么就应该把一个n步的推导分成若干部分，每个变元一个部分。这些部分可能比n步少，因此就必须使用对所有小于等于n的情况都包含的归纳假设，就像1.4.2节中所说的那样。

???5.1.6 句型

由开始符号推导出来的串有着很特殊的作用，它们称作“句型”，即如果

G?(V,T,P,S)是一个CFG，那么任何在(V∪T)*中且满足S??的串α都是句型。如果

?S??则α是左句型，如果如果S??则α是右句型。注意语言L(G)是由所有属于T*的

lmrm??句型组成的，也就是由只含终结符号的句型组成的。

例5.8：考虑图5.2中表达式的文法。例如，E?(I?E)是一个句型，因为可以有这样一个推导：

E?E?E?E?(E)?E?(E?E)?E?(I?E)

然而这个推导既不是最左的也不是最右的，原因是在最后一步中被替换的是中间的E。

举一个左句型的例子：考虑a?E，存在最左推导：

E?E?E?I?E?a?E

lmlmlm类似的，下面的推导

E?E?E?E?(E)?E?(E?E)

rmrmrm可以说明E?(E?E)是一个右句型。□

5.1.7 5.1节习题

习题5.1.1：设计下列语言的上下文无关文法：

* a) 集合{0n1n | n≥1}，即所有一个或多个0后面跟着相同数目的1的串的集合。 *! b) 集合{aibjck | i≠j 或 j≠k}，即所有满足如下性质的串的集合：若干个a后面跟着若干

个b，后面再跟着若干个c，并且或者a和b的数目不同，或者b和c的数目不同，或者两者都不同。 ! c) 所有不是ww形式的由a和b构成的串的集合，即不是把某个串任何重复了一遍的

串。 !! d) 所有0的个数是1的个数两倍的串的集合。

习题5.1.2：下面的文法产生了正则表达式0*1(0+1)*的语言：

S?A1BA?0A|?B?0B|1B|?试给出下列串的最左推导和最右推导： * a) 00101。 b) 1001。 c) 00011。

! 习题5.1.3：证明任何正则语言都是上下文无关语言。提示：通过对正则表达式中的运算符的数目进行归纳的方法来构造CFG。

! 习题5.1.4：如果一个CFG的每个产生式的体都最多只有一个变元，并且该变元总在最右端，那么该CFG称做右线性的。也就是说，右线性文法的所有产生式都是A?wB或A?w的形式，其中A和B是变元，w是由零个或多个终结符号所组成的串。

a) 证明任何右线性文法所产生的语言都是正则语言。提示：构造一个ε-NFA来模拟最左推导，并用它的状态来表示当前左句型中的单个变元。 b) 证明任何正则语言都有右线性文法。提示：用一个DFA，并且用文法的变元来表示状态。 *! 习题5.1.5：设T?{0,1,(,),?,*,?,e}，可以把T看作字母表为{0, 1}的正则表达式所使用的符号的集合，唯一的不同是用e来表示符号ε，目的是为了避免有可能出现的潜在的混淆。你的任务是以T为终结符号集合来设计一个CFG，该CFG生成的语言恰好是字母表为{0, 1}的正则表达式。