形式语言与自动机文法的一般理论.ppt

1,形式语言与自动机（Formal Languages and Automata）,第二章 文法的一般理论,南京航空航天大学计算机科学与技术学院 胡 军,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,2,2.1 问题的提出 2.2 形式文法与形式语言 2.3 文法的乔姆斯基分类,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,3,2.1 问题的提出,任何有意义的语言都不是任意字符串的集合，而是符合某些规则要求的字符串集合.自然语言(英语，语法)；程序设计语言(C语言，文法)；文法(Grammar):用有限个规则描述无穷多字符串的集合自然语言描述(如：英语语法)；严格的形式规则描述（如：C语言文法、Pascal 语言文法）-形式文法，形式语言,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,4,BNF(Backus-Naur Form),例2.1 在类PasCal语言中，是用下述一组规则定义的：:=:=IFTHENElSE:=WHILEDO:=BEGINEND:=；:=:=:=:=|=:=|（）:=+|-|*|/:=0|1|2|3|4|5|6|7|8|9:=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,5,问题的提出,例2.2 根据例2.1中的各规则，下述的字符串 WHILE x5 DO x:=(x+2)是一个合法的语句;因为：整个符合的定义结构；x5是的一种；x:=（x+1）是的一种（从而也是的一种）；,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,6,语法树(分析树，Parser Tree),2023年10月31日星期二,南京航空航天大学计算机学院 胡军,7,问题的提出,例2.3 用下述语法规则定义英语中的句子。thea applecatman eatssingsruns,the apple runs 语法/语义,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,8,2.2 形式文法与形式语言,定义2.1 一个文法G是一个四元组 G=(V,T,P,S)，其中：V：是变元（Variable，Nonterminal）的有限集。T：是终结符（Terminal）的有限集。P：是产生式（Production）的有限集，其中每个产生式都是的形式，其中(VT)+，且其中至少有一个V中的符号，(VT)*。称为产生式的左部，称为产生式的右部。SV，称为文法G的开始符号。(S很重要，决定这组规则最终要定义什么，考虑例2.3中的和)例2.4:G1=(A,B,0,1,A0B,B1B,B0,A)。G2=(A,B,C,a,b,C,AaBC,Bb,CCC,C,A)。G3=(L,M,N,0,1,2,M0LN,L1,0L2,LN12，N0，M)。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,9,文法表示方法的约定,凡有关文法的例子，都遵循下述的约定：大写拉丁字母A,B,C,D,E和S等等表示变元，除非另做说明，S表示开始符号。小写拉丁字母a,b,c,d,e,数字等等表示终结符。小写拉丁字母u,v,w,x,y,z等等表示终结符串。小写希腊字母，等等表示变元和终结符共同组成的串。另外还约定，同一个文法中如果有若干个左部相同而右部不同的产生式，如：1，2，n则可以缩写为：1|2|n在上述约定下，写一个文法时，只写出它的产生式集合就可以了.,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,10,字符串的推导 与 归约,定义2.2 给出文法 G=(V,T,P,S)，我们定义两个字符串之间的一个关系“”：若=123,=13,并且2是P中的一个产生式，则有，此时称由直接推导出。根据第一章关于集合上关系的闭包的定义，我们也可将 扩充为，将 称为由推导出。若有S，则称为句型，当，则称为句子。对应于推导，还有一个重要的概念，称为“归约”。其定义是：如果 是由到的推导，则反过来称归约到，记作。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,11,字符串的推导 与 规约,例2.7 对于例2.6中给出的文法G，我们有：S 0A1 00A11 000A111 000111第一步直接推导用的是第（1）个产生式，第二步直接推导用的是第（2）个产生式，第三步直接推导还是用第（2）个产生式，最后一步直接推导用的是第（3）个产生式。总起来我们也可以写为S 000111。在这个推导中，0A1，00A11，000A111,000111都是句型，而000111又是句子。在今后写推导式子的时候，若所指的文法是明确无误的，则可将记号 或 中的G省略，只写 或 即可。另外，如果经过i步的直接推导到，就可写。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,12,形式文法与形式语言,定义2.3 给出文法 G=(V,T,P,S)，它所产生的语言记作(G)，由下述集合定义：L(G)=|S，并且*。换句话说，文法G产生的语言(G)，就是由G中开始符号S推导出来的全体终结符号串所构成的集合，也就是句子的集合。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,13,文法 语言,例2.8 给出文法G,它有两个产生式：SaSbSab则该文法产生的语言(G)=an bnn1。这是根据(G)的定义，考虑从S的推导，若先用G中第二个产生式，则S ab，就不能再往下推导了，此时相当于语言中1的情况。若从S出发，先用第一个产生式-1次，即S aSb aaSbb an-1S bn-1，最后再使用第二个产生式一次，得到S ab，这个推导对于任何1都是对的。再加上=1的情况，即可得到L(G)an bnn1。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,14,文法语言,例2.9给出文法G，它的产生式是：SaBbAAabAAaSBbaBBbS(G)是由相等个数a和b组成的（次序不限）所有串的集合，加以证明。为了证明最终的结论，要证明以下三个互相关联的命题。S，当且仅当中包含相等个数的a和b。A，当且仅当中a的个数比b的个数多1。B，当且仅当中b的个数比a的个数多1。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,15,文法语言,下面我们用关于w长度的归纳法(多重归纳法)来证明上述三个命题。归纳基础w1。命题（2），（3）显然是对的，因为只能有A a，B b，用其他产生式时都将推导出长度大于1的串。对于命题（1），因为在w1这个大前提下，一方面不可能有S w，另一方面中也不可能包含相等个数的a和b，即“当且仅当”的两个方面都是假的，故命题（1）自然成立。归纳步骤假设对于所有长度不超过k-1的串，命题（1），（2），（3）成立，现在要证当wk时（k2），命题（1），（2），（3）也成立。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,16,文法语言,先证命题（1）。如果S，那么推导的第一步必然是S aB或S bA。对于第一种情形，必然有aw1，且B w1，因为w1k1，则根据归纳法假设，它包含b的个数比a的个数多1（命题（2），因此包含a的个数与b的个数相等。对于S bA的情形，证明完全类似。反之，如果wk，且w包含相等个数的a和b，要证S w。考虑w的第一个符号只有a或b两种情况，若是a，则waw1，且w1k1。由于w1中包含b的个数比a的个数多1，根据归纳法假设，必有B w1（命题（3）。此时使S的第一次直接推导为S aB，然后将B推导到1，最后得到S aw1w。对于w以b开始的情况，可以完全类似地证明。考虑再证明命题（2）和（3）。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,17,语言文法,例2.10 给出语言 a1，找出产生它的文法。a，aa，aaa，它是一个无限集。因此必须先产生出一个a来，我们首先用产生式Sa来实现。因为是无限集，必须用递归的方法，以一个a为基础，不断地添加一个a。即再用一个产生式SaS，与第一个产生式合起来，整个文法就是：SaSaS当然，产生的文法不是唯一的，我们也可以用以下两个产生式SaSSa还可以用文法SaSS,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,18,语言文法,例2.11 构造一个文法，使其能产生语言a，b*。w是由a和b以任意次序组成的串（包括空串），w是w的逆转，ww是由偶数个a，b组成且由中心开始左右对称的串，如abba，baaaab，aabaabaa等等。例2.12构造一个文法，使其能产生语言anbncn1。（不太容易）,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,19,文法等价,定义2.4对于两个不同的文法G1(V1，T1，P1，S1），G2(V2，T2，P2，S2)，如果(G1)(G2)，则称文法G1与G2等价。同一个语言可以由不同的文法产生。在例中已经看到，一个很简单的语言an|n1就可由三个不同的文法产生。文法是用四元组定义的，在两个四元组的各对应部分中，只要有一点点不同，就应当看作是不同的文法。如在一个已有的文法上，随意加上一些变元，一些终结符，或一些不影响S推导结果的产生式等等，都会变成新的文法。在这个意义下，任何一个语言都可以有无穷多个文法产生它。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,20,2.3 文法的乔姆斯基分类,定义 2.5 对于文法G（V，T，P，S）按以下方法分为四类：若中的产生式，不加另外的限制，则G称为0型文法，或短语结构文法（PSG）。若中每个产生式都满足条件|，则G称为1型文法，或上下文有关文法（CSG）。若中每个产生式都具有如下形式：A，(VT)*，AV，则称G为2型文法，或上下文无关文法（CFG）。若中每个产生式都具有如下形式：Aa或AaB，aT，A，BV，则称G为3型文法，或正则文法（RG）。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,21,文法的乔姆斯基分类,定义2.6 由短语结构文法产生的语言，称为短语结构语言，简记为PSL。由上下文有关文法产生的语言，称为上下文有关语言，简记为CSL。由上下文无关文法产生的语言，称为上下文无关语言，简记为CFL。由正则文法产生的语言，称为正则语言，简记为RL。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,22,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,23,右线性文法,定义2.9 对于文法G=(V,T,P,S),如果P中产生式都呈以下形式:AwAwB这里A,BV,wT*,则文法G称为右线性文法。类似地，如果P中产生式都呈AwABw形式，这里A,BV,wT*,则文法G称为左线性文法。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,24,右线性文法,定理2.2 任何由右线性文法产生的语言都能被正则文法产生。证明 设L是一个右线性文法G产生的语言，G=(V,T,P,S)。现在由G构造正则文法G=(V,T,P,S)，其中P的构造为:对于P中形如Aw的产生式,若w=a(aT)或w=,则已符合正则文法的要求，将它们直接放入P中。对于w=a1a2an(n2),则引入新变元A1,A2,An-1,并将以下一组产生式Aa1A1A1a2A2（*）An-1an加入P中。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,25,右线性文法,类似地，对于P中形如AwB的产生式，若w 2，则将它们直接放入P中。对于w=a1a2an(n2)，则引入新变元B1,B2,Bn-1，并将以下一组产生式 Aa1B1 B1a2B2（*）Bn-1anB加入P中。V中的变元就是出现在P中的全部变元。因为G中产生式的个数是有限的，所以新引入的变元的个数也是有限的，不管新老变元有多少个，我们可以假设它们的名字全不相同。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,26,右线性文法,下面来证明G与G等价(L(G)L(G)and L(G)L(G)?)一方面，设有S x（xT*）。如果在推导过程中没有使用Aa1a2an(n2)和Aa1a2anB(n2)形式的产生式，则自然也有S x。如果在推导过程中每使用一次产生式Aa1a2an(n2)，就连续使用P中以下一组产生式 Aa1A1 A1a2A2 An-1an来替代。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,27,右线性文法,如果在推导过程中每使用一次产生式Aa1a2anB(n2)，就连续使用P中以下一组产生式 Aa1B1 B1a2B2 Bn-1anB来替代。这样显然也有S x。因此，L(G)L(G)。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,28,右线性文法,另一方面，设有S x。如果在推导过程中使用了（*）组中的第一个新产生式Aa1A1，因为新引入的变元是成组出现的，而且与其它变元都不相同，则必须连续使用本组的其余各产生式才行。这样，这一组连续推导可以使用G中原来的一个产生式Aa1a2an(n2)用一次推导来代替。如果在G的推导过程中使用了（*）组中的第一个新产生式Aa1B1，则基于同样的理由，也必须连续使用本组的其余各产生式才行。那么，这一组连续推导可以使用G中原来的一个产生式Aa1a2anB(n2)用一次推导来代替，因此也有A x，这就是说L(G)L(G)。最后我们得出L(G)=L(G)。定理证完。定理2.3 任何由左线性文法产生的语言都能被如下的文法G=(V,T,P,S)产生：在G中的产生式仅为Aa和ABa两种形式，其中aT,A,BV。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,29,正则文法,定理 2.4 给出正则文法G=(V,T,P,S),且L(G)=L。则存在另一文法G=(V,T,P,S)，它的产生式仅为Aa和ABa两种形式，(其中aT,A,BV)，使得L(G)=LR。证明 我们由G构造G，其出发点是因为要让G能产生L的逆转集合LR，就必须把原来G中产生式的右部也都逆转过来，构成G中的产生式。具体来说，P的构造是：对于P中形如Aa的产生式(aT A,V)，则将它们全部放入P中。对于P中形如AaB的产生式(aT,A,BV),则将产生式ABa放入P中。因为G是正则文法,其产生式只有Aa和AaB两种形式,经用上述方法构造出来的G，在形式上已符合定理要求,现在要证L(G)=LR。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,30,正则文法,一方面,设x=a1a2anL(G)，要证xR=ana2a1L(G)。对于n1，在G中有直接推导S x，使用的产生式或为Sa1，或为S。这两种产生式也在G中，所以，在G中有直接推导S x，而且此时x=xR。对于n2，在G中要用一系列直接推导S a1B1（用产生式Sa1B1）a1a2B2（用产生式B1a2B2）a1a2an-1Bn-1（用产生式Bn-2an-1Bn-1）a1a2an-1an（用产生式Bn-1an）或者有 a1a2an-1Bn-1 a1a2an-1anBn（用产生式Bn-1anBn）a1a2an-1an（用产生式Bn）,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,31,正则文法,对应G中的产生式Sa1B1，G中有SB1a1，对应G中的产生式B1a2B2,G中有B1B2a2,对应G中的产生式Bn-2an-1Bn-1,G中有Bn-2Bn-1an-1,对应G中的产生式Bn-1anBn,G中有Bn-1Bnan。至于G中的产生式Bn-1an和Bn，G中也有同样的产生式。S B1a1（用产生式SB1a1）B2a2a1（用产生式B1B2a2）Bn-1an-1a2a1（用产生式Bn-2Bn-1an-1）anan-1a2a1（用产生式Bn-1an）或者有Bn-1an-1a2a1 Bnanan-1a2a1（用产生式Bn-1Bnan）anan-1a2a1（用产生式Bn）所以总起来有 S anan-1a2a1=xR，即xR L(G)。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,32,正则文法,另一方面，设x=a1a2anL(G),要证xR=ana2a1L(G)。对于n1，根据与前面同样的理由，结论显然成立。对于n2，在G中要用一系列直接推导 S B1an（用产生式SB1an）B2an-1an（用产生式B1B2an-1）Bn-1a2an-1an（用产生式Bn-2Bn-1a2）a1a2an-1an（用产生式Bn-1a1）或者有Bn-1a2an-1an Bna1a2an-1an（用产生式Bn-1Bna1）a1a2an-1an（用产生式Bn）,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,33,正则文法,G中产生式是G中产生式的唯一来源，因此，在G中也有一系列直接推导 S anB1（用产生式SanB1）anan-1B2（用产生式B1an-1B2）anan-1a2Bn-1（用产生式Bn-2a2Bn-1）anan-1a2a1（用产生式Bn-1a1）或者有anan-1a2Bn-1 anan-1a2a1Bn（用产生式Bn-1a1Bn）anan-1a2a1（用产生式Bn）这也就是 S anan-1a2a1=xR。即xR L(G)。总之，我们有L(G)=L(G)R。定理证完。,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,34,课后要求,习题：(P.40)2.3（使用数学归纳法对串长证明）2.4(1),(2),(3),(4)2.5,2023年10月31日星期二,南京航空航天大学计算机学院 胡军,