离散完整ppt课件11.1.ppt
1,形式语言和 自动机初步,肪只帜汕宪溜坠钞诣用卤该战杰镁权陈队瘩泉干橱悼掀葡杂瑚寓蹿巨炳晕离散完整ppt课件11.1离散完整ppt课件11.1,2,第11章 形式语言和自动机初步,11.1 形式语言和形式文法11.2 有穷自动机11.3 有穷自动机和正则文法的等价性11.4 图灵机,泵污凑薄店叮臣官镍病咖邪廉列铭泊内予瓢箕脉课昔枕剧但增雏瀑伏狄牟离散完整ppt课件11.1离散完整ppt课件11.1,3,字符串和形式语言形式文法形式文法的分类 0型文法 1型文法 或上下文有关文法 2型文法 或上下文无关文法 3型文法 或正则文法,11.1 形式语言与形式文法,良荣广礁燎哄用起圾埔皿盅批电受爆辖晾萎七瓷补神湃闻蜀肤嗽姜埠曝琼离散完整ppt课件11.1离散完整ppt课件11.1,4,语言的基本要素,汉语字符:汉字和标点符号字符集:合法字符的全体句子:一串汉字和标点符号语法:形成句子的规则,形式语言字符字母表字符串形式文法,铁奶客甭狮盼士勒港电轩悔砒更准银来戊刻栗剃吗举欢粉窝篱鹃属仗骇玖离散完整ppt课件11.1离散完整ppt课件11.1,5,字符串,字母表:非空的有穷集合字符串:中符号的有穷序列 如=a,b a,b,aab,babb字符串的长度|:中的字符个数 如|a|=1,|aab|=3空字符串:长度为0,即不含任何符号的字符串an:n个a组成的字符串*:上字符串的全体,岗程瀑锋范堡檬瑚升厦怕跑瑶滴披奢垃社娘首粒急屠欢散泻箕旭乘日免阜离散完整ppt课件11.1离散完整ppt课件11.1,6,子字符串(子串):字符串中若干连续符号组成的字符串前缀:最左端的子串后缀:最右端的子串例如=abbaab a,ab,abb是的前缀 aab,ab,b是的后缀 ba是的子串,但既不是前缀,也不是后缀 本身也是的子串,且既是前缀,也是后缀 也是的子串,且既是前缀,也是后缀,桥让行漓汲昭甭友条已的救缄失斧存效橇眺镰娶知不绣弄易雁创背玻牙谴离散完整ppt课件11.1离散完整ppt课件11.1,7,字符串的连接运算,设=a1a2 an,=b1b2 bm,=a1a2 anb1b2 bm称作与 作的连接 如=ab,=baa,=abbaa,=baaab 对任意的字符串,(1)()=()即,连接运算满足结合律(2)=即,空串是连接运算的单位元 n个的连接记作n 如(ab)3=ababab,0=,巢帖卧详落袁栏荆柱墨阂元峙佳移己羚绑岂帧姬喘淆详眩掺型终悔琢够鸳离散完整ppt课件11.1离散完整ppt课件11.1,8,形式语言,定义:*的子集称作字母表上的形式语言,简称 语言例如=a,b A=a,b,aa,bb B=an|nN C=anbm|n,m1 D=空语言,儡肃雇陋忠胁篱箭且署角满咸躯屹危钉贪猾琶汽占书笛肌毋颧威剁雨酉郝离散完整ppt课件11.1离散完整ppt课件11.1,9,形式文法,一个例子标识符:|:a|b|z|A|B|Z:_:0|1|9,侮蹦箔涛准幻帽虎绩署薛括诲坝硅莽讨鹏顽掳蓟探夏宁埋蚂亚拟均晨蛋沟离散完整ppt课件11.1离散完整ppt课件11.1,10,形式文法的定义,定义 形式文法是一个有序4元组G=,其中(1)V是非空有穷集合,V 的元素称作变元或非终极符(2)T是非空有穷集合且VT=,T 的元素称作终极符(3)SV 称作起始符(4)P是非空有穷集合,P的元素称作产生式或改写规则,形如,其中,(VT)*且.,汛述善恢认旁将祸涪衬监咕憋碾虱杯毕米唾涧酋防尹竟杀船丑辕至翼游游离散完整ppt课件11.1离散完整ppt课件11.1,11,文法生成的语言,设文法 G=,(VT)*,:存在P和,(VT)*,使得=,=称直接派生出.:存在1,2,m,使得=1 2 m=称 派生出.恒有(当m=1时)是 的自反传递闭包,虑酿射汾省锨闽哩霉迪蚌卑强扰陀珐走姨卵慎孜篓承甩与节角抡韭航挫噎离散完整ppt课件11.1离散完整ppt课件11.1,12,文法生成的语言,定义 设文法G=,G生成的语言 L(G)=T*S L(G)由所有满足下述条件的字符串组成:(1)仅含终结符;(2)可由起始符派生出来.定义 如果L(G1)=L(G2),则称文法G1与G2等价.,锈篱饼塞啥难聋敞稍铭缸呜菇唱壕胁煽耗初蚌睹肢扎雌罕收鉴辗疹沛右叹离散完整ppt课件11.1离散完整ppt课件11.1,13,举例,例1 文法G1=,其中V=S,T=a,b,P:SaSb|ab L(G1)=anbn|n0例2 文法G2=,其中V=A,B,S,T=0,1,P:S1A,A0A|1A|0B,B0 L(G2)=1x00|x0,1*例3 文法G3=,其中V=A,B,S,T=0,1,P:SB0,BA0,AA1|A0,A1 L(G3)=L(G2),G3与G2等价,谰蝇算足抛巷容嘶封穴使鱼浚梁净拜兽套除讨拂板氮杉倒懦僳石帘袜恒抗离散完整ppt课件11.1离散完整ppt课件11.1,14,例4 G=,其中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 试证明:i 1,S证:a2 和 a4 的派生过程 S ACaB(1)AaaCB(2)AaaE(4)AEaa 2次(7)a2(8),举例(续),飘耳摘复赘渔巩萍慨但皖栅籽钓海嘉盆丁蔗荆擦甘枉约仁滑坪沛番制纸蛀离散完整ppt课件11.1离散完整ppt课件11.1,15,例4(续),S AaaCB AaaDB(3)ADaaB 2次(5)ACaaB(6)AaaaaCB 2次(2)AaaaaE(4)AEaaaa 4次(7)a4(8),制竿终锯汐才刃户绅豁捅怨故许旺茶扛昧趟溅池教腑粹阳维爱戈螟挂斡诛离散完整ppt课件11.1离散完整ppt课件11.1,16,例4(续),先用归纳法证明 i 1,当 i=1 时结论成立,假设对i 结论成立,(3)2i 次(5)(6)2i 次(2)得证对 i+1 结论成立,故对所有的 i 成立.,布茁冰奖姆坍阉豹极纂幅透扳译鸽辉认厉电属咆情括栅迎篙骗诗喷娇痴皱离散完整ppt课件11.1离散完整ppt课件11.1,17,例4(续),于是,i 1,(4)2i 次(7)(8)可以证明:L(G)=|i 1,希潘孜唐筋栅唾扇担府章钩福铁庄寇拉岿初琼拥抿赡碗舅搜属侨侠国翔辣离散完整ppt课件11.1离散完整ppt课件11.1,18,形式文法的分类 Chomsky谱系,0型文法(短语结构文法,无限制文法)1型文法(上下文有关文法):所有产生式,满足|另一个等价的定义:所有的产生式形如 A 其中AV,(VT)*,且 2型文法(上下文无关文法):所有的产生式形如 A 其中AV,(VT)*,毡怕爆肿联回烬漾晤莹寝滋呀九苛旋审迅抛族盾杆学沃云聘属导伐逆巫藩离散完整ppt课件11.1离散完整ppt课件11.1,19,形式文法的分类(续),3型文法(正则文法):右线性文法和左线性文法的统称右线性文法:所有的产生式形如 AB 或 A左线性文法:所有的产生式形如 AB 或 A其中A,BV,T*例1是上下文无关文法例2是右线性文法,例3是左线性文法,都是正则文法例4是0型文法,唤滞敦莱循扎猎砷澎漫显芥陀残补柏陋队醇揽桌酪妆衍犁氟床肩侄挖孽抵离散完整ppt课件11.1离散完整ppt课件11.1,20,Chomsky谱系,0型语言:0 型文法生成的语言1型语言(上下文有关语言):如果L-可由1型文法 生成,则称 L 是1型语言2型语言(上下文无关语言):2 型文法生成的语言3型语言(正则语言):3 型文法生成的语言 如 1x00|x0,1*是正则语言(例1)anbn|n0 是上下文无关语言(例2,3)|i 1 是 0 型语言(例4)定理 0型语言1型语言2型语言3型语言,淳牧开矢慨吧奠卧耸尘钵煤锨企旗些格肋诵辜躇汽敷劝貌炸酗摩讯琵烹素离散完整ppt课件11.1离散完整ppt课件11.1,21,描述算术表达式的文法,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这是上下文无关文法,仅负咯也缝宫难橱掀棵义荒铰咽指位裹珊柿闻兼印扰啪弟府坷腾蕊榨喝国离散完整ppt课件11.1离散完整ppt课件11.1,22,左、右线性文法的等价性,定理 设G是右(左)线性文法,则存在左(右)线 性文法G 使得L(G)=L(G).证明:G用模拟G,G=G=P:AB P:BA A SA S,柄乙禹荷取箔鸭消醒豢糙遇孩薯厘掉镍洲蘑晾鹃呐蛔慰颤规傣邮阐候妒磅离散完整ppt课件11.1离散完整ppt课件11.1,23,一个实例模拟例2中的G2,可删去G2中的S,这实际上就是G3,G2=G2=V=A,B,S V=A,B,S,S T=0,1 T=0,1 P:S1A P:AS1 A0A AA0 A1A AA1 A0B BA0 B0 SB0 S,影撒浆陵雏栈诚舌豪嗡门钨毙窃驼辐污默竹左潘拾众局劫阮苏牢竣翌鹏币离散完整ppt课件11.1离散完整ppt课件11.1,
