形式语言与自动机理论--第二章 文法-3（第五周）

1、第2章 文法 1.语言结构分析2.文法形式定义3.文法的构造4.文法的乔姆斯基体系5.空语句6.小结14.文法的乔姆斯基体系定义2-7 线性文法(liner grammar) 设G=(V，T，P，S)，如果对于P，均具有如下形式：AwAwBx其中A，BV，w，xT*，则称G为线性文法。线性语言(liner language) L(G)叫做线性语言24.文法的乔姆斯基体系定义2-8 右线性文法(right liner grammar) 设G=(V，T，P，S)，如果对于P，均具有如下形式：AwAwB其中A，BV，wT+，则称G为右线性文法。右线性文法就是RG右线性语言(right liner l

2、anguage) L(G)叫做右线性语言。34.文法的乔姆斯基体系左线性文法(left liner grammar) 设G=(V，T，P，S)，如果对于P，均具有如下形式：AwABw其中A，BV，wT+，则称G为左线性文法。左线性语言(left liner language) L(G)叫做左线性语言。44.文法的乔姆斯基体系定理2-2 L是一个左线性语言的充要条件是存在文法G，G中的产生式要么是形如：Aa的产生式，要么是形如ABa的产生式，使得L(G)=L。其中A、B为语法变量，a为终极符号。 54.文法的乔姆斯基体系定理2-3 左线性文法与右线性文法等价。 按照定理2-1的证明经验，要想证明

3、本定理，需要完成如下工作：对任意右线性文法G，我们能够构造出对应的左线性文法G，使得L(G)=L(G)；对任意左线性文法G，我们能够构造出对应的右线性文法G，使得L(G)=L(G)。64.文法的乔姆斯基体系例 2-17 语言0123456的左线性文法和右线性文法的构造。右线性文法Gr：Sr0ArAr1BrBr2CrCr3DrDr4ErEr5FrFr6 74.文法的乔姆斯基体系0123456在文法Gr中的推导 Sr0Ar使用产生式Sr0Ar 01Br使用产生式Ar1Br 012Cr 使用产生式Br2Cr 0123Dr 使用产生式Cr3Dr 01234Er使用产生式Dr4Er 012345Fr使用

4、产生式Er5Fr 0123456使用产生式Fr684.文法的乔姆斯基体系左线性文法Gl：SlAl6 AlBl5 BlCl4 ClDl3 DlEl2 ElFl1 Fl0 94.文法的乔姆斯基体系104.文法的乔姆斯基体系0123456在文法Gl中的推导 SlAl6使用产生式SlAl6 Bl56使用产生式AlBl5 Cl456使用产生式BlCl4 Dl3456使用产生式ClDl3 El23456 使用产生式DlEl2 Fl1234456使用产生式ElFl1 0123456使用产生式Fl0 114.文法的乔姆斯基体系0123456被归约成文法Gl的开始符号S 0123456 Fl1234456使用产

5、生式Fl0 El23456使用产生式ElFl1 Dl3456使用产生式DlEl2 Cl456使用产生式ClDl3 Bl56使用产生式BlCl4 Al6使用产生式AlBl5 Sl使用产生式SlAl6 124.文法的乔姆斯基体系134.文法的乔姆斯基体系定理 2-4 左线性文法的产生式与右线性文法的产生式混用所得到的文法不是RG。证明：设有文法G15：S0AAS1|1 不难看出，L(G15)=0n1n|n1。我们构造不出RG G，使得L(G)= L(G15)=0n1n|n1。因为L(G15)=0n1n|n1不是RL。所以，G15不是RG。有关该语言不是RL的证明我们将留到研究RL的性质时去完成。

6、145. 空语句 形如A的产生式叫做空产生式，也可叫做产生式。 在RG、CFG、CSG中，都不能含有空产生式。所以，任何CSL中都不含有空语句。从而CFL和RL中都不能含空语句。 空语句在一个语言中的存在并不影响该语言的有穷描述的存在性，甚至除了为生成空语句外，空产生式可以不被用于语言中其他任何句子的推导中。 155. 空语句 允许CSL、CFL、RL包含空语句后，还会给问题的处理提供一些方便。 允许在RG、CFG、CSG中含有空产生式允许CSL、CFL、RL包含空语句。 165. 空语句 定理2-5 设G=(V，T，P，S)为一文法，则存在与G同类型的文法G=(V，T，P，S)，使得L(G)

7、=L(G)，但G的开始符号S不出现在G的任何产生式的右部。证明：（1）当文法G=(V，T，P，S)的开始符号S不出现在P中的任何产生式的右部时，G就是所求的G175. 空语句 （2）如果不满足（1）的情况，则取S V，G=(VS，T，P，S) 其中 P=PS|SP 上述文法满足定义要求的G，只需证明在“但G的开始符号S不出现在G的任何产生式的右部”条件下， L(G)= L(G) 分析：如果L(G) L(G) 且L(G) L(G) 则L(G)= L(G) 所以分别证明L(G) L(G) 和L(G) L(G) 均成立即可。185. 空语句 （1）证明L(G) L(G)思路：如果对于任意的xL(G)

8、 都能证明xL(G)，则 L(G) L(G)成立证明：对任意的xL(G)，由文法产生的语言的定义知，在G中存在如下推导： S 使用产生式S（根据定理，S仅在产生式左侧出现，所以由推导出x必定通过P中的除S以外的其他产生式产生的，即 *x 195. 空语句 因为P=PS|SP 所以推导*x中使用的产生式都是P中的产生式。因此，推导*x在G中仍然成立。由P的定义知，必有SP 所以， S使用P中的产生式S *x使用P中的产生式 故，x L(G) 所以： L(G)L(G) 成立205. 空语句 （2）证明 L(G)L(G)对任意的xL(G)，G中存在如下推导： S使用P中的产生式S *x使用P中的产生

9、式由P=PS|SP ，知道G中， S使用产生式S *x使用P所包含的P中的其他产生式。 故， x L(G)所以L(G)L(G)。 综上，定理得到证明。215. 空语句 定义2-10：设G=(V，T，P，S)是一个文法，如果S不出现在G的任何产生式的右部，则： 如果G是CSG，则仍然称G=(V，T，PS，S)为CSG；G产生的语言仍然称为CSL。 如果G是CFG，则仍然称G=(V，T，PS，S)为CFG；G产生的语言仍然称为CFL。 如果G是RG，则仍然称G=(V，T，PS，S)为RG。G产生的语言仍然称为RL。225. 空语句 定理2-6 下列命题成立： 如果L是CSL，则L仍然是CSL。 如

10、果L是CFL，则L仍然是CFL。 如果L是RL，则L仍然是RL。235. 空语句 证明：对第1个命题：设L是CSL，则存在一个CSG G=(V，T，P，S)，使得L(G)=L。由定理2-5-1，不妨假设S不出现在G的任何产生式的右部。取：G=(V，T，PS，S)由于S不出现在G的任何产生式的右部，所以，S不可能出现在任何长度不为0的句子的推导中。245. 空语句 易证：L(G)=L(G)。由于G是CSG，所以，L(G)是CSL。同理可证第2和第3个命题。 255. 空语句 定理2-7 下列命题成立 如果L是CSL，则L-仍然是CSL。 如果L是CFL，则L-仍然是CFL。 如果L是RL，则L-

11、仍然是RL。 265. 空语句 证明：对第1个命题：设L是CSL，则存在一个CSG G=(V，T，P，S)，使得L(G)=L。如果L，则L-=L，所以， L-是CSL。如果L，由定理2-5，不妨假设S不出现在G的任何产生式的右部。取：G=(V，T，P-S，S)275. 空语句 由于S不出现在G的任何产生式的右部，所以，如果L(G)中存在长度非0的句子，S不可能出现在它们的推导中。也就是说，将S从G中去掉后，不会影响L(G)中任何长度非0的句子的推导。容易证明： L(G)=L(G)-由于G是CSG，所以，L(G)-是CSL。同理可证其他两个命题。 285. 空语句 对于任意文法G=(V，T，P，

12、S)，对于G中的其他变量A，出现形如A的产生式是不会改变文法产生的语言的类型的，而且这样一来，对我们进行文法的构造等工作还提供了很多方便。所以，我们约定：对于G中的任何变量A，在需要的时候，可以出现形如A的产生式。 296. 小结 本章讨论了语言的文法描述。首先介绍文法的基本定义和推导、归约、文法定义的语言、句子、句型、文法的等价等重要概念。 讨论了如何根据语言的特点、通过用语法变量去表示适当的集合（语法范畴）的方法进行文法构造， 介绍了文法的乔姆斯基体系，将文法划分成PSG、CSG、CFG、RG等4类。 在这些文法中，线性文法是一类重要的文法。 306. 小结 文法G=(V，T，P，S)。任意AV表示集合L(A)=w | wT*且A * w。 推导与归约。文法中的推导是根据文法的产生式进行的。如果P，(VT)*，则称在G中直接推导出：G ；也称在文法G中直接归约成。316. 小结 语言、句子和句型。文法G产生的语言L(G)=w | wT*且S * w，