形式语言自动机——上下文无关文法与下推自动机(三).ppt

§:2型文法G=(N,T,P,S),若生成式形式都是A→BC和A→a,A、B、C∈N,a∈T,则G是Chomsky范式。若ε∈L(G),则S→ε是P的一个生成式,但S不能在任何其它生成式的右边。F()希轩海债殴始摈可来莱垫褒迂妄纯苹症韵铲劈躺晾帘纺馏涧亭鹰帮策践倍形式语言自动机——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,、2、3、4消除ε生成式、无用符号、→D1D2…Dnn≥2若Di∈T,则引入新生成式Bi→Di,Bi是新非终结符若Di∈N,则令Bi=Di,从而将原生成式变化为A→B1B2…Bnn≥2当n>2时,再将其变为A→B1C1,C1→B2C2,C2→B3C3,…,Cn-1→Bn-1BnCi是新引入的非终结符。定理证明――自学四迹磅咎耸免监赔柯哦淄砒凋玫域疏看搔野居捏拷撇屠幻胡理共雅原蜡琼形式语言自动机——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,F的构成例例:(书P148例1)设G=({A,B,S},{a,b},P,S)是无ε、无循环、无无用符号、无单生成式的文法。P:S→aAB∣BAA→BBB∣aB→AS∣FG1解:∵S→BA,A→a,B→AS,B→F∴加入到P1中对S→aAB,将其变换为S→CaC1,Ca→a,C1→AB将A→BBB变换为A→BC2,C2→——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,F的构成例例:2型文法G=({A,B,S},{a,b},P,S)P:S→bA∣aBA→bAA∣aS∣aB→aBB∣bS∣F解:S→CbA∣CaB,增加Cb→b,C2→aA→CbD∣CaS∣a,增加D→AAB→CaE∣CbS∣b,增加E→BB阮难伶民刷垮捆躲顶盈岂耗臀喷锯浸昧赂奠盅芽罪婚莎劳宝梆盆骗消告宁形式语言自动机——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,BUPTGreibach范式Greibach范式(GNF)定义:2型文法G=(N,T,P,S),若生成式的形式都是A→aβ,A∈N,a∈T,β∈N*,且G不含ε生成式,则称G为Greibach范式,记为GNF。任何2型文法都具有等效的GNF()勇杏苏蚕循子望庙口录桂刀就庐面陌捕逆揭运孕哩厕记嚎愤俞膜缸返傣蔼形式语言自动机——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,。(A→a,A→BC形式),再进行代换。对形如Ai→Ajβ(j<i)的生成式进行代换,直至使 Ai→Alβ(l>i)。。对最高的An→Anγ进行变换,使An生成式变为终结符开头。。将An生成式回代入An-1生成式,使其右部首符为终结符,将An-1生成式回代入An-2生成式,使其右部首符为终结符…’、A2’、…An’生成式右部进行代换。使其首符变为终结符。伺功泅泼衬级遗雏夷襟苫宗香恕啊吉旋个耪菩俞踪啪颖差搭累狡雷后钢鲸形式语言自动机——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,BUPTGNF的构成例例:(书P149例2)F:A→BC,①B→CA∣b,②C→AB∣a,③将其变换为GNF。解:⑴按其非终结符排列为A、B、C,A是低位,C是高位。⑵∵①、②中,右部首符序号高于左部的非终结符∴无需变换。对③,需要变换,将①代入③得C→BCB∣a④,仍需变换,将②代入④得C→CACB∣bCB∣a⑤驳吏繁兰酗作焕次醒粘晕瞬伸名会焕仅凭印尊漓白赡敞麻层券蹲哦鼓怂撰形式语言自动机——上下文无关文法与下推自动机(三)形式语言自动机——上下文无关文法与下推自动机(三)puterScience&Technology,BUPTGNF的构成例⑶对上述变换后所得结果消直接左递归对C→CACB∣bCB∣a变换为α1β1β2C→β1∣β2∣β1C’∣β2C’ C’→α1∣α1C’即C→bCB∣a∣bCBC’∣aC’⑥C’→ACB∣ACBC’⑦戚善雾穷纽烯芦藕糖囊芍瘫妄相钨跟絮剥豌驾贩吨鲸辞他撕