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

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

第三章上下文无关文法与下推自动机目录 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∈N * 设当推导步骤＜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)找出等效的无左递归文法。上一页下一页退出

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* G 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 * G * 由归纳假设，有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) G 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CaC 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范式上一页下一页退出

例：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) (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)～ ↓(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 * 若：S  xr，则有(q0,x，s)┝ (q0,ε，r) Lm 证明： K 当i＝k时，命题①成立，即证明：若：S  xr， * Lm 则(q0,x，s)┝ (q0,ε，r) k k 由 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时，命题为： (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 * 有(q0,x1,s)┝ (q0,ε，AP)，故：Sx1AP M 而由(q0,a,AP)┝1(q0,ε,r1p),有δ(q0,a,A)={(q0,r1)} M * ∴ 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→ε除外)的等价的上下文无关文法。本章结束！上一页下一页退出

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

Similar presentations

Presentation on theme: "形式语言与自动机主讲：方敏西安电子科技大学."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

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

Similar presentations

Presentation on theme: "形式语言与自动机 主讲：方 敏 西安电子科技大学."— Presentation transcript:

Similar presentations

About project

反馈

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

Presentation on theme: "形式语言与自动机主讲：方敏西安电子科技大学."— Presentation transcript: