《形式语言与自动机》课件ch4.3.ppt
《《形式语言与自动机》课件ch4.3.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件ch4.3.ppt(9页珍藏版)》请在文库网上搜索。
1、1School of Computer Science,BUPT4.3 Chomsky范式和范式和Greibach范式范式nChomsky范式定义:n 2型文法型文法G(N,T,P,S),),若生成式形式都若生成式形式都是是ABC和和Aa,A、B、C N,a T,则G是是Chomsky范式。若范式。若 L(G),),则S是是P的一的一个生成式,但个生成式,但S不能在任何其它生成式的右不能在任何其它生成式的右边。n每个上下文无关文法都具有等效的每个上下文无关文法都具有等效的CNF(定理定理4.3.1)2School of Computer Science,BUPTCNF 的构成步骤的构成步骤1.
2、用算法用算法1、2、3、4消除消除生成式、无用符号、单生成式生成式、无用符号、单生成式2.对生成式对生成式AD1D2Dn n2 若若DiT,则引入新生成式则引入新生成式BiDi,Bi是新非终结符是新非终结符 若若DiN,则令则令BiDi,从而将原生成式变化为从而将原生成式变化为 AB1B2Bn n2 当当n2 时,再将其变为时,再将其变为 AB1C1,C1B2C2,C2B3C3,Cn1Bn1Bn Ci是新引入的非终结符。是新引入的非终结符。定理证明定理证明自学自学3School of Computer Science,BUPTCNF 的构成例的构成例 例例:设G(A,B,S,a,b,P,S)是
3、无是无、无循无循环、无无用符号、无无无用符号、无单生成式的文法。生成式的文法。P:SaAB BA ABBB a BAS b 求等效的求等效的CNF G1解解:SBASBA,AaAa,BAS,BbBAS,Bb已是已是CNFCNF 加入到加入到P P1 1中中对对SaABSaAB,将其变换为将其变换为SCSCa aC C1 1,C Ca aaa,C C1 1ABAB 将将ABBBABBB变换为变换为ABCABC2 2,C C2 2BBBB.4School of Computer Science,BUPTCNF 的构成例的构成例 例例:2 2型文法型文法G G(AA,B B,SS,aa,bb,P P
4、,S S)P:SbAaB AbAAaSa BaBBbSb P:SbAaB AbAAaSa BaBBbSb 求等效的求等效的CNFCNF解解:SCSCb bACACa aB B,增加增加C Cb bbb,C Ca aaa AC ACb bDCDCa aSaSa,增加增加DAADAA BC BCa aECECb bSbSb,增加增加EBBEBB5School of Computer Science,BUPTGreibachGreibach范式范式n Greibach范式(GNF)定义:n2型文法G(N,T,P,S),若生成式的形式都是Aa,AN,aT,N*,且G不含生成式,则称G为Greibach
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 ch4