形式语言与自动机 主讲：方 敏 西安电子科技大学

第三章 上下文无关文法 与下推自动机 目 录 3.1 推导树与二义性 3.2 上下文无关文法的改写 第三章 上下文无关文法 与下推自动机 目 录 3.1 推导树与二义性 3.2 上下文无关文法的改写 3.3 Chomsky范式和Greibach范式 3.4 CFL的泵引理 3.5 下推自动机 3.6 上下文无关文法与下推自动机 3.7 上下文无关语言的性质 3.8 CFG中的ε规则

上下文无关文法和它所描述的上下文无关语言，在定 义程序设计语言、语法分析、简化程序设计语言的翻译 等方面有重要的意义. 内容：1、上下文无关文法 　　　2、两个范式:Chomsky 范式,Greibach范式 　　　3、确定的下推自动机、非确定下推自动机(PA) (Pnshdown Antomator) 　　　4、对任何CFA都能找到一种具有特有形式的 等价的CFG (Context-Free Grammar) 与上下文无关文法相应的识别器是下推自动机. 确定的下推自动机对应于上下文无关语言的一个子集(大部分程序设计语言) 例如:程序设计语言中的数套结构,用CFG描述而ｒG不行 上一页 下一页 退 出

树中的一个枝结点A，有直接子孙ｘ1ｘ2…ｘK， 有产生式Aｘ1ｘ2…ｘK 定义：tree是CFG G＝(N,T,P,S)语法树,是有序树 3.1 推导树与二义性(语法树) 树中的一个枝结点A，有直接子孙ｘ1ｘ2…ｘK， 　　　有产生式Aｘ1ｘ2…ｘK 定义：tree是CFG　G＝(N,T,P,S)语法树,是有序树 l 树根：S l  枝结点是非终结符 l   叶子结点是终结符或ε l 枝特点A有直接子孙ｘ1ｘ2…ｘi,则Aｘ1ｘ2…ｘi 例：G＝(｛E｝，｛+，＊，i,（，）,｝，P，E) E E+E｜E＊E｜(E)｜i 句子：(α＊α＋α) * 定义：CFG　G＝(N，T，P，S)如果存在S ω G是有一棵叶子为ω的语法树 上一页 下一页 退 出

定义：CFG G是二义的  ω∈L(G)，有两T不同的最 左(右)推导 文法二义的语言二义表示字的文法均二义 3.2上下文无关文法的改写 不改变文法描述能力前提下改写文法满足一定要求. 改写目标：将CFG改写成某种标准形式. (1) 改写成Chomsky范式：产生式形式均为：文法二义的 上一页 下一页 退 出

CFG G＝(N,T,P,S) ,β,ω∈T*ｘ∈N∪T * * 当ｘ出现在S α×β ω,则ｘ有用符号 * * A BC｜α　　　A,B,C∈N　α∈T (2)Greibach范式 A  α　　　 ∈N*,α∈T 1、删除文法中的无用符号 (1)有用／无用符号  　 CFG　G＝(N,T,P,S)　,β,ω∈T*ｘ∈N∪T * * 当ｘ出现在S α×β ω,则ｘ有用符号 * * ｘ不出现在S α×β ω,则ｘ为无用符号 即： ①CFA　G中,A∈N,能否由A推导出某些终结符串； ②A是否能出现在由文法起始符号S推出的句型中 上一页 下一页 退 出

(2) 定 理1：已知：CFG G＝(N，T，P，S) L(G)≠φ，则必能找到一个等效G1，对G1的每个非终结符A * A ω,ω∈T*(证明有用非终结符可推出终结符串) 证明： 已知：G＝(N,T,P,S)　设：G1＝(N1,T1,P1,S) 　　  A∈N，　有A ω∈P　　则：A∈N1 如果：有A ｘ1ｘ2…ｘｎ∈P　ｘi∈VT∪N1(已放入 N1 中非终结符) 则Aｘ1ｘ2…ｘｎ ω(终结符串)　则A∈N1 G1的P1：是符号在N1∪T中的生成式。 证：A∈N如A ω，ω∈T*, 则A∈N1 经1步推导：有生成式A ω∈P 上一页 下一页 退 出

算法1:找出所有有用非终结符(能推出终结符的非终结符) 对已给G＝(N,T,P,S)  根据定义有A∈N1 *  设当推导步骤＜K，有A ω,A∈N1成立  * 当进行K步骤推导时， Aｘ1ｘ2…ｘｎ  * ω(ω1ω2…ωｎ) 其中ｘi ωi　　1≤i≤ｎ　ωi∈T*   而且它们都是少于K步推导出来的。 * ∴ｘi ∈N1 故Aｘ1ｘ2…ｘｎ　　　A∈N1 　 Aｘ1ｘ2…ｘｎ∈P 算法1:找出所有有用非终结符(能推出终结符的非终结符) 对已给G＝(N,T,P,S) 删无用非终结符,及相关产生式,得G1＝(N1,T,P1,S) 上一页 下一页 退 出

(2) N‘＝｛A｜A ω,ω∈T*｝, N’为非终结符集合 (3)如果N0≠N‘,则(4),否则N1＝N＇(有用非终结符) N’= N0∪｛A｜A  ,  ∈(T∪N0)*｝,转(3) 例：N＝｛S,A,B｝　T＝｛0,1｝ P＝｛S 0,A 1,B 0｝ (1)N0＝φ (2)N＇＝｛S，A，B　｝ (3)N0≠N＇∴N0＝N＇＝｛S 0，A 1，B 0｝ (4)N＇＝N0∪{ }＝N0 ∴有用非终结符集＝N0＝｛S，A，B｝ 上一页 下一页 退 出

定理2：CFG：G＝(N，T，P，S)则必可找到等效的 G1＝(N1，T1，P1，S) 对ｘ∈N1∪T1 * 存在 ，β∈(N1∪T1)*，有S    (证：从文法起始S能推出含X的句型) 证明： 构造G1：　　S∈N1 (1)若A∈N1且A  ∈P，则含中的非终结符是属 于N1，终结符∈T1。 (2)重复(1),直到再没有新的符号加入N1，T1为止 (3)P1={A |A ∈P,A∈N1,  ∈(N1∪T1)*｝ 由G1的构造可知: * * ＜1＞S ω与S ω等价,则G1与G等价 G G1 上一页 下一页 退 出

＜2＞ｘ∈(N1∪T1)它必出现在G1的 某个 * 句型中,即存 在ε∈(N1∪T1)*使得 Sω=αｘβ 删去。 G经过定理1和定理2后得出G1与G等价,并没有无用符号。 例：CFG G＝({S,A,B},{a},S,P) P={S AB|a,A a} 求一个与G等价的且没有无用符号的CFG。 解：删不能产生终结符的非终结符B.及S  AB. 得：G’=({S，A}，{a}, S, {S  a,A  a}) 删不可达非终结符A，及相应产生式A  a G’’=({s},{a}，s，{s  a}) 上一页 下一页 退 出

注：先删不能生成终结符的非终结符，再删不可达符号， 顺序不可颠倒。 2. CFG变换 上面讨论了CFG的化简，实际上也是CFG的一种变换。 CFG的变换：将一个CFG变换成另一个等价的CFG，其目的是希望通过变换，得到一个具有较好性质的CFG。 例如：chomsky范式和Greibach范式，就是两个具有很好性质的CFG。 (1)定义：ε产生式。可零化的非终结符。 设 CFG G＝(N,T,S,P).若Aε∈P,则称： * A  ε为ε产生式； 若A  ，则称A为G中可零化的非终结符号。 G 若P中无ε字产生式，或只有S ε，S不出现在任何产生式右部，则称G为无ε文法。 上一页 下一页 退 出

定理：CFG G＝(N,T,S,P),若L(G)≠Φ, L(G)≠{ε},则 存在一个没有无用符号，没有ε产生式的 证明：先构造一个与CFG G＝(N,T,S,P)等价，又没有ε产生式的CFG G”＝(N,T,S,P”)。为此，先找出G中所有的可零化的非终结符号。 设：V0={A| A ε,A ∈N} 可零化的非终结符号。 构造V0：   (1)若:A  ε∈P，则 A  V0 (2)若:A X1X2 …Xn∈P,且Xi∈V0(1≤i≤n),则 A∈V0 (3)重复(2)，直到没有新的非终结符加入V0为止， 现将P改造为P”： P1={A  ε|A  ε∈P} 上一页 下一页 退 出

P2={B β|B  Aβ∈P,A∈V0,  β≠ε}. 令P’’＝P- P1 +P2 从而，构造出G”＝(N,T,S,P’’) 显然，G”中没有ε产生式，如果G的某步推导中，用到 P中的产生式B Aβ(A∈V0 ,  β≠ε),而再以后的 每一步推导中，必须要用A ε的，那么再G’’相应推导 中，用P’’中的B β，而不必用Aε,推导照样进行,； 反之亦然，L(G’’)=L(G) 再对G”应用定理1，2，便得到CFG G’＝(N’,T’,S,P’), G’没有无用符号，且L(G’)= L(G’’)= L(G), 又P’  P’’，所以，G’也无ε产生式，可得 无ε字产生式及无用符号的文法G’。 上一页 下一页 退 出

例: CFG G1({S,A,B}，{a}，S, P1 ). P1 ={S  AB,A a，B ε}, CFG G2 =({S,A,B},{a，b}，s，P2) P2＝{S AB,A a|ε，B b} 求与G1 和G2 分别等价,且没有ε产生式的CFG G1’,G2’ 解：G1, V0={ B}， P1’={S AB，A  a, S A} 所以G1’=({S,A,B},{a}，S,P1’) G2，V0={ A} P2’={S AB，A  a, B b， S B } G2’=({S,A,B},{a，b}，S, P2’) 当S∈V0时,(即Sε),则P’’应加入以下生成式 S’ ε∣S, S’是一个新非终结符。 N1= N∪{ S’ }，则 ：G’ =( N1,T,S,P’’) 上一页 下一页 退 出

例：G =( N,T, P ,S)。N＝{S},T={a，b} P: S aSbS∣bSaS∣ε 求：无ε字生成式的等效文法G1 解：G1是有ε生成式的文法，除S  ε外，S出现在产生 式右边 V0={ S} P’ ={S  aSbS|abS|aSb|ab|bSaS|baS|bSa|ba} 因为 S∈V0， 所以P’ ={S  a S b S |abS|aSb|ab|bSaS |baS|bSa|ba,S’ |S } G’ =({S,S’},{a,b},P’,S’) 结论：含ε产生式的CFG G ，存在一个与G等效的无ε 产生的G1 。 上一页 下一页 退 出

当G是无ε产生式的CFG，但存在单产生式。可利用算法2构成一个无单产生式的等效方法G1。 (2) 单生成式 形如 A B, A,B∈N,则称为单生成式 当G是无ε产生式的CFG，但存在单产生式。可利用算法2构成一个无单产生式的等效方法G1。 算法2： ① 对任意 A∈N, * 构造一个非终结符集合任意NA＝{B∣AB} 1)  N1={A}. 2)  N’={C∣B C∈P且B∈N0}∪N0 3)  如果N’ ≠N0, 则N0＝N’,转2) 否则，NA＝N’ 上一页 下一页 退 出

如果B∈P且不是单产生式，则对于B∈NA中的所有 A，把A加入P1中， ③得G1＝( N1,T1, P1 ,S) 结论：对于每个单产生式得CFG G，存在一个等效的无单产生式的文法G1 。 例: G=({E,T,F},{+,*.(,),a}，p，E) E E+T∣T P: T T*F∣F F (E)∣a 解：G是无ε产生式文法，但有单生成式E  T,T  F ①N0＝{E} ②因为E T ∈P, F T ∈P,则N’＝{E,T,F}=NE ③同理：NT＝{T,F}，NF＝{F}， 上一页 下一页 退 出

构造P1,因为E E+T∈P，且不是单生成式，故P1有 E  E+T∣T*F∣(E) ∣a T T*F∣(E) ∣a 3.递归文法 + 定义:CFG G,如果存在A aAβ,A∈N,称G是递归的文法； + 如果存在AAβ,则称G是左递归文法， 如果存在AaA, 则称G是右递归文法， 如果存在AA, 则称G是循环文法。 上一页 下一页 退 出

定理:CFG G=(N,T,P,S)P中有A产生式,A A1∣A 2∣ …∣A m∣β1∣β2∣….∣βn∣,其中βi是第一个字符不再是非终结符A，可构成文法G1 ： G1 ＝(N∪{A’},T,P,S) P1 是P中A的产生式用以下两组产生式取代： Aβ1|β2|…|βn|β1A’|β2 A’∣…|βn A’ A’  1| 2|….|m| 1A’|2 A’|…| m A’ 其中A’是一个新非终结符，则有L(G1)=L(G) 证明：G中只有关于A的产生式被改变了，要证明G和G1等效，主要考虑G中A产生式产生的语言，和G1中AA’产生的语言之间的关系。 由G：A  A1|A2|….|A m|β1|β2|….|βm A  A ( 1| 2|….| m )|β1|β2|….|βm 上一页 下一页 退 出

 (β1∣β2∣….∣βn)(a1∣a2∣….∣am)* 由G1:Aβ1|β2|…|βn|β1 A’|β2 A’|….|βn A’ A A   A    … A  …   (β1∣β2∣….∣βn)a*)  (β1∣β2∣….∣βn)(a1∣a2∣….∣am)* 由G1:Aβ1|β2|…|βn|β1 A’|β2 A’|….|βn A’ A’1|2|…|m|1 A’ |2 A’ |…|m A’ 设：  = 1∣ 2∣….∣ m A’  | A, A’   A’   A’  …A’  … + A β1∣β2∣….∣βn(β1∣β2∣….∣βn)A’  β1∣β2∣….∣βn(β1∣β2∣….∣βn)  +  (β1∣β2∣….∣βn)(ε∣ +) 上一页 下一页 退 出

 (β1∣β2∣….∣βn)(1∣2∣…∣m)* 所以 L(G)=L(G1) 例：CFG G＝(N,T,P,S) N={S,A,B}, T={+,*,(,),a} S→S+A∣A 去掉左递归并不增加ε P: A→A*B∣B B→(S)∣a 解：S→S+A∣A A→A*B∣B S→A∣A S’ A→B∣B A’ S’→+A∣+AS’ A’→* B∣*B A’ G1=({ S,,A,B,A’,S’},{+,*,(,),a},P,S) 上一页 下一页 退 出

(1)将非终结符,按一定次序排序,N={A1,A2,A3,…Am} 置i＝1 S A∣A S’ S’  + A∣A S’ P1： A B∣B A’ A’  * B∣*B A’ B (S)∣a 消左递归(直接/间接左递归) (1)将非终结符,按一定次序排序,N={A1,A2,A3,…Am} 置i＝1 如果 Ai  是P的产生式，则的第一个符号应是终结符，或者是排列在Ai后边的一个非终结符AL(L>i) (2) Ai→Ai 1∣Ai 2∣…∣Ai n∣β1∣….∣βp 不存在第一个字符是Ak的βL(1≤L≤p)，则将Ai用以下产生式取代： 上一页 下一页 退 出

Ai β1∣β2∣…∣βp∣βi Ai’∣…∣βp Ai’ Ai’   1∣…∣ n∣ i Ai’∣…∣ n Ai’ Ai’是新非终结符，所有Ai’产生式的第一个符号或是终结符，或是排在Ai后的一个非终结符。 (3)如果i＝m，则G1已产生，否则：置i＝i+1，且j＝1； (4)用Aj  β1∣β2∣…∣βn取代Ai＝Aj 的每一个产生式得：Ai→β1  ∣…∣βn  至此,所有Aj产生式右边的第一个字符,或者是终结 符,或者是排在Ai后面的一个非终结符。Aj也是如此。 (5)如果j＝i－1,则转向(2),否则,置j＝i+1 转向(4) 该算法说明,  CFG ,都存在一个无左递归的等效文法。 例：CFG G=({ A1, A2, A3},{a，b}，P,A1)找出等效的无左递归文法。 上一页 下一页 退 出

A3 A3A1A3A2|a b A3 A2|A3 A1 A2’ A3A2|a b A2’ A3A2 ∣a A2∣A3 A3∣a P: A2A3 A1|A1 b A3A1 A2|A3 A3|a 解:A1不变, A1 A2 A3∣a A2 A3 A1∣A2 A3 b∣ab A2 A3 A1∣ab∣A3 A1A21 ∣ab A2’ A2’ A3 b∣A3 b A2’ A3 A2A3 A2∣a A2∣A3 A3∣a A3 A3A1A3A2|a b A3 A2|A3 A1 A2’ A3A2|a b A2’ A3A2 ∣a A2∣A3 A3∣a A3 abA3A2|abA2’A3A2|aA2|a∣abA3A2A3’∣ abA2’A3A2A3’|aA2A3’|aA3’ A3’ A1A3A2∣A1 A2’ A3 A2∣A3∣A1A3A2A3’∣A1 A2’ A3A2 A3’∣A3 A3’ 上一页 下一页 退 出

3.3 chomsky范式和Greibach范式 Chomsky范式(CNF文法) CFG G=(N,T,P,S) 若P的形式均是： A→BC 和A→a, A,B,C∈N,a∈T, 则G是chomsky范式文法。 若ε∈L(G),则s→ε是P的一个产生式，但s不能在任 何其他产生式的右边。 定理1：任何CFL L，都能由产生式是chomsky范式的CFG G产生，L(G)=L. 证明：CFG A→ , A∈N,  ∈(NUT)* (1).若产生式右边只有一个符号,如果是A→B单产生 式,则可找到一个等效文法,使之不含单产生式。 如果是形如A→a，a∈T，则属于范式的形式。 以下G＝(N,T,P,S)是不含单生成式的文法。 (2)当A→D1D2…Dn，n≥2，Di∈T，则引入新Bi∈N. 上一页 下一页 退 出

Bi Di属于CNF形式，如果Di∈N，则Di=Bi 则得，Gi=(N,T,P,S),产生式形为： A , AB1B2…Bn，n≥2 * * 如果有 β，则必有 β，故L(G)  L(G1) G G1 下面证: L(G1)=L(G)用推导的步数归纳证明。 * * 如果Aω,则Aω，A∈N, ω∈T* G1 G △当步数为1，是A→a ，G1是从G中得到这样产生式并 未作任何修改，故结果成立。 △假设步数＝k，结果成立。 * 对步数＝k＋1时，有A  ω，其第一步必是 G1 A B1B2…Bn,n≥2 且ω＝ω1ω2…ωn Biωi 1≤i≤n 上一页 下一页 退 出

若Bi∈N1- N,P1中只有一个产生式可供推导， 即Bi Di, Di∈T,即Di = ωi * 若Bi∈N ,则推导Bi ωi，其步数≤k * G1 * 由归纳假设，有Bi  ωi，因此，A ωi G G (3)对P1的每一个产生式A→B1B2…Bn,n≥3,做以下变换， AB1C1,C1B2C2, C2 B3C3,…Cn－2 Bn－1Bn, 构成文法G2＝(N2，T,P2,S) * * 若Aω，必有Aω，有L(G1)  L(G2) G1 G2 同理可证：L(G2)  L(G1) 上一页 下一页 退 出

例1． CFG G=({A,B,S},{a，b}，P，S) P: S Aab S B A A BBB A a B AS B b 找出与G等效的chomsky范式文法 解：SAab SaC 1 C1AB SCa C1 Caa C1 AB ABBB ABC2 C2BB CFG G’=({A,B,S,Ca ,C1,C2},{a，b}，P’，S) P’：SCaC1 SBA Caa Aa C1AB Bb ABC2 C2BB BAS 上一页 下一页 退 出

例：CFG G=({S,A,B},{a，b}，S,P) P: SbA∣a B AbAA∣as∣a BaBB∣bs∣b 求与G等价的CNF 解：因为G无无用符号、产生式和单生成式, 故可直接改写G SbA∣aB SC2A∣C1B C1 a C2 b AbAA∣as AC2AA∣C1S AC2D1 D1 A A 所以 A C2D1∣C1S∣a D1 AA 上一页 下一页 退 出

BaBB∣bs∣b BC1BB∣C2S∣b BC1D2 D2BB 所以 BC1D2∣C2S∣b D2BB G’=({S,A,B,C1,C2,D1,D2},{a,b},S,P’) P’={SC2A∣C1B, AC2D1∣C1S, BC1D2∣C2S, D1AA, D2BB, C1a, C2b, Aa, Bb} 定义：CFG G=(N,T,P,S) 如果：P＝{A a  ∣A∈N, a∈T,  ∈N*} ,称G为Greibach范式(记为GNF). 上一页 下一页 退 出

定理2：任何CFL L，都能由产生式是Greibach范式的 GFG G产生，使L(G)=L。 证明： 设：G=(N,T,P,S)是chomsky文法，N={ A1,A2,…An} （1）将P中从A1到An的产生式改写为：Ai→Ajβ 应当满足j＞i。 △假设产生式改为：1≤i≤k，满足j＞i，那么 Ai→Ajβ便是一个产生式。 △再改Ak＋1的产生式，如果Ak＋1→Ajβ是一个产生 式，j＜k＋1，则由消间接递归方法，将每个 Aj代入Ak＋1→Ajβ中的Aj。 至多重复k－1次，得：Ak＋1ALβ(L≥k＋1) 上一页 下一页 退 出

△再去到l＝k＋1的产生式，用消直接左递归的方法。 △对N中得每个非终结符，重复以上的过程，可以得到 Ak→ALβ L＞k Ak→aβ a∈T A’k→β β∈(N∪{ A1’, A2’,…, An’}* 即An是下标号最高的非终结符，An的候选的第一个字符 必须是终结符，An－1的候选的第一个字符是An或终结符， 如此处理An－2，An－3，…A的产生式，直到每一个产生式右 边的第一个字符均为终结符。 最后，对新非终结符Ai’，用A1…Ak代入,得起始为终结 符的符号串。 例：CFG G＝({A,B,C},{a，b}，P,A) P: A→BC B→CA∣b C→AB∣a 求与G等价的Greibach范式 上一页 下一页 退 出

解：A表序号最低,C表序号最高,(∵G已是Chomsky范式) A BC 改满Ak→ALβ k＜L B CA∣b C BCB∣a C CACB∣bCB∣a C bCB∣a∣ bCBC‘∣aC’ 已是GNF C’  ACB∣ACBC’ 将C代入B BbcBA|aA|bcBC’A|ac‘A|b 是GNF 将B代入A: AbcBAC|aAC|bcBC’AC|aC’AC|bC 是GNF 将A代入C’ C’bCBACCB|aACCB|bcBC’ACCB|aC’ACCB|bcBB| bcBACCBC’|aAccBC’|bcBC’ACCBC’|aC’ACCBC’|bccBC’ 上一页 下一页 退 出

例：GNF G=({A1,A2,A3},{a,b},A1,P); P={A1A2A3， A2A3A1∣b， A3A1A2∣a} 求与G等价的GNF 解：替换：A3A1A2 A3A2A3A2∣a 再代： A3A3A1A3A2∣bA3A2∣a A3bA3A2∣a∣bA3A2A3’∣aA3’ A3’ A1A3A2∣A1A3A2A2 进行回代：A3代入A2，A2代入A1 A2 bA3A2A1∣aA1∣bA3A2A3’A1∣aA3’A1∣b A1bA3A2A1A3∣aA1A3∣bA3A2A3’A1A3∣aA3’A1A3∣bA3 将A1代入A3’ 上一页 下一页 退 出

A3’bA3A2A1A3A3A2∣aA1A3A3A2∣bA3A2A3’A1A3A3A2| aA3’A1A3A3A2∣bA3A3A2∣bA3A2A1A3A3A2A3‘∣aA1A3 A3A2A3’∣bA3A2A3’A1A3A3A2A3’∣aA3’A1A3A3A2A3’∣bA3A3A2A3’ 上一页 下一页 退 出

CFL的泵引理给出了一个语言是CFL的必要条件， 因此，它提出了判断一个L不是CFL的方法。 CFL的泵引理： (1) 如果L是任一CFL,那么存在一个正整数N(与L有关)； (2) 如果z∈L且∣z∣≥N，那么存在u,v,w,x,y，使得 z＝uvwxy，且满足： i．∣ v x∣≥1 ii．∣vwx∣≤N iii．对每一个非负整数i，都有uviwxiy∈L 例：CNF G＝({A,B,C}{a，b}，A,P) P={A BC, B BA, C BA, A a, B b} (1)G的非终结符的个数为k＝3,得定理中的N＝23=8 (2)取z＝babbababba∈L(G),且∣z∣＝10＞8 上一页 下一页 退 出

Z的语法树,最长路有四条,长度＝5,取A v1 v2的路， 标记为B，验证v1 v2 满足定理中的i，ii，iii。 V1 推出的句子：z1＝babba V2 推出的句子：z2＝b 设：z3＝bab z4＝a ，则z1＝z3z2z4 且 ∣z3z4 ∣＝∣baba∣＝4＞1 上一页 下一页 退 出

由G的产生式组P可见:B  z3Bz4,即:B babBa * G G Z3 z4 以及：B  z 3iz3z4i i≥0 G * * 由G的产生式组P可见:B  z3Bz4,即:B babBa * G G Z3 z4 以及：B  z 3iz3z4i i≥0 G z＝uz3z2z4y 其中：u＝ε，y＝babba。 令：v＝z 3，ω＝z 2 ，x＝z4 则 z＝uvwxy，且满足i，ii，iii 例：求证：L={0n2∣n=1,2,…} 不是CFL 解：L的句子长度为完全平方数。 设：L是CFL，利用CFL的泵引理：存在N, z＝0n2∈L，且∣z∣≥N，令z＝uvwxy，有 (1)∣vx∣≥1 (2)∣vwx∣≤N； (3)uviwxiy∈L，i≥0 上一页 下一页 退 出

由(1)(2)可知：1≤∣vx∣≤N(∵ ∣w∣至少为1) 由(3)知：uv2wx2y∈L，取i＝2. N2≤N2+1≤∣uv2wx2y∣=∣uvwxy∣+∣vx∣ ≤N2+ N＜(N+1)2 得uv2wx2y的长度不是完全平方数，这与L的句子长为完全平方数矛盾。 ∴ L不是CFL (前面已经证明该L不是rL) 例：L={an,bn,cn∣n＝1，2…}，不是CFL. 解：设：L是CFL，根据CFL泵引理，存在N, z＝aNbNcN∈L，∣z∣≥N，令z＝uvwxy，有 (1)|vx|≥1，(2)|vwx|≤N，(3)uviwxiy∈L，i≥0 由(2)可知： 不能出现v中含字符a的同时，x中含字符c 上一页 下一页 退 出

∵ z＝aNbNcN, a,c和b的字符个数不变， v,x不能同取a，这样，a的个数与bc不变， v,x不能同取c，这样，c的个数与ab不变， v,x不能同取b，这样，b的个数与ac不变。 v,x不能取ab，bc，这样出现字符abc交错。 由(3)可知：uxwy∈L (即i＝0) ∵ z＝aNbNcN＝uvwxy，在z中去掉v,x，∣vx∣≥1，必在z中去掉字符，∵ a，b，c中任一字符，abc的个数 均不等于3。故L不是CFL. 例:L={ ambncmdn∣m,n=1,2…}不是CFL 解：在z中，不能v中含字符a的同时x中含c，或v中含b同 时x中含有d。 由(3)知：uwy∈L(i取0)。但从z＝aNbNcNdN＝ uvxxy中去掉v和x，由(1)知，必要从z中去掉一些字符，这样uwy中a与b或c与d的个数不相等。这与L定义相矛盾，故L不是CFL。 上一页 下一页 退 出

∑={ a1,a2,…am} 是输入字符的有限集合； Γ={ z1,z2,…zk} 是下推栈符号的有限集合， 称Γ为下推字母表或栈符号表。 3.5下推自动机(PA) 1.下推自动机的定义与模型 PA M＝(Q,∑,Γ,,q0,Z0,F) Q={ q0,q1,…,qn} 是有限状态集 ∑={ a1,a2,…am} 是输入字符的有限集合； Γ={ z1,z2,…zk} 是下推栈符号的有限集合， 称Γ为下推字母表或栈符号表。  ： Q×(∑ ∪{ε})× Γ →2QΓ* 即 是Q×(∑ ∪{ε})× Γ到QΓ*的所有子集 构成的一个映射，称为转换函数。 F Q 终态集 理解： (1)有限控制：根据,控制读入头读入或不读入字符，改变PA所处的状态以及下推栈的内容。 上一页 下一页 退 出

(2)下推栈称为栈，字是一个具有记忆功能的存贮装置。所谓记忆功能是指下推栈能记住已进栈的号及其先后次序。   (2)下推栈称为栈，字是一个具有记忆功能的存贮装置。所谓记忆功能是指下推栈能记住已进栈的号及其先后次序。 (3)PA M运行： 初态：下推栈的栈底z0，输入从左到右扫描， 处于初态q0。 (qi,aij,zik,)决定下一时刻M所处的状态：读入头指向下一输入字符或不动，以及用一个栈符号串代栈顶符号。 上一页 下一页 退 出

最终：有限控制处于一个终态，或下推栈中的符号被弹 出，这时称PA M识别或接收了这个输入符号串，在前 一种情况称M为终态PA；后一种情况，称M为空栈PA。 2.NPA(非确定下推自动机) NPA M=(Q,Σ, Γ,δ,q0，z0，F) δ: δ(q,a,z)＝{(p1,r1),(p2,r2)…, (pm,rm)} 其中，q，pi∈Q。ri∈Γ*,1≤i≤m，a∈∑U{ε} (1)当a∈∑时,状态q,输入字符a,栈顶符号为z的NPA M 时,下一时刻转入状态p1,p2,…pm中的某一 个,例pi,读入头右移一个字符a,并用ri代 替z,ri中字符号是由右至左依次进栈的. ri最左端处于栈顶，ri最右端处于栈底。 (2)当a＝时，除读入头不动，其他同a∈∑况一样。 (3)对某些z∈Q，a∊∑∪{} ,z∊Γ,若NPA M没有转换， 则记为δ(q,a,z)＝Φ 上一页 下一页 退 出

δ：δ(q，a,z)={(p,r)}或者δ(q， ，z)=Φ q,P∈Q,a∈Σ∪{ε}，z∈Γ， r∈Γ*。并满足： 3.DPA DPA M＝(Q,Σ,Γ,δ,q0,z0,F) δ：δ(q，a,z)={(p,r)}或者δ(q， ，z)=Φ q,P∈Q,a∈Σ∪{ε}，z∈Γ， r∈Γ*。并满足： （1）若：δ(q，a,z)＝ {(p,r)},其中p,q∈Q，a∈∑， z∈Γ， r∈Γ*，则δ(q，a,z)＝Φ， （2）若：δ(q，ε,z)={(p,r)},其中p,q∈Q,z∈Γ， r∈Γ*,则对于a∈Σ,δ(q，a,z)＝Φ,称为ε转换, 表示不考虑当前字符，也表示即使读完输入字符， 仍存在ε转换。 例如：当δ(q,a,z)= {(p,r)}时， △  (q，aω，z )┝ (p，ω ，ß) 输入 下推栈 M 如用┝* 表示┝的闭合，表经零次或多次移动。 △  (q，w,r)┝*(q‘，w’,r‘) 上一页 下一页 退 出

其中，q，q’∈Q，w, w’ ∈Σ*，r，r‘∈Γ* △ 规定：(q,w,r)表示输入字符串已被读完 被弹空。 DPA M的转换函数,保证在任一状况,M最多有一种移动。 3.DPA所识别的语言 PA接受语言L(M)的方式有两种：一是终态接受， 一是空栈接收， (1)以终至接收L(M) L(M)={ω|(q0, ω ,z0)┝*(q,ε, )且q∈F,a∈Γ*} (2)以空栈接收语言Lφ(M)： Lφ(M)＝{ω︳(q0,ω,ε0)┝*(q,ε,ε)且q∈Q， } 此时可认为终态集为空， 上一页 下一页 退 出

当一个语言被空栈DPA M识别，它的终至集合是什么无 关紧要，通常认为F=Q 例1: 构造一个DPA M，使L(M)={anbn︳n≥1} 解：DPA M＝(Q,T,Γ,δ,q0,z0,F) Q={q0,q1,q2}，T＝{a,b}, Γ ＝{ z0，a} F={ q0}, δ: δ(q0,a,z0)＝{q1,az0} δ(q1,a,a)＝{q1,aa} δ(q1,b,a)＝{q2,ε} δ(q2,b,a)＝{q2,ε} δ(q2,ε,z2)＝{q0,ε} 当输入ab时， 上一页 下一页 退 出

(q0,ab,z0)┝(q1,b,az0)┝(q2,ε,z0)┝(q0,ε,ε) 当输入aaabbb时， (q0,aaabbb,z0) ┝ (q1,abb,az0) ┝ (q1,bb,aaz0) ┝ (q2,b,az0) ┝ (q2,ε,z0) ┝ (q0,ε,ε) 由于q0∈F，所以ab，aabb可被DPA M接受， 从M的工作过程可以看出，它把输入得若干个a逐个压 入下推栈中，当开始输入第一个字符b后，就从下推栈中 弹出一个a，状态从q1，转向q2 在状态q2 ，每输入一个b，下推栈弹出一个a，如果输 入b的个数与a相同,状态便从q2转到了终态q0,而后停止。 ∴ L(M)={anbn︳n≥1} 或证：(q0,a,z0)┝ (q2,ε,az0) 上一页 下一页 退 出

i (q1,ai, az0) ┝ (q2,ε，a i+1z0) (q1,b,a i+1z0)┝ (q2,ε，a iz0) (q2,bi,a iz0) ┝ (q2,ε,z0)┝(q0，ε，ε) 2n+1 ∴ 有（q0,anbn,z0) ┝ (q0, ε, ε) 又：(q0，ε，z0) ┝ (q0，ε，ε) ∴ L(M)={anbn︳n＝0,1,2…} 上一页 下一页 退 出

例1. 设空栈DPA M＝(Q,Σ, Γ ,δ, q1, z0,Φ)，其中: Q={q1,q2},Σ＝{ 0,1,c}, Γ={z0,z1,z2}， δ： δ(q1，0，z0)＝{(q1，z1z0)} δ(q1，0，z1)＝{(q1，z1z1)} δ(q1，0，z2)＝{(q1，z1z2)} δ(q1，1，z0)＝{(q1，z2z0)} δ(q1，1，z1)＝{(q1，z2z1)} δ(q1，1，z2)＝{(q1，z2z2)} δ(q1，c，z0)＝{(q2，z0)} δ(q1，c，z1)＝{(q2，z1)} δ(q1，c，z2)＝{(q2，z2)} δ(q2，0，z1)＝{(q2，ε)} δ(q2，1，z2)＝{(q2，ε)} δ(q2，ε，z0)＝{(q2，ε)} 上一页 下一页 退 出

求证：N(M)={ωcω－1|ω∈{0,1}*}. 解：设：ω＝011 看M是如何识别： ωcω－1＝011c110 (q1,011c110，z0) ┝ (q1,11c110,z1z0) ┝ (q1,1c110,z2z1z0)┝(q1,c110,z2z2z1z0)┝ (q2,110,z2z2z1z0)┝(q2,10,z2z1z0) ┝ (q2,0，z1z0)┝ (q2,ε, z0)┝ (q2,ε,ε) 上一页 下一页 退 出

由于M是空栈DPA，上述移动结果表明M识别句子ωcω－1 (q，z)—表示下一时刻M所处的状态和栈顶符号且原栈 顶符号压入栈中，—表示没有转换。 (q,ε)—表示原栈顶符号被弹出,没有新的栈符号进栈。 4.NPA识别的语言 (1)设终态NPA M＝(Q,Σ, Γ ,δ, q0, z0，F) QΓ ∪{} 1 c  (q1,z0) (q1,z1) (q1,z2) (q2,z0) -- (q2,z1) (q2,z2) (q2,ε) 上一页 下一页 退 出

L(M)={ω|(q0,ω,z0)┝*(p,ε, r) ω∈∑*， 对于某个P∈F，对于某个r∈Γ* } (2)设空栈 NPA M＝(Q,Σ,Γ,δ, q0, z0，Φ)， 用N(M)表空栈 NPA M所识别的语言 N(M)={ω|(q0,ω,z0)┝*(p,ε,ε),ω∈∑*,P∈Q} 例:设空栈NPA M=({q1,q2},{0,1},{ z0,z1,z2},δ,q1,z0,Φ) 其中δ： (1)δ＝(q1,0,z0)＝{( q1,z1z0)} (2)δ＝(q1,0,z1)＝{( q1,z1z1),( q2,ε)} (3)δ＝(q1,0,z2)＝{( q1,z1z2)} (4)δ＝(q1,1,z0)＝{( q1,z2z0)} (5)δ＝(q1,1,z1)＝{( q1,z2z1)} (6)δ＝(q1,1,z2)＝{( q1,z2z2), ( q2，ε)} 上一页 下一页 退 出

(7) δ＝(q2,0,z1)＝{( q2,ε)} (8) δ＝(q2,1,z2)＝{( q2,ε)} 求证：N(M)={ω |ω∈{0,1}*} 解: 先从一个具体的句子开始,设ω＝001,ω=001100 (q1,001100,z0)┝(9)( q2,001100,ε) 失败 ↓(1) (2)-2 (10) (q1,01100,z1z0)┝ ( q2,1100,z0)┝ (q2,1100,ε)失败 ↓(2)-1 (q1,1100,z1z1z0) ↓(5) 上一页 下一页 退 出

(q2,00,z1z1z0) (q1,0,z1z2z2z1z1z0)┝(q2,ε,z2z2z1z1z0) ↓(7) ↓(2)～1 (6)～1 (q1,100,,z2z1z1z0)┝ (q1，00，z2z2z1z1z0) ↓(6)～2 ↓(3) (2)～2 (q2,00,z1z1z0) (q1,0,z1z2z2z1z1z0)┝(q2,ε,z2z2z1z1z0) ↓(7) ↓(2)～1 (q2,0,z1z0) (q1,ε,z1z1z2z2z1z1z0) 失败 ↓(7) (q2,ε,z0) ↓(10) (q2,ε,ε) 下面转入一般性的讨论 由下表知 上一页 下一页 退 出

① (2)，(6)表明在(q0，0ω,z1r)，(q1,1ω,z2r)时，M都有两种可能的移动(两种可能的选择)； (1)(9)表明：在(q0,0ω,z0)，(q1,1ω,z0)时，M也有两种可能的移动，如在识别句子：001100的开始所遇到的情况，只能取其一，这正是NPA的特征。 ② (1)(3)(4)(5)式及(2)(6)的第一种选择表明：在状态为q1时,栈顶符号为z0,z1,z2,输入字符为0或1时，下一时刻状态仍为q1,栈顶符号相应地为z1或z2,且把原栈顶 上一页 下一页 退 出

④ (7)(8)表明：在状态q2，栈顶符号为z1或z2，输入符号相应地为0或1时，才有转换，否则无转换， 符号压入栈内。 ③ (2)(6)两式作第二种选择表明：在状态q1，栈顶符号为z1或z2，输入字符相应地为0，1时，下一时刻状态为q2时，原栈顶符号被弹出，无新符号进栈。 ④ (7)(8)表明：在状态q2，栈顶符号为z1或z2，输入符号相应地为0或1时，才有转换，否则无转换， 有转换地时候,下一时刻仍为q2，原栈顶符号被弹出，无新的栈符号进栈。 ⑤ (9)(10)表明：不论状态为q1还是q2，只要输入串已输入完毕(为ε)，且下推栈中只剩开始符号z0，则M可以把z0弹出下推栈，使其变成空栈。 当输入ω时，用(1)～(6)而不用(9)，如果用(2)(6)都 作第一种选择,这时q1不变，输入字符为0或1,进栈符号 相应地为z1或z2，并不断地把上一时刻的栈顶符号压入栈 内，直到输入ω的最后一个字符为止； 上一页 下一页 退 出

当输入 的第一个字符时，由于它与ω最后一个字符 相同，这时必用到(2)或(6)，都作第二种选择，状态变 为q2不变，从下推栈中弹出栈顶符号,此后q2不变,继续向 栈外弹出栈顶符号。 当ω输入完毕，状态仍为q2，这时输入符号为ε，栈 内只剩下开始符号z0，用(10)把z0弹出，栈变空。 即：ω＝a1a2…an-1an ai∈{0,1},i=1,2,…n ω = a1a2…an-1ananan-1…a2 a1, (q1,a1a2…an-1ananan-1…a2 a1,z0)┝n (q1,anan-1a1a2…a2a1,zan+1zan-1+1…za2+1za1+1z0)┝n (q2,ε,z0 )┝(q2 ε,ε) 在这里只写出成功的移动序列，没有写出失败的移动序列。 上一页 下一页 退 出

DFA 与NFA等价，但对PA却没有类似的结论。 例：ω能被空栈NPA识别，但它不能被任何DPA所识别，表明DPA 与 NPA不等价。 当ω＝ε时，ω ＝ε，有 (q1,ε,z0 )┝(q2,ε,ε) ∴ N(M)={ωcω－1|ω∈{0.1}*} 同理可以证明上述包含关系反过来也对。 DFA 与NFA等价，但对PA却没有类似的结论。 例：ω能被空栈NPA识别，但它不能被任何DPA所识别，表明DPA 与 NPA不等价。 6.定理： 如果Lf是PA Mf以终态接受的语言，则必存在一个下推自动机 MΦ,以空栈接受的语言LΦ，使LΦ＝Lf。 证明：PA Mf＝(Q,T,Γ,δ,q0,z0，F) 构造PA MΦ: MΦ＝(Q∪{ qe, q1},T,Γ∪{z1},δ1, q1, z1,Φ) 上一页 下一页 退 出

当Mf进入终态时，让MΦ消除自己的栈，用qe消除栈， 用z1作MΦ的栈底符号，如果Mf栈空而未进入终态时，MΦ 也不会产生偶然地接受，因为MΦ的栈底符号Z1，只有在 qe状态才能消除它。 δ1定义： ①  δ1(q1,ε，z1)＝{(q0,z0z1)}, MΦ的第一个动作 是将z0z1 压入下推栈，同时进入Mf的起始状态，z1 为下推栈底符号。 ② q∈Q,a∈T∪{ε},z∈Γ,有δ1(q，a，z)包含 δ(q,a,z)的元素，使MΦ模拟Mf; ③q∈Q和z∈Γ∪{z1},有δ1(q,ε,z)含有(qe,ε) ④z∈Γ∪{z1}，有δ1(qe,ε,z)＝{(qe,ε)} 上一页 下一页 退 出

当Mf进入终态时，③④使MΦ能进入终态qe，清除自己 的栈而接受输入。 对于MΦ，当输入ω字符串时，存在格局： n (q1,ε,z)┝ (q0,ε,z0z1)┝ (q,ε,x1 x2…xkz1) MΦ MΦ ┝(q0,ε,x2x3…xk z1)┝ (q0,ε,ε) 当且仅当 MΦ n MΦ  (q0,ω,z0) ┝(q0,ε,x2x3…xk) Mf 其中q∈F，x1x2…xk ∈T* 所以有LΦ＝Lf 定理：如果LΦ＝PA MΦ，以空栈接受的语言，则必存在一个PA Mf,以终态接受Lf，使Lf ＝LΦ。 上一页 下一页 退 出

构造PA Mf=(Q∪{q0f,qf},T,Γ∪{z1},δf,q0f,z1,{qf}) 证明：PA MΦ=(Q,T,Γ,δ,q0,z0,Φ) 构造PA Mf=(Q∪{q0f,qf},T,Γ∪{z1},δf,q0f,z1,{qf}) ①δf(q0f,ε,z1)={(q0,z0z1)},使Mf进入MΦ的起始状态， Mf的栈底符号为Z1 ② q∈Q, a∈T∪{U}和z∈T，有 δf(q,a,z)=δ(q0，a, z)} 表示Mf模拟MΦ。 ③ q∈Q,有： δf(q,ε,z1)含有(qf,ε) 证明方法类似定理证明(同上) 3.6 上下文无关文法与下推自动机 CFG G识别语言：L(G)  PA M ,L(M)使：L(M)=L(G), 反之亦然。 上一页 下一页 退 出

定理1:设CFG G＝(N,T,P,S),产生语言L(G)，则存在一个空栈NPA M,以空栈接受语言：L(M),使LΦ(M)＝L(G) 证明：先设：εL,则存在一个GNF G＝(VN,VT,S,P)， 使L(G)=L, 由G构造空栈NPA M M＝({q0},VT,VN,δ,q0,S,Φ) δ： Γ z0 δ(q0,a,A)={(q0,r)|A→ar∈p,A∈VN,a∈VT,r∈VN*} 目的:要证明M能且仅能模拟G的最左推导，即： * * x∊VT+,Sx,成立的充必要条件是: (q0,x,S)┝ (q0,  ,  ) Lm ∵G为GNF,它的产生式均为Aar’,A∊VN,a∊VT,r’∊VN* G的每个句型为：xr，x∈VT+,r∈VN* 上一页 下一页 退 出

下面证明一个更广泛的命题：x∈VT+, r∈VN* * * S  xr  (q0,x，s)┝ (q0,ε，r) Lm 充要条件 * * S  xr  (q0,x，s)┝ (q0,ε，r) Lm 充要条件 上述命题分为两个小命题： * * ①   若Sxr，则(q0,x,s)┝ (q0,ε,r) * * ②   若(q0,x，s)┝ (q0,ε，r)，则S  xr。 (1)如果A→β∈p，则δ(q,ε,A)＝(q,β)， a∈T，δ(q,a，a)＝{(q, ε)} 证明①，对G的最左推导步数作归纳： 当推导步数i=1时, 1 1 命题变为:若Sxr,则(q0,x,s)┝*(q0,ε,r) 当S xr，则S→xr∈p，x∈VT ,r∈VN* 。 上一页 下一页 退 出

由δ的定义，就是：δ(q0,x，s)＝{(q0, r)} 即: (q0,x，s)┝ (q0,ε，r)，命题成立。 设当i=k-1，时命题1成立，即： k-1 * 若：S  xr，则有(q0,x，s)┝ (q0,ε，r) Lm 证明： K 当i＝k时，命题①成立，即证明：若：S  xr， * Lm 则(q0,x，s)┝ (q0,ε，r) k k-1 1 由 Sxr，得S x1AP  x1a r1p＝xr Aar1 其中：x＝x1a r=r1p x∈VT+ , A∈VN ，a∈VT。 p，r1∈VN*， A→ar1∈p 上一页 下一页 退 出

由A→ar1∈p 即(q0, a,A)┝(q0,ε，r1) 从而：(q0,x，s)┝*(q0,ε，r1P),r1P为非终结符， K-1 由假设：S x1AP 得(q0,x,s)┝*(q0,ε,AP) (q0,x1a,s)┝*(q0,a,AP) 即 (q0,x，s)┝*(q0,a，AP) 由A→ar1∈p 即(q0, a,A)┝(q0,ε，r1) 从而：(q0,x，s)┝*(q0,ε，r1P),r1P为非终结符， ∴ i＝k时，命题1成立。命题1得证。 ②对M的移动次数作归纳，证命题2， * 若(q0,x，s)┝*(q0,ε，r1), 则S xr 当移动次数i＝1时， 命题为： 1 (q0,x，s)┝(q0,ε，r) x∈VT , M 即:δ(q0,x，s)={(q0,r)}S xr,故i＝1成立。 上一页 下一页 退 出

即若(q0,x,s)┝ (q0,ε,r),则:S xr。 要证:i＝k时,命题2成立， K M * 设：x＝x1a,x1∈VT+,a∈VT M 由(q0,x，s)┝k(q0,ε，r) 存在A∈VN，P∈VN* M 使：(q0,x1a,s)┝k-1(q0,a，AP)┝1(q0,ε，r) M M 其中r=r1p，r1∊VN* , r1代替上一时刻的栈顶符号A的栈 符号串。输入a之前，M所处的状态和下推栈的内容不会 受a的影响，于是由： (q0,x1a,s)┝k-1 (q0,a，AP) 上一页 下一页 退 出

有(q0,x1,s)┝ (q0,ε，AP)，故：Sx1AP M k-1 * 有(q0,x1,s)┝ (q0,ε，AP)，故：Sx1AP M 而由(q0,a,AP)┝1(q0,ε,r1p),有δ(q0,a,A)={(q0,r1)} M * 1 ∴ A→a r1, ∴ S x1AP x1a r1p xr 即 i＝k时，命题2成立，故命题2成立得证。 综上所述，整个命题得证。 * 令 r＝ε, 对于x∈VT+ , S x *  (q0,x,s)┝M(q0, ε, ε) ∴当ε L时，L=L(G)=N(M)。 若ε∈L时，补充：δ(q0,ε,s)＝{( q0,ε)} 表ε∈N(M)，便证明：L=N(M)， 例：GNF G＝({S,A},{a,b},S,P)，其中 P={S→aAA,A→as|bs|a},求与G等价的NPA(空栈) 上一页 下一页 退 出

M=({q}，{ a,b },{ s, A},δ，q，S,Φ) δ: δ(q,a,s)＝{(q,AA)} 解：根据以上证明方法：设空栈NPA M=({q}，{ a,b },{ s, A},δ，q，S,Φ) δ: δ(q,a,s)＝{(q,AA)} δ(q,a,A)＝{(q,s),(q,ε)} δ(q,b,A)＝{(q,s)} 定理4：对于每个空栈NPA M，都存在一个CFG G使 L(G)=N(M) 证明：设空栈NPA M＝(Q,Σ,Γ,δ, q0, z0,Φ) 由M构造CFG G＝(VN, VT,S,P) 其中： VN＝{[ q,A,p]| q, p∈Q,A∈Γ}∪{S} VT＝∑ P定义为： ① q∈Q，令：S→[q0, z0, q] 是P的一个产生式。 上一页 下一页 退 出

➂ δ(q,a,A)={(q1,ε)} 令[q,A, q1] →a 是P的一个产生式,其中q,q1∈Q,a∈∑∪{ε},A∈T ➁δ(q,a,A)＝{(q1,A1A2…Am)} 其中q,q1∈Q，a∈∑∪{ε}，A1,A2,…Am∈Γ，对于每一组从Q中有放回取得的m个状态q2,q3…qm+1，令[q,A,qm+1]→a[q1,A1,q2] [q2,A2,q3]…[qm,Am,qm+1]是P的一个产生式。 ➂ δ(q,a,A)={(q1,ε)} 令[q,A, q1] →a 是P的一个产生式,其中q,q1∈Q,a∈∑∪{ε},A∈T CFG G的VN和P的定义遵循这样的原则：当M输入字符串x时，在G中句子x的最左推导恰是对M的模仿。 为证明:L(G)=N(M),只须证明:p,q∈Q,A∈Γ,x∈∑*, * 充要 * [q,A,p] x  (q,x,A)┝ (p,ε,ε) G M 例 空栈NPA M=({q0,q1},{0,1},{z,z0},δ,q0,z0,Φ) δ: δ(q0,0,z0)={(q0,zz0)} δ(q0,0,z)={(q0,zz)} δ(q0,1,z)={(q1,ε)} δ(q1,1,z)={(q1,ε)} 上一页 下一页 退 出

δ(q1,ε,z)={(q1,ε)} δ(q1,ε,z0)={(q1,ε)} 求一个与M等价的CFG G＝(VN,VT,S,P) 解：VN＝{s,[q0,z,q 0],[q0,z,q1],[q1,z,q0]*, [q1,z,q1],[q0,z0 ,q0] , [q0,z0,q1], [q1,z0,q0]*,[q1,z0,q1]} VT＝{0,1} P:应该从S的产生式开始，然后对已在产生式右端出 现的非终结符定义关于它们的产生式。 S→[q0,z0 ,q0]，S→[q0,z0 ,q1] 由：δ(q0,0,z0)={(q0,zz0)} 关于非终结符 [q0,z0 ,q0],[ q0,z0 ,q1]的产生式为： 上一页 下一页 退 出

由δ(q1,ε,z0)={( q1,ε)} [q1,z0 ,q1] →ε [q0,z0 ,q0] **→0[q0,z ,q0] [q0,z0 ,q0] [q0,z0 ,q0] **→0[q0,z ,q1] [q1,z0 ,q0] [q0,z0 ,q1] →0[q0,z ,q0] [q0,z0 ,q1] [q0,z0 ,q1] →0[q0,z ,q1] [q1,z0 ,q1] 由δ(q0,0,z)={( q0,zz)} [q0,z,q0]→0[q0,z ,q0] [ q0, z, q0] [q0,z,q0]→0[q0,z ,q1] [ q1, z, q0] [q0,z,q1]→0[q0,z ,q0] [ q0, z, q1] [q0,z,q1]→0[q0,z ,q1] [ q1, z, q1] 由δ(q0,1,z)={( q1,ε)} [q0,z,q1]→1 由δ(q1,ε,z0)={( q1,ε)} [q1,z0 ,q1] →ε 由δ(q1,ε,z)={( q1,ε)} [q1,z ,q1] →ε 由δ(q1,1,z)={( q1,ε)} [q1,z ,q1] →1 上一页 下一页 退 出

由于没有非终结符[q1,z ,q0]、[q1,z0 ,q0]的产生式， 所以在句型的推导过程中，使用含它们的产生式，都不 能推导出终结符号串； 由于非终结符号[q1,z ,q0]、[q0,z0 ,q0]的产生式含有 它们，所以这些相应产生式无用。去掉[q1,z ,q0]， [q1,z0 ,q0],[q0,z,q0],[q0,z0 ,q0]的产生式，不影响G产 生的语言。 ∴ G的P： S→[q0,z0 ,q1] [q0,z0 ,q1] →0[q0,z ,q1] [q1,z0 ,q1] [q0,z ,q1] →0[q0,z ,q1] [q1,z ,q1]|1 [q1,z ,q1] →1|ε [q1,z 0,q1] →ε 上一页 下一页 退 出

CFG G有一个具有 A1A2的非终结符A，1和2都 G 是非空行,则G称为自嵌套的。非终结符A也称自嵌套的。 3.7 上下文无关语言的性质 1.自嵌套特性 * CFG G有一个具有 A1A2的非终结符A，1和2都 G 是非空行,则G称为自嵌套的。非终结符A也称自嵌套的。 正是这种自嵌套特性产生形为uviwxiy的句子。 结论：非自嵌套CFG产生一个正规集。 即 当且仅当 CFL L是正规的 所有它的文法都是自嵌套的(逆反命题) 定理1，设G为一非自嵌套的CFG,则L(G)是正规集， 例：CFG G＝({ε},{a,b},p,s) p={s→asa, s→a, s→b, s→a, s→b} ∵s→asa ∴ G自嵌套，s是自嵌套。 产生一正规集，L(G)={(a|b)+} (自嵌套特性的文法CFG也可能产生一正规集) 上一页 下一页 退 出

自嵌套特性对CFG的产生式作为几点限制而不缩小可能 产生的语言数。 现在考虑CFG 的一个扩充： 含有关于A的A→ε产生式，空字产生式也叫ε规则。CFL允许有这样的产生式，具有ε产生式的CFG产生的语言始终是CFL 定理：若L是G=(VN,VT,P,S)产生的，P中每一个产生式的形式均为A→,A∈VN,∈(VN∪VT) * (也可为ε),则L 能由这样的一种文法产生，即每一个产生式或都为 A→ 形式，或者为S→ ε形式，此外S不出现在任何产生式的右边。 上一页 下一页 退 出

本章结束！ 应用： 在只有形为A→ε的CFG与不具有此形的那些CFG 之间，唯一的差别是：前者可能把ε作为L中的一 个字。对此，确能找到一个不具有ε产生式 (S→ε除外)的等价的上下文无关文法。 本章结束！ 上一页 下一页 退 出