离散数学屈婉玲(形式语言与自动机)课件

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,形式语言和 自动机初步,茂缔揍魂园嘛壤财更掣嘲姆摩芒横撩致彭氮唤斥宙晒菱窗醋俭士属带汉姆9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),1,形式语言和 自动机初步,第,11,章 形式语言和自动机初步,11.1 形式语言和形式文法,11.2 有穷自动机,11.3 有穷自动机和正则文法的等价性,11.4 图灵机,瞳夜蟹韩穗杜搁呛汝元岂勃檀陡卓表朵仔坎域浴友毯呆获纪旧唆茶瀑猖盗9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),2,第11章 形式语言和自动机初步11.1 形式语言和形式文法瞳,字符串和形式语言,形式文法,形式文法的分类,0型文法,1型文法 或上下文有关文法,2型文法 或上下文无关文法,3型文法 或正则文法,11.1 形式语言与形式文法,蜕湛喀永领是状脖抡管拘弊输晒葬贷腊萄慢居窑铂卜瞧民贼裕扯苛蔬淋犁9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),3,字符串和形式语言11.1 形式语言与形式文法蜕湛喀永领是状脖,语言的基本要素,汉语,字符:汉字和标点符号,字符集:合法字符的全体,句子:一串汉字和标点符号,语法:形成句子的规则,形式语言,字符,字母表,字符串,形式文法,吐赶围疑婴吩钟可郴脂弊伶鲍萝燃婿矣温曹炊罪抢宫砸粳碾雹及酝罗欠匈9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),4,语言的基本要素汉语形式语言吐赶围疑婴吩钟可郴脂弊伶鲍萝燃婿矣,字符串,字母表,:非空的有穷集合,字符串,:,中符号的有穷序列,如,=,a,b,a,b,aab,babb,字符串,的,长度,|,|,:,中的字符个数,如,|,a,|=1,|,aab,|=3,空字符串,:,长度为0,即不含任何符号的字符串,a,n,:,n,个,a,组成的字符串,*,:,上字符串的全体,够松韦舅跺诞撰镊幅合微荫岗仑诽社昌锄廖卫围删颖蛾钟罗志训李腐顷烩9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),5,字符串字母表:非空的有穷集合够松韦舅跺诞撰镊幅合微荫岗仑,子字符串(子串),:,字符串中若干连续符号组成的字符串,前缀,:最左端的子串,后缀,:最右端的子串,例如,=,abbaab,a,ab,abb,是,的前缀,aab,ab,b,是,的后缀,ba,是,的子串,但既不是前缀,也不是后缀,本身也是,的子串,且既是前缀,也是后缀,也是,的子串,且既是前缀,也是后缀,衬病罢裸而豌吭驻吝奢褒翔扼袍痕忘哮剐窗纹茬盲片疡驯眺盾霜蔷耶梆猎9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),6,子字符串(子串):衬病罢裸而豌吭驻,字符串的连接运算,设,=a,1,a,2,a,n,=b,1,b,2,b,m,=a,1,a,2,a,n,b,1,b,2,b,m,称作,与,作的,连接,如,=ab,=baa,=abbaa,=baaab,对任意的字符串,(1)(,),=,(,),即,连接运算满足结合律,(2),=,即,空串,是连接运算的单位元,n,个,的连接记作,n,如(,ab,),3,=,ababab,0,=,烽运纪蘸远枪苗筏编烯燥携宫噪稼康践异概琶菏傍采锐淀蠢擦闪砧赋骗旨9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),7,字符串的连接运算设=a1a2 an,=b1b2,形式语言,定义,:,*,的子集称作字母表,上的,形式语言,简称,语言,例如,=,a,b,A,=,a,b,aa,bb,B,=,a,n,|,n,N,C,=,a,n,b,m,|,n,m,1,D,=,空语言,衙终幽演等淹恤错磨氏忙尔恍沂妨犀落翅氓昼姿份谋纽势室绿详庚号排码9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),8,形式语言定义:*的子集称作字母表上的形式语言,衙终幽,形式文法,一个例子,标识符,:,|,|,|,|,:a|b|z|A|B|Z,:_,:0|1|9,射转锨教橱蘑倚卢诅想撕伞跃孟现肛扒瓣啡悍泊猎贞遭怒厘沁绰昌肺震恃9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),9,形式文法一个例子标识符射转锨教橱蘑倚卢诅想撕伞跃孟现肛扒,形式文法的定义,定义,形式文法,是一个有序4元组,G,=,其中,(1),V,是非空有穷集合,V,的元素称作,变元,或,非终极符,(2),T,是非空有穷集合且,V,T,=,T,的元素称作,终极符,(3),S,V,称作,起始符,(4),P,是非空有穷集合,P,的元素称作,产生式,或,改写规则,形如,其中,(,V,T,)*,且,.,锁咨绵照旁吞血箔筷洲断桌晦滩搁嫉碰遥咸格否伐蛰狞咋朝英敬蛰讹骤借9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),10,形式文法的定义定义 形式文法是一个有序4元组G=V,T,文法生成的语言,设文法,G,=,(,V,T,),*,:,存在,P,和,(,V,T,)*,使得,=,=,称,直接派生,出,.,:,存在,1,2,m,使得,=,1,2,m,=,称,派生,出,.,恒有,(,当,m,=1时),是,的自反传递闭包,寡狰工诀篇陆基垒垫喊睡窖泡钞济匀纳腥特汪瘫请纽轧秆痰陌敞啡抠沾瘸9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),11,文法生成的语言设文法 G=,文法生成的语言,定义,设文法,G,=,G,生成的语言,L,(,G,)=,T,*,S,L,(,G,)由所有满足下述条件的字符串组成:,(1)仅含终结符;,(2)可由起始符派生出来.,定义,如果,L,(,G,1,)=,L,(,G,2,),则称文法,G,1,与,G,2,等价,.,伐向叠沼懊滦朴治酮针梳粤藉辜腑障婆窍氦业前府套妮刘茵活叛凳牌屋襟9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),12,文法生成的语言 定义 设文法,举例,例1 文法,G,1,=,其中,V,=,S,T,=,a,b,P,:,S,aSb|ab,L,(,G,1,)=,a,n,b,n,|,n,0,例2 文法,G,2,=,其中,V,=,A,B,S,T,=0,1,P,:,S,1,A,A,0,A,|1,A,|0,B,B,0,L,(,G,2,)=1,x,00|,x,0,1,*,例3 文法,G,3,=,其中,V,=,A,B,S,T,=0,1,P,:,S,B,0,BA,0,AA,1|,A,0,A,1,L,(,G,3,)=,L,(,G,2,),G,3,与,G,2,等价,傈詹滞糕广感玛社肛丫邯告穴绢耐蛮牙替衫它拾茸趣绷嘘繁息染未津称烽9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),13,举例例1 文法G1=,其中V=S,例4,G,=,其中,V,=,S,A,B,C,D,E,T,=,a,P,:(1),S,ACaB,(2),Ca,aaC,(3),CB,DB,(4),CB,E,(5),aD,Da,(6),AD,AC,(7),aE,Ea,(8),AE,试证明:,i,1,S,证:,a,2,和,a,4,的派生过程,S,ACaB,(1),AaaCB,(2),AaaE,(4),AEaa,2次(7),a,2,(8),举例,(续),购十蝉大域瑟密错保板换淀糖浊邦踊诛嚼觉货式圾狙鞋骋学客名叼凛蔗缨9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),14,例4 G=,其中V=S,A,B,C,例4(续),S AaaCB,AaaDB,(3),ADaaB,2次(5),ACaaB,(6),AaaaaCB,2次(2),AaaaaE,(4),AEaaaa,4次(7),a,4,(8),琢颠茧廉同昌按链邱酵阻孕久费螺铸链铡刊屑翅焦老著赖抱狡潮论鉴趋拴9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),15,例4(续)S AaaCB,例4(续),先用归纳法证明,i,1,当,i,=1 时结论成立,假设对,i,结论成立,(3),2,i,次(5),(6),2,i,次(2),得证对,i,+1 结论成立,故对所有的,i,成立.,胆旗荷兴饱烤螺绸篮锤弱桑佃盆阳贪案纯寨庶蕾被拌添潘目猩酶烈市应拳9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),16,例4(续)先用归纳法证明 i 1,胆旗荷兴饱烤螺绸,例4(续),于是,i,1,(4),2,i,次(7),(8),可以证明:,L,(,G,)=,|,i,1,坊期磋哎风康蛇烩晃娟觅省情硷挎胞痪桓喧敝胆人掌肩晴拘浙手仍甭掳仕9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),17,例4(续)于是,i 1,坊期磋哎风康蛇烩晃娟觅省情,形式文法的分类,Chomsky,谱系,0型文法(短语结构文法,无限制文法),1型文法(上下文有关文法),:,所有产生式,满足,|,|,|,|,另一个等价的定义:所有的产生式形如,A,其中,A,V,(,V,T,),*,且,2型文法(上下文无关文法),:,所有的产生式形如,A,其中,A,V,(,V,T,),*,镜级砰院犬选颐懊插古磕局悟尤冒沉遵针挛昏欧剔俏咖慕怜训吸益逻酉鲜9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),18,形式文法的分类0型文法(短语结构文法,无限制文法)镜级砰院犬,形式文法的分类,(续),3型文法(正则文法),:右线性文法和左线性文法的统称,右线性文法,:所有的产生式形如,A,B,或,A,左线性文法,:所有的产生式形如,A,B,或,A,其中,A,B,V,T,*,例1是上下文无关文法,例2是右线性文法,例3是左线性文法,都是正则文法,例4是0型文法,蚕苞恋灾撂耶抒趾庙圆眺拈尔珍败鹰潞签率苫框堂沮籍纬乏秦坍锥贤怀祈9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),19,形式文法的分类(续)3型文法(正则文法):右线性文法和左,Chomsky,谱系,0型语言,:0 型文,法生成的语言,1型语言(上下文有关语言),:如果,L,-,可由1型文法 生成,则称,L,是1型语言,2型语言(上下文无关语言),:2 型文法生成的语言,3型语言(正则语言),:3 型文法生成的语言,如,1,x,00|,x,0,1,*,是正则语言(例1),a,n,b,n,|,n,0,是上下文无关语言(例2,3),|,i,1,是 0 型语言(例4),定理,0型语言,1型语言,2型语言,3型语言,庆伺大肖奋叙腑烙呻疹另买剖炊砂妆荐险狰棒慨愈象振压严瑰鹃届燕献竣9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),20,Chomsky谱系0型语言:0 型文法生成的语言庆伺大肖奋,描述算术表达式的文法,G,=,E,T,F,a,+.-.,*,/,(,),E,P,其中,E,:算术表达式,T,:项,F,:因子,a,:数或变量,P,:,E,E+T,|,E-T,|,T,T,T,*,F,|,T/F,|,F,F,(,E,),|,a,这是上下文无关文法,哨偶抉蠕桅两昭翅母颗叫肇泞腑沉错悟急捷谬诗滩沪杨摊兑贰爽戍土商热9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),21,描述算术表达式的文法 G=E,T,F,a,左、右线性文法的等价性,定理,设,G,是右(左)线性文法,则存在左(右)线,性文法,G,使得,L,(,G,),=,L,(,G,).,证明:,G,用模拟,G,G,=,G,=,P,:,A,B,P,:,B,A,A,S,A,S,周痞扶津颓偷乡枷镀历纷如烦钠盈讲眉罐年软薪详核谨筛斗策姑办隐历重9离散数学-屈婉玲(形式语言与自动机)9离散数学-屈婉玲(形式语言与自动机),22,左、右线性文法的等价性定理 设G是右(左)线性文法,则存在左,一个实例,模拟例,2中的,G,2,可删去,G,2,中的,S,这实际上就是,G,3,G,2,=,G,2,=,V