形式语言与自动机--文法的一般理论.ppt
《形式语言与自动机--文法的一般理论.ppt》由会员分享,可在线阅读,更多相关《形式语言与自动机--文法的一般理论.ppt(34页珍藏版)》请在咨信网上搜索。
1、形式语言与自动机(Formal Languages and Automata)第二章 文法的一般理论南京航空航天大学南京航空航天大学计算机科学与技术学院计算机科学与技术学院 胡胡 军军2024/5/13 周一1.o2.1 问题的提出 o2.2 形式文法与形式语言 o2.3 文法的乔姆斯基分类2024/5/13 周一2.2.1 问题的提出o任何有意义的语言都不是任意字符串的集合,而是符合某些规则要求的字符串集合符合某些规则要求的字符串集合.n自然语言(英语,语法);n程序设计语言(C语言,文法);o文法(Grammar):用有限个规则描述无穷有限个规则描述无穷多字符串的集合n自然语言描述(如:英
2、语语法);n严格的形式规则描述(如:C语言文法、Pascal 语言文法)-形式文法,形式文法,形式语言形式语言2024/5/13 周一3.BNF(Backus-Naur Form)o例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|z2024/5/13 周一4.问题的提出o例2.2 根据例2.1中的各规则,下述的字符
3、串 WHILE x5 DO x:=(x+2)是一个合法的语句;因为:n整个符合的定义结构;nx5是的一种;nx:=(x+1)是的一种(从而也是的一种);2024/5/13 周一5.语法树(分析树,Parser Tree)2024/5/13 周一6.问题的提出o例2.3 用下述语法规则定义英语中的句子。thea applecatman eatssingsrunsthe apple runs 语法语法/语义语义ArticleArticle2024/5/13 周一7.2.2 形式文法与形式语言 o定义2.1 一个文法文法G是一个四元组 G=(V,T,P,S),其中:V:是变元变元(Variable,
4、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)。2024/5/13
5、周一8.文法表示方法的约定o凡有关文法的例子,都遵循下述的约定:大写拉丁字母A,B,C,D,E和S等等表示变元变元,除非另做说明,S表示开始符号。小写拉丁字母a,b,c,d,e,数字等等表示终结符终结符。小写拉丁字母u,v,w,x,y,z等等表示终结符串终结符串。小写希腊字母,等等表示变元和终结符共同组成变元和终结符共同组成的串的串。另外还约定,同一个文法中如果有若干个左部相同而右部不同的产生式,如:1,2,n则可以缩写为:1|2|n在上述约定下,写一个文法时,只写出它的产生式集合就可以了.2024/5/13 周一9.字符串的推导 与 归约o定义2.2 给出文法 G=(V,T,P,S),我们定
6、义两个字符串之间的一个关系关系“”:若=123,=13,并且2是P中的一个产生式,则有 ,此时称由直接推导直接推导出。根据第一章关于集合上关系的闭包的定义,我们也可将 扩充为 ,将 称为由推导推导出。o若有S ,则称为句型句型,当,则称为句子句子。o对应于推导,还有一个重要的概念,称为“归约归约”。其定义是:如果 是由到的推导,则反过来称归约到,记作 。2024/5/13 周一10.字符串的推导 与 规约o例2.7 对于例2.6中给出的文法G,我们有:S 0A1 00A11 000A111 000111o第一步直接推导用的是第(1)个产生式,第二步直接推导用的是第(2)个产生式,第三步直接推导
7、还是用第(2)个产生式,最后一步直接推导用的是第(3)个产生式。总起来我们也可以写为S 000111。在这个推导中,0A1,00A11,000A111,000111都是句型,而000111又是句子。o在今后写推导式子的时候,若所指的文法是明确无误的,则可将记号 或 中的G省略,只写 或 即可。另外,如果经过i步的直接推导到,就可写 。2024/5/13 周一11.形式文法与形式语言o定义2.3 给出文法 G=(V,T,P,S),它所产生的语言记作(G),由下述集合定义:L(G)=|S ,并且*。换句话说,文法G产生的语言(G),就是由由G中开始中开始符号符号S推导出来的全体终结符号串所构成的集
8、合推导出来的全体终结符号串所构成的集合,也就是句子的集合句子的集合。2024/5/13 周一12.文法 语言o例2.8 给出文法G,它有两个产生式:SaSbSab则该文法产生的语言(G)=an bnn1。o这是根据(G)的定义,考虑从S的推导,若先用G中第二个产生式,则S ab,就不能再往下推导了,此时相当于语言中1的情况。若从S出发,先用第一个产生式-1次,即S aSb aaSbb an-1S bn-1,最后再使用第二个产生式一次,得到S ab,这个推导对于任何1都是对的。再加上=1的情况,即可得到L(G)an bnn1。2024/5/13 周一13.文法语言o例2.9给出文法G,它的产生式
9、是:SaBbAAabAAaSBbaBBbS(G)是由相等个数a和b组成的(次序不限)所有串的集合,加以证明。为了证明最终的结论,要证明以下三个互相关联的命题。S ,当且仅当中包含相等个数的a和b。A ,当且仅当中a的个数比b的个数多1。B ,当且仅当中b的个数比a的个数多1。2024/5/13 周一14.文法语言下面我们用关于关于w长度的归纳法长度的归纳法(多重归纳法多重归纳法)来证明上述三个命题。归纳基础归纳基础w1。命题(2),(3)显然是对的,因为只能有A a,B b,用其他产生式时都将推导出长度大于1的串。对于命题(1),因为在w1这个大前提下,一方面不可能有S w,另一方面中也不可能
10、包含相等个数的a和b,即“当且仅当”的两个方面都是假的,故命题(1)自然成立。归纳步骤归纳步骤假设对于所有长度不超过k-1的串,命题(1),(2),(3)成立,现在要证当wk时(k2),命题(1),(2),(3)也成立。2024/5/13 周一15.文法语言o先证命题(先证命题(1)。o如果S ,那么推导的第一步必然是S aB或S bA。对于第一种情形,必然有aw1,且B w1,因为w1k1,则根据归纳法假设,它包含b的个数比a的个数多1(命题(2),因此包含a的个数与b的个数相等。o对于S bA的情形,证明完全类似。o反之,如果wk,且w包含相等个数的a和b,要证S w。考虑w的第一个符号只
11、有a或b两种情况,若是a,则waw1,且w1k1。由于w1中包含b的个数比a的个数多1,根据归纳法假设,必有B w1(命题(3)。此时使S的第一次直接推导为S aB,然后将B推导到1,最后得到S aw1w。o对于w以b开始的情况,可以完全类似地证明。o考虑再证明命题(2)和(3)。2024/5/13 周一16.语言文法o例2.10 给出语言 a1,找出产生它的文法。oa,aa,aaa,它是一个无限集。因此必须先产生出一个a来,我们首先用产生式Sa来实现。因为是无限集,必须用递归的方法,以一个a为基础,不断地添加一个a。即再用一个产生式SaS,与第一个产生式合起来,整个文法就是:SaSaSo当然
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 自动机 文法 一般 理论
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。