有限自动机理论章下推自动机精品文稿.ppt

《有限自动机理论章下推自动机精品文稿.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论章下推自动机精品文稿.ppt（166页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、有限自动机理论章下推自动机第1页，本讲稿共166页 FA只能处理正则语言只能处理正则语言 正则文法生成无穷语言是由于正则文法生成无穷语言是由于 A-wA不需要记录不需要记录w的个数的个数第2页，本讲稿共166页 无关文法无关文法生成无穷语言生成无穷语言 A-A 需要记录需要记录和和之间的对应关系之间的对应关系 无法用无法用FA的有穷个状态来表示。的有穷个状态来表示。第3页，本讲稿共166页为为FA扩充一个扩充一个无限容量无限容量的的栈栈 用用栈栈的的内内容容和和FA的的状状态态结结合合起起来来就就可以表示可以表示无限存储。无限存储。这种模型就是下推自动机这种模型就是下推自动机PDA第4页，本讲

2、稿共166页 PDA作作为为形形式式系系统统最最早早于于1961年年出出现现在在 Oettinger 的论文中。的论文中。与与 上上 下下 文文 无无 关关 文文 法法 的的 等等 价价 性性 由由Chomsky于于1962年年发现发现。第5页，本讲稿共166页与与FA比较比较PDA具有一个栈存储器具有一个栈存储器有两个操作：有两个操作：入栈入栈-将内容压入栈中将内容压入栈中 出栈出栈-将栈顶元素移出将栈顶元素移出第6页，本讲稿共166页下推自动机下推自动机物理模型物理模型a1a2a3aj anan+1FSC存储带存储带栈存储器栈存储器第7页，本讲稿共166页栈存储器栈存储器 存放存放不同于不

3、同于字母的符号字母的符号 只能对只能对栈顶栈顶元素进行操作。元素进行操作。第8页，本讲稿共166页下推自动机动作下推自动机动作 根据 FSC当前的当前的状态状态 输入带上的当前输入带上的当前字符字符 栈顶符号栈顶符号 进行进行状态改变状态改变和入栈或出栈和入栈或出栈操操作作 将读头向右将读头向右移动移动一个单元一个单元第9页，本讲稿共166页5.1.1 确定的下推自动机确定的下推自动机 例例5-1 语言语言 L=w|w(a,b)*，且，且a、b个数相等个数相等 暂时不考虑状态暂时不考虑状态 (或或PDA仅有一个状态仅有一个状态)第10页，本讲稿共166页初始初始栈为空栈为空从左到右逐个扫描串从

4、左到右逐个扫描串w(a，b)*第11页，本讲稿共166页入栈若栈为若栈为空空,当前符号是当前符号是a,则则A入栈入栈若栈为若栈为空空,当前符号是当前符号是b,则则B入栈入栈若栈顶为若栈顶为A,当前符号是当前符号是a,则则A入栈入栈若栈顶为若栈顶为B,当前符号是当前符号是b,则则B入栈入栈第12页，本讲稿共166页出栈若栈顶为若栈顶为A,当前符号是当前符号是b，则，则A出栈出栈若栈顶为若栈顶为B,当前符号是当前符号是a，则，则B出栈出栈第13页，本讲稿共166页若串若串w有相同个数的有相同个数的a和和b 当且仅当当且仅当 w扫描结束后，扫描结束后，栈为空栈为空。第14页，本讲稿共166页注意注意

5、PDA在在两种情况下停机两种情况下停机：串扫描结束串扫描结束 没有对应的规则没有对应的规则第15页，本讲稿共166页串扫描结束栈如果为空栈如果为空 就接收扫描过的串。就接收扫描过的串。第16页，本讲稿共166页对于非正式的对于非正式的算法算法，用用形式化形式化的方式进行描述：的方式进行描述：第17页，本讲稿共166页特殊的符号特殊的符号Z0表示栈底表示栈底 初始化时先压入栈初始化时先压入栈第18页，本讲稿共166页规则规则(指令指令)若若x是是w的当前符号的当前符号 D是栈顶符号是栈顶符号则用符号串则用符号串V代替代替D即将即将D弹出栈，而将串弹出栈，而将串V压入栈压入栈第19页，本讲稿共16

6、6页具体若若x是是w的的当当前前符符号号，栈栈顶顶符符号号为为D 将将D弹出栈弹出栈 将将A压入栈，成为新的栈顶压入栈，成为新的栈顶第20页，本讲稿共166页一般地一般地若若x是是w的的当当前前符符号号，栈栈顶顶符符号号为为D 表示：表示：将将D弹出栈弹出栈 将串将串A1A2 Ak压入栈压入栈(A1为新栈顶为新栈顶)第21页，本讲稿共166页例例5-1 算法的算法的形式化描述形式化描述第22页，本讲稿共166页规则规则 表示将表示将w扫描结束后，扫描结束后，将栈置成空将栈置成空也表示该也表示该PDA可以接收可以接收空串空串第23页，本讲稿共166页思考：如何接收语言如何接收语言 L=w|w(a

7、,b)+,且且a和和b个数相等个数相等?第24页，本讲稿共166页例：语言L=anbn|n0定义：定义：第25页，本讲稿共166页则还可以接收语言则还可以接收语言 (ab)n|n0，或，或 ambm(ab)n|m0,n0 等语言。等语言。第26页，本讲稿共166页思考：如何接收语言 L=anbn|n0 L=anbn|n0 L=(ab)n|n0 L=(ab)n|n0第27页，本讲稿共166页例5-2 L=wcwT|w(a，b)*识别语言识别语言第28页，本讲稿共166页思想：将将w的各个字符压入栈后的各个字符压入栈后 栈中的内容从栈中的内容从栈顶到栈底栈顶到栈底的顺序的顺序 刚好是刚好是wT的顺

8、序的顺序第29页，本讲稿共166页为了为了区别区别压栈和出栈动作压栈和出栈动作 增加两个增加两个状态状态-read 和和match PDA处于处于read状态时，状态时，处理整个串的前半部分，将对应的处理整个串的前半部分，将对应的符号压符号压入栈入栈第30页，本讲稿共166页扫描到字母扫描到字母c时时 PDA的状态转为的状态转为match开始处理整个串的后半部分，将栈开始处理整个串的后半部分，将栈中的内容中的内容出栈出栈。第31页，本讲稿共166页规则规则 若若PDA处于状态处于状态q w的当前字母是的当前字母是x 当前栈顶符号为当前栈顶符号为D则自动机的状态改变为则自动机的状态改变为q并用符

9、号串并用符号串V代替代替D第32页，本讲稿共166页（在本例中）用（在本例中）用Z代表任意的栈顶符号代表任意的栈顶符号 规则规则read，a，Z，read，AZ可以表示以下可以表示以下3条规则：条规则：read，a，Z0，read，AZ0read，a，A，read，AAread，a，B，read，AB第33页，本讲稿共166页用下列的规则来描述用下列的规则来描述PDAread，a，Z，read，AZread，b，Z，read，BZread，c，Z，match，Zmatch，a，A，match，match，b，B，match，match，Z0，match，第34页，本讲稿共166页若串若串w是该

10、语言的合法的串是该语言的合法的串 当且仅当当且仅当 w扫描结束后，扫描结束后，栈为空栈为空。第35页，本讲稿共166页Z0符号栈符号栈串串abbcbba的处理过程的处理过程ABreadmatch=B第36页，本讲稿共166页扫描到扫描到字母字母c 栈栈内内的的内内容容（从从栈栈顶顶到到栈栈底底）是是扫扫描描过的串的逆过的串的逆 与未扫描过的串的顺序相同与未扫描过的串的顺序相同此时，不作出栈和入栈操作，此时，不作出栈和入栈操作，仅仅把仅仅把PDA的的状态从状态从read改变到改变到match。第37页，本讲稿共166页接收语言接收语言L=anbn|n0q0，a，Z0，q0，AZ0q0，a，A，q

11、0，AAq0，b，A，q1，q1，b，A，q1，q1，Z0，q1，第38页，本讲稿共166页5.1.2 不确定的下推自动机不确定的下推自动机例例5-3 语言语言L=wwT|w(a,b)*第39页，本讲稿共166页 没有中心点字符没有中心点字符 在在扫扫描描过过程程中中，就就没没有有确确定定的的位位置置进进行状态的变换行状态的变换 具有具有不确定不确定性。性。第40页，本讲稿共166页使用规则使用规则read，Z，match，Z 来代替来代替read，c，Z，match，Z即即在在read状状态态时时，可可随随时时改改变变为为match状状态态（栈的内容和扫描符号不变）（栈的内容和扫描符号不变）

12、第41页，本讲稿共166页read，a，Z，read，AZread，b，Z，read，BZread，Z，match，Zmatch，a，A，match，match，b，B，match，match，Z0，match，第42页，本讲稿共166页该该PDA是是不确定不确定的的 处于状态处于状态read状态时状态时 随时随时都可以进行选择都可以进行选择:继续扫描，或状态变换为继续扫描，或状态变换为match第43页，本讲稿共166页一个串一个串w能够由能够由PDA所识别：所识别：仅当串是仅当串是wwT的形式的形式且且PDA状态在状态在中心点中心点进行了变换进行了变换第44页，本讲稿共166页对于不确定的

13、对于不确定的PDA和串和串w 若存在至少一个可能的扫描过程若存在至少一个可能的扫描过程 使得当串使得当串w扫描结束时，栈为空扫描结束时，栈为空 则称串则称串w能够被能够被PDA所所识别识别。第45页，本讲稿共166页接收语言接收语言L=(ab)n|n0q1，a，Z0，q2，AZ0q2，b，A，q1，q1，Z0，q1，第46页，本讲稿共166页接收语言接收语言L=(ab)n|n0q0，a，Z0，q0，AZ0q0，b，A，q1，q1，a，Z0，q2，AZ0q2，b，A，q1，q1，Z0，q1，第47页，本讲稿共166页定义5-1下推自动机下推自动机PDA是一个七元式：是一个七元式：M=(Q，q0，

14、Z0，F)Q是一个有限状态的集合是一个有限状态的集合 是输入串的字母集合是输入串的字母集合 是栈内符号集合是栈内符号集合第48页，本讲稿共166页q0Q是开始状态是开始状态Z0是栈底符号是栈底符号F Q是接收状态集合是接收状态集合第49页，本讲稿共166页：Q()Q*对于确定的对于确定的PDA，有，有 （q，x，D）=(q，V)对于不确定的对于不确定的PDA，有，有 (q，V)（q，x，D）第50页，本讲稿共166页一般一般使用使用 表示表示函数函数第51页，本讲稿共166页定义定义5-2 PDA格局格局(或瞬间描述或瞬间描述ID)格局代表某个时刻格局代表某个时刻PDA的情况的情况 PDA的格

15、局是一个三元式的格局是一个三元式 (q，w，)其中，其中，q为状态为状态第52页，本讲稿共166页w=x1x2xn 还没有被扫描到的串还没有被扫描到的串(将扫描将扫描x1)=Z1Z2Zm 栈的内容栈的内容(Z1在栈顶在栈顶，Zm在栈底在栈底)第53页，本讲稿共166页PDA初始格局为初始格局为 (q0，w，Z0)接收格局为接收格局为 (q，)其中其中:qQ（与接收状态无关）（与接收状态无关）第54页，本讲稿共166页格局的转换是格局的转换是 由于状态转换函数的作用引起的由于状态转换函数的作用引起的第55页，本讲稿共166页确定的确定的PDA 引起的格局转换为：引起的格局转换为：(q，xw，A)

16、=(q1，w，A1A2 Ak)第56页，本讲稿共166页不确定的不确定的PDA （情况（情况1）则则(q,xw,A)=(q1，w,A1A2 Ak)则则(q,xw,A)=(q2，xw，B1B 2Bj)第57页，本讲稿共166页不确定的不确定的PDA （情况（情况2）则则(q,xw,A)=(q1，w，A1A2 Ak)则则(q,xw,A)=(q2，w，B1B 2Bj)第58页，本讲稿共166页用用=*代表格局的任意次变换代表格局的任意次变换第59页，本讲稿共166页 不不确确定定PDA对对于于某某一一格格局局可可能能会会有不同的下一格局。有不同的下一格局。第60页，本讲稿共166页5.1.3 PDA

17、接收语言的两种方式接收语言的两种方式定定义义5-3 PAD以以空空栈栈方方式式接接收收的的语语言言为为L(M），且），且 L(M)=w|(q0，w，Z0)=*(q,)qQ第61页，本讲稿共166页接收格局与接收状态无关接收格局与接收状态无关 只要当只要当串串w扫描结束扫描结束，而，而栈为空栈为空则串则串w被被PDA以以空栈方式空栈方式所接收。所接收。第62页，本讲稿共166页定义5-4PAD以以终终态态方方式式接接收收的的语语言言为为F(M)，且且 F(M)=w|(q0,w，Z0)=*(q,)qF,*第63页，本讲稿共166页接收格局与栈是否为空无关接收格局与栈是否为空无关只只要要当当串串w扫

18、扫描描结结束束，而而PDA处处于于某某个个接收状态接收状态则串则串w被被PDA以终态方式以终态方式所接收。所接收。第64页，本讲稿共166页定理5-1语言语言L被被PDA以终态方式以终态方式所接收所接收 当且仅当当且仅当 它被它被PDA以以空栈方式空栈方式所接收。所接收。即终态接收与空栈接收方式等价。即终态接收与空栈接收方式等价。第65页，本讲稿共166页证明：证明：l略略第66页，本讲稿共166页5.1.4广义广义PDA和单态和单态PDA定义定义5-5 广义的广义的PDA是七元式是七元式 PDA=(Q,，q0，Z0，F)（除了（除了外，其余同一般的外，其余同一般的PDA）其中其中第67页，本

19、讲稿共166页Q是一个有限状态的集合是一个有限状态的集合是输入串的字母集合是输入串的字母集合是栈内符号集合是栈内符号集合q0Q是开始状态是开始状态Z0是初始的栈底符号是初始的栈底符号F Q是接收状态是接收状态(终止状态终止状态)集合集合第68页，本讲稿共166页：Q()+Q*(q，x，B1 B2 Bk)=(q，C1 C2 Cn)一般形式为一般形式为 第69页，本讲稿共166页一般的一般的PDA，栈顶只是一个符号，栈顶只是一个符号广义广义PDA的的栈顶栈顶可以为可以为多个符号多个符号。第70页，本讲稿共166页定理5-4若语言若语言L能由广义能由广义PDA所接收所接收 则则L能够由一般的能够由一

20、般的PDA所接收。所接收。第71页，本讲稿共166页证明思路 广义的广义的PDAPDA的一条规则的一条规则一般一般PDAPDA的多条规则的组合的多条规则的组合就是就是第72页，本讲稿共166页证明：l对于广义的对于广义的PDA的任意一条规则的任意一条规则 增加状态增加状态r1，r2，rk-1，第73页，本讲稿共166页改造为：改造为：第74页，本讲稿共166页l得到一般的得到一般的PDA 且且L=L(PDA)。第75页，本讲稿共166页定义定义5-6单态单态PDA l仅有一个状态的仅有一个状态的PDA 规则简化为规则简化为 第76页，本讲稿共166页(等价性等价性)问题问题l一个一个NFA是否

21、可以是否可以转换转换为为 一个一个单态单态PDA？第77页，本讲稿共166页思路思路 NFA=（Q，,，q0，F）将将NFA的的状态状态当作当作PDA的的栈内符号栈内符号构造单态的构造单态的PDA=（*，Q，*，q0，*)第78页，本讲稿共166页NFA：(q，x)=q1，q2，qn单态的单态的PDA：第79页，本讲稿共166页lNFA：若若 q*(q0，w)l单态的单态的PDA：有有（*，w，q0）=*（*，q）第80页，本讲稿共166页lNFA：若若(q，x)Fl 单态的单态的PDA：第81页，本讲稿共166页因此因此NFA：*(q0，w)F单态的单态的PDA：（*，w，q0）=*（*，）

22、即即 L(NFA)=L(PDA)第82页，本讲稿共166页右线性文法右线性文法G=（，V，S，P）也可以对应一个单态的也可以对应一个单态的PDA，第83页，本讲稿共166页l产生式产生式 AbB Ab PDA的规则的规则 第84页，本讲稿共166页l将文法的开始符号将文法的开始符号S当作是单态当作是单态PDA的栈底符号，则的栈底符号，则 第85页，本讲稿共166页对于文法对于文法G S=*w1A=w1bB=*w1bw2=w对于单态对于单态PDA (*，w1bw2，S)=*(*，bw2，A)=(*，w2，B)=*(*，)第86页，本讲稿共166页例5-4 语言L=anbn|n1文法文法SaSBS

23、aB Bb 单态单态PDA第87页，本讲稿共166页l对对于于串串anbn，单单态态的的PDA可可能能会会有有以以下下的格局转换：的格局转换：(*，anbn，S）=n(*，an-jbn，SBj）(*，anbn，S）=n（*，an-kbn，Bk）(*，anbn，S）=n（*，bn，Bn）其中：其中：是导出是导出和和的中间过程；的中间过程；第88页，本讲稿共166页会会导导致致停停机机，因因为为没没有有合合适适的的规规则则可以完成最后的转换：可以完成最后的转换：（*，bn，Bn）=*（*，）第89页，本讲稿共166页 使用使用n-1次规则次规则 1次规则次规则 n次规则次规则 第90页，本讲稿共1

24、66页5.1.5 下推自动机的存储技术下推自动机的存储技术l参考参考Turing的存储技术。的存储技术。l略略第91页，本讲稿共166页5.1.6 PDA扫描多个符号扫描多个符号l参考参考Turing的扫描多个符号技术。的扫描多个符号技术。l略略第92页，本讲稿共166页5.2 上下文无关文法和范式上下文无关文法和范式l范式是指标准的形式范式是指标准的形式l在在代代数数中中，2/4，3/6，的的范范式式是是1/2。本本节节讨讨论论在在上上下下文文无无关关文文法法的的几几个个重重要要的的范式范式。第93页，本讲稿共166页定理定理5-5G是是一一个个上上下下文文无无关关文文法法，则则存存在在一一

25、个个上上下下文无关文法文无关文法G，使得：，使得：L(G)=L(G)若若L(G)，则，则G没有空串产生式没有空串产生式第94页，本讲稿共166页若若L(G)，则，则G有有S，且且S不出现在不出现在G的任何产生式的右边的任何产生式的右边G中没有中没有AB形式的产生式。形式的产生式。第95页，本讲稿共166页证明证明前前3点是点是空串定理空串定理的内容的内容(见见2.6)第第4点证明参见点证明参见参考文献参考文献1。第96页，本讲稿共166页5.2.1 Chomsky范式(CNF)l定义定义5-7 上下文无关文法上下文无关文法G=(，V，S，P)若若G的每个产生式是下列形式之一：的每个产生式是下列

26、形式之一：第97页，本讲稿共166页 ABC A，B，CV Aa AV，a S 且且S不出现在产生式的右边不出现在产生式的右边则则G是是Chomsky范式范式(CNF)。第98页，本讲稿共166页定理5-6 G是是一一个个上上下下文文无无关关文文法法，则则存存在在一一个个等等价的上下文无关文法价的上下文无关文法G 使得使得L(G)=L(G)，且，且G是是CNF。第99页，本讲稿共166页证明证明l对于任意的上下文无关文法对于任意的上下文无关文法G 首先使它满足首先使它满足定理定理5-5的要求的要求 对于文法中的任意的产生式对于文法中的任意的产生式 AB1B2Bm 第100页，本讲稿共166页l

27、假设每个假设每个Bi都是非终结符都是非终结符(若不是，则使用非终结符若不是，则使用非终结符Bi来代替来代替Bi，并增加产生式，并增加产生式BiBi)第101页，本讲稿共166页AB1B2Bm若若m=2，满足了，满足了CNF要求；要求；m3，将它改造为，将它改造为m-1个产生式：个产生式：第102页，本讲稿共166页AB1B2Bm AB1C1 C1B2C2 Cm-3Bm-2Cm-2 Cm-2Bm-1Bm第103页，本讲稿共166页l其中其中 C1，C2，Cm-2是新加的非终结符是新加的非终结符得到的文法得到的文法G是是CNF 且且L(G)=L(G)。证毕。证毕。第104页，本讲稿共166页5.2

28、.2 Greibach范式(GNF)l定义定义5-8上下文无关文法上下文无关文法G=(，V，S，P)是是GNF，若，若G的每个产生式形式为的每个产生式形式为 AbW b，WV*第105页，本讲稿共166页定理5-7lG是是一一个个上上下下文文无无关关文文法法，则则存存在在一一个个等等价的上下文无关文法价的上下文无关文法G，l使得使得L(G)=L(G)且且G中没有中没有直接左递归直接左递归的产生式，的产生式，即不存在即不存在AAv形式的产生式形式的产生式 其中：其中：AV，v(UV)+。第106页，本讲稿共166页l没没有有直直接接左左递递归归的的文文法法也也称称为为无无直直接接左递归范式（左递

29、归范式（NLR）。）。第107页，本讲稿共166页证明l见见2.7。第108页，本讲稿共166页l某些文法可能没有直接左递归，某些文法可能没有直接左递归，但可能会有但可能会有间接左递归间接左递归。第109页，本讲稿共166页定理定理5-8lG是一个上下文无关文法，则存在一个是一个上下文无关文法，则存在一个等价的上下文无关文法等价的上下文无关文法G，使得使得L(G)=L(G)且且G中没有间接左递归的产生式。中没有间接左递归的产生式。第110页，本讲稿共166页l没有间接左递归的文法也称为无间没有间接左递归的文法也称为无间接左递归范式。接左递归范式。第111页，本讲稿共166页证明证明l见见2.7

30、。第112页，本讲稿共166页定理5-9lG是是任任意意一一个个上上下下文文无无关关文文法法，则则存存在在一一个等价的上下文无关文法个等价的上下文无关文法G，使得使得L(G)=L(G)且且G是是Greibach范式范式(GNF)。第113页，本讲稿共166页l对对于于任任意意的的上上下下文文无无关关文文法法G，产产生生式式形形式为式为 AiAjw Aiaw或或第114页，本讲稿共166页假设假设w包含的字符全为非终结符包含的字符全为非终结符对于对于Aiaw，本身就是，本身就是GNF的形式的形式第115页，本讲稿共166页对于对于AiAjw l利利用用消消除除左左递递归归的的算算法法，在在消消除

31、除左左递递归归的的以以后后，从从An-1开开始始，将将An代代入入到到An-1，将将An-1代入到代入到A n-2，直至，直至A1，再再将将增增加加的的非非终终结结符符的的产产生生式式的的开开头头符符号号代替掉，得到代替掉，得到GNF。第116页，本讲稿共166页5.3 PDA与上下文无关语言与上下文无关语言lPDA识别的语言是上下文无关语言。识别的语言是上下文无关语言。第117页，本讲稿共166页定理5-10l对于上下文无关语言对于上下文无关语言L和文法和文法G 若若L=L(G)，则，则语言语言L能被能被(广义广义)不确定的不确定的PDA所接收所接收第118页，本讲稿共166页证明：l假设文

32、法是假设文法是GNF范式范式 构造一个单态的构造一个单态的PDA来接收语言来接收语言L；第119页，本讲稿共166页l文文法法G中中有有3种种形形式式的的产产生生式式，它它们们分分别别对应对应PDA的规则：的规则：S Ab AbW其中：其中：AV，WV+，第120页，本讲稿共166页需要证明需要证明语言语言L=L(PDA)。为证明之，先证明为证明之，先证明（*，w1w2，S）=*（*，w2，）iff S=*w1第121页，本讲稿共166页即扫描串后即扫描串后w1，M栈内符号串为栈内符号串为；若上述成立，假设若上述成立，假设w2=，则，则（*，w1，S）=*（*，）iff S=*w1第122页，

33、本讲稿共166页l现在用归纳法证明现在用归纳法证明（对串（对串w1的长度进行归纳）的长度进行归纳）（*,w1w2，S）=*（*,w2，）iff S=*w1第123页，本讲稿共166页证明证明基础：当基础：当w1=，有两种情况：，有两种情况：a）（）（*，w2，S）=*（*，w2，S）iff S=*S 是成立的；是成立的；b）若）若S在在G中，则有中，则有 （*,w2，S）=*（*，w2，）iff S=*是成立的；是成立的；第124页，本讲稿共166页l假设：当假设：当w1时，长度为时，长度为n时；时；（*,w1w2，S）=*（*,w2，）iff S=*w1l令令=A，w2=aw3，（将将w1a

34、当当作作新新的的w1，长度为，长度为n+1），则），则第125页，本讲稿共166页l(*,w1aw3，S）=*（*,aw3，A）iff S=*w1Al而而（*，aw3，A）=（*，w3，）iff Aa第126页，本讲稿共166页因此因此(*，w1aw3，S)=*(*，w3，)iff S=*w1al所以：假设成立，证毕。所以：假设成立，证毕。第127页，本讲稿共166页例5-10文法文法G为为 S(L|L(LL|)对于串：对于串：()()第128页，本讲稿共166页l构造的单态的构造的单态的PDA（栈底为（栈底为S）为：）为：S(LS L(LLL)第129页，本讲稿共166页l对于单态的对于单态

35、的PDA 可以构造对应的上下文无关文法可以构造对应的上下文无关文法G 使得使得L(M)=L(G)第130页，本讲稿共166页例5-11有单态的PDA：第131页，本讲稿共166页构构造造上上下下文文无无关关文文法法G（用用Z代代替替Z0作作为为开始符号）为：开始符号）为：ZaAZ|bBZ|AaAA|b BbBB|a第132页，本讲稿共166页例5-12构造PDA 接收接收语语言言 L=w2wT|w0,1*第133页，本讲稿共166页解法1：lread-match第134页，本讲稿共166页解法2：GNF=PDAl产生产生L的上下文无关文法：的上下文无关文法：S2|0S0|1S1第135页，本讲

36、稿共166页将文法转化成GNF S2|0SA|1SB A0 B1第136页，本讲稿共166页构造单态PDA /S0SA /S1SB /S2 /A0 /B1第137页，本讲稿共166页定理定理5-11l对于单态的对于单态的PDA 存在一个上下文无关文法存在一个上下文无关文法G 使得使得L（G）=L(PDA)且且G为为GNF范式形式。范式形式。第138页，本讲稿共166页证明证明 PDA 文法文法 Ba Ba 第139页，本讲稿共166页l根据单态的根据单态的PDA 可以得到对应的可以得到对应的GNF。而而多多态态的的PDA，不不可可以以直直接接得得到到GNF。第140页，本讲稿共166页问题问题

37、多态多态PDA如何得到对应的上下文无关文法如何得到对应的上下文无关文法？第141页，本讲稿共166页定理5-12l对对于于多多态态PDA，存存在在上上下下文文无无关关文文法法G，使得，使得L(G)=L(M)。第142页，本讲稿共166页证明证明l构造上下文无关文法构造上下文无关文法G 思思路路为为用用文文法法的的一一个个推推导导模模拟拟PDA的一个动作的一个动作。l具体过程参考具体过程参考P135。第143页，本讲稿共166页对于对于多态PDAl得得到到对对应应的的上上下下文文无无关关文文法法的的产产生生式具有如下的形式：式具有如下的形式：AaA1A2An AA1A2An Aa A第144页，

38、本讲稿共166页定理5-13l若若M是是多多态态的的PDA，则则存存在在一一个个单单态态PDA，使得，使得 L(PDA)=L(PDA)第145页，本讲稿共166页证明证明l略。略。第146页，本讲稿共166页总之总之l对于一个对于一个PDA 存存在在一一个个上上下下文文无无关关文文法法G，使使得得L(M)=L(G)。第147页，本讲稿共166页注意注意确定确定PDA和不确定和不确定PDA不等价。不等价。第148页，本讲稿共166页例例 构造构造PDA接收接收l语言语言L=w|wa,b*w中中a的个数为的个数为b的的2倍倍 且且a必须成对出现必须成对出现 第149页，本讲稿共166页思路：l将一

39、个将一个a当作一个成对的当作一个成对的aa:构造上下文无关文法构造上下文无关文法G为：为：ZaCAZ|bBZ|AaCAA|bBbBB|aCCa第150页，本讲稿共166页有单态PDA：第151页，本讲稿共166页例5-16构造构造(广义广义)PDA接收接收语言语言 L=w|wa,b*且且w中中a的个数为的个数为b的的2倍倍第152页，本讲稿共166页考虑出栈情况基本结构为：基本结构为：aab、aba和和baa。第153页，本讲稿共166页aab、aba和baa第154页，本讲稿共166页方法方法2：构造文法构造文法SSaSaSbS|SaSbSaS|SbSaSaS|转换为转换为GNF 转换为转换

40、为PDA第155页，本讲稿共166页思考思考 构造构造PDA接收接收语语言言L=w|wa,b+,且且w中中a的的个个数数为为b的的2倍倍考查题考查题第第2题题第156页，本讲稿共166页例5-17 构造构造PDA接收接收 语言语言 L=anbm|0n m，m 2n第157页，本讲稿共166页 SaSB|aSBB|Bb第158页，本讲稿共166页单态单态PDA为为第159页，本讲稿共166页或或 单态单态PDA第160页，本讲稿共166页例5-18 构造构造PDA接收接收语言语言L=anbm|0 m n，n 2m第161页，本讲稿共166页SaASB|aSB|AaBb第162页，本讲稿共166页单态PDA第163页，本讲稿共166页或或 单态单态PDA第164页，本讲稿共166页补充补充l 双栈双栈PDA:Q Q*识别语言识别语言 l anbn anbm 和简单算术表达式和简单算术表达式第165页，本讲稿共166页anbn第166页，本讲稿共166页