07879离散数学-屈婉玲(形式语言与自动机)111.ppt

1,形式语言和自动机初步,2,第11章形式语言和自动机初步,11.1形式语言和形式文法11.2有穷自动机11.3有穷自动机和正则文法的等价性11.4图灵机,3,字符串和形式语言形式文法形式文法的分类0型文法1型文法或上下文有关文法2型文法或上下文无关文法3型文法或正则文法,11.1形式语言与形式文法,4,语言的基本要素,汉语字符:汉字和标点符号字符集:合法字符的全体句子:一串汉字和标点符号语法:形成句子的规则,形式语言字符字母表字符串形式文法,5,字符串,字母表:非空的有穷集合字符串:中符号的有穷序列如=a,ba,b,aab,babb字符串的长度|:中的字符个数如|a|=1,|aab|=3空字符串:长度为0,即不含任何符号的字符串an:n个a组成的字符串*:上字符串的全体,6,子字符串(子串):字符串中若干连续符号组成的字符串前缀:最左端的子串后缀:最右端的子串例如=abbaaba,ab,abb是的前缀aab,ab,b是的后缀ba是的子串,但既不是前缀,也不是后缀本身也是的子串,且既是前缀,也是后缀也是的子串,且既是前缀,也是后缀,7,字符串的连接运算,设=a1a2an,=b1b2bm,=a1a2anb1b2bm称作与作的连接如=ab,=baa,=abbaa,=baaab对任意的字符串,(1)()=()即,连接运算满足结合律(2)=即,空串是连接运算的单位元n个的连接记作n如(ab)3=ababab,0=,8,形式语言,定义:*的子集称作字母表上的形式语言,简称语言例如=a,bA=a,b,aa,bbB=an|nNC=anbm|n,m1D=空语言,9,形式文法,一个例子标识符:|:a|b|z|A|B|Z:_:0|1|9,10,形式文法的定义,定义形式文法是一个有序4元组G=,其中(1)V是非空有穷集合,V的元素称作变元或非终极符(2)T是非空有穷集合且VT=,T的元素称作终极符(3)SV称作起始符(4)P是非空有穷集合,P的元素称作产生式或改写规则,形如,其中,(VT)*且.,11,文法生成的语言,设文法G=,(VT)*,:存在P和,(VT)*,使得=,=称直接派生出.:存在1,2,m,使得=12m=称派生出.恒有(当m=1时)是的自反传递闭包,12,文法生成的语言,定义设文法G=,G生成的语言L(G)=T*SL(G)由所有满足下述条件的字符串组成:(1)仅含终结符;(2)可由起始符派生出来.定义如果L(G1)=L(G2),则称文法G1与G2等价.,13,举例,例1文法G1=,其中V=S,T=a,b,P:SaSb|abL(G1)=anbn|n0例2文法G2=,其中V=A,B,S,T=0,1,P:S1A,A0A|1A|0B,B0L(G2)=1x00|x0,1*例3文法G3=,其中V=A,B,S,T=0,1,P:SB0,BA0,AA1|A0,A1L(G3)=L(G2),G3与G2等价,14,例4G=,其中V=S,A,B,C,D,E,T=a,P:(1)SACaB(2)CaaaC(3)CBDB(4)CBE(5)aDDa(6)ADAC(7)aEEa(8)AE试证明:i1,S证:a2和a4的派生过程SACaB(1)AaaCB(2)AaaE(4)AEaa2次(7)a2(8),举例(续),15,例4(续),SAaaCBAaaDB(3)ADaaB2次(5)ACaaB(6)AaaaaCB2次(2)AaaaaE(4)AEaaaa4次(7)a4(8),16,例4(续),先用归纳法证明i1,当i=1时结论成立,假设对i结论成立,(3)2i次(5)(6)2i次(2)得证对i+1结论成立,故对所有的i成立.,17,例4(续),于是,i1,(4)2i次(7)(8)可以证明:L(G)=|i1,18,形式文法的分类Chomsky谱系,0型文法(短语结构文法,无限制文法)1型文法(上下文有关文法):所有产生式,满足|另一个等价的定义:所有的产生式形如A其中AV,(VT)*,且2型文法(上下文无关文法):所有的产生式形如A其中AV,(VT)*,19,形式文法的分类(续),3型文法(正则文法):右线性文法和左线性文法的统称右线性文法:所有的产生式形如AB或A左线性文法:所有的产生式形如AB或A其中A,BV,T*例1是上下文无关文法例2是右线性文法,例3是左线性文法,都是正则文法例4是0型文法,20,Chomsky谱系,0型语言:0型文法生成的语言1型语言(上下文有关语言):如果L-可由1型文法生成,则称L是1型语言2型语言(上下文无关语言):2型文法生成的语言3型语言(正则语言):3型文法生成的语言如1x00|x0,1*是正则语言(例1)anbn|n0是上下文无关语言(例2,3)|i1是0型语言(例4)定理0型语言1型语言2型语言3型语言,21,描述算术表达式的文法,G=E,T,F,a,+.-.*,/,(,),E,P其中E:算术表达式,T:项,F:因子,a:数或变量P:EE+T|E-T|TTT*F|T/F|FF(E)|a这是上下文无关文法,22,左、右线性文法的等价性,定理设G是右(左)线性文法,则存在左(右)线性文法G使得L(G)=L(G).证明:G用模拟G,G=G=P