有限自动机理论章下推自动机幻灯片.ppt

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

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

2、种模型就是下推自动机这种模型就是下推自动机PDA第4页，共166页，编辑于2022年，星期六 PDA作作为为形形式式系系统统最最早早于于1961年年出出现在现在 Oettinger 的论文中。的论文中。与与 上上 下下 文文 无无 关关 文文 法法 的的 等等 价价 性性 由由Chomsky于于1962年年发现发现。第5页，共166页，编辑于2022年，星期六与与FA比较比较PDA具有一个栈存储器具有一个栈存储器有两个操作：有两个操作：入栈入栈-将内容压入栈中将内容压入栈中 出栈出栈-将栈顶元素移出将栈顶元素移出第6页，共166页，编辑于2022年，星期六下推自动机下推自动机物理模型物理模型a

3、1a2a3ajanan+1FSC存储带存储带栈存储器栈存储器第7页，共166页，编辑于2022年，星期六栈存储器栈存储器 存放存放不同于不同于字母的符号字母的符号 只能对只能对栈顶栈顶元素进行操作。元素进行操作。第8页，共166页，编辑于2022年，星期六下推自动机动作下推自动机动作 根据 FSC当前的当前的状态状态 输入带上的当前输入带上的当前字符字符 栈顶符号栈顶符号 进行进行状态改变状态改变和入栈或出栈和入栈或出栈操操作作 将读头向右将读头向右移动移动一个单元一个单元第9页，共166页，编辑于2022年，星期六5.1.1 确定的下推自动机确定的下推自动机 例例5-1 语言语言 L=w|w

4、(a,b)*，且，且a、b个数相等个数相等 暂时不考虑状态暂时不考虑状态 (或或PDA仅有一个状态仅有一个状态)第10页，共166页，编辑于2022年，星期六初始初始栈为空栈为空从左到右逐个扫描串从左到右逐个扫描串w(a，b)*第11页，共166页，编辑于2022年，星期六入栈若栈为若栈为空空,当前符号是当前符号是a,则则A入栈入栈若栈为若栈为空空,当前符号是当前符号是b,则则B入栈入栈若栈顶为若栈顶为A,当前符号是当前符号是a,则则A入栈入栈若栈顶为若栈顶为B,当前符号是当前符号是b,则则B入栈入栈第12页，共166页，编辑于2022年，星期六出栈若栈顶为若栈顶为A,当前符号是当前符号是b，

5、则，则A出栈出栈若栈顶为若栈顶为B,当前符号是当前符号是a，则，则B出栈出栈第13页，共166页，编辑于2022年，星期六若串若串w有相同个数的有相同个数的a和和b 当且仅当当且仅当 w扫描结束后，扫描结束后，栈为空栈为空。第14页，共166页，编辑于2022年，星期六注意注意PDA在在两种情况下停机两种情况下停机：串扫描结束串扫描结束 没有对应的规则没有对应的规则第15页，共166页，编辑于2022年，星期六串扫描结束栈如果为空栈如果为空 就接收扫描过的串。就接收扫描过的串。第16页，共166页，编辑于2022年，星期六对于非正式的对于非正式的算法算法，用用形式化形式化的方式进行描述：的方式

6、进行描述：第17页，共166页，编辑于2022年，星期六特殊的符号特殊的符号Z0表示栈底表示栈底 初始化时先压入栈初始化时先压入栈第18页，共166页，编辑于2022年，星期六规则规则(指令指令)若若x是是w的当前符号的当前符号 D是栈顶符号是栈顶符号则用符号串则用符号串V代替代替D即将即将D弹出栈，而将串弹出栈，而将串V压入栈压入栈第19页，共166页，编辑于2022年，星期六具体若若x是是w的的当当前前符符号号，栈栈顶顶符符号号为为D 将将D弹出栈弹出栈 将将A压入栈，成为新的栈顶压入栈，成为新的栈顶第20页，共166页，编辑于2022年，星期六一般地一般地若若x是是w的的当当前前符符号号

7、，栈栈顶顶符符号号为为D 表示：表示：将将D弹出栈弹出栈 将串将串A1A2 Ak压入栈压入栈(A1为新栈顶为新栈顶)第21页，共166页，编辑于2022年，星期六例例5-1 算法的算法的形式化描述形式化描述第22页，共166页，编辑于2022年，星期六规则规则 表示将表示将w扫描结束后，扫描结束后，将栈置成空将栈置成空也表示该也表示该PDA可以接收可以接收空串空串第23页，共166页，编辑于2022年，星期六思考：如何接收语言如何接收语言 L=w|w(a,b)+,且且a和和b个数相等个数相等?第24页，共166页，编辑于2022年，星期六例：语言L=anbn|n0定义：定义：第25页，共166

8、页，编辑于2022年，星期六则还可以接收语言则还可以接收语言 (ab)n|n0，或，或 ambm(ab)n|m0,n0 等语言。等语言。第26页，共166页，编辑于2022年，星期六思考：如何接收语言 L=anbn|n0 L=anbn|n0 L=(ab)n|n0 L=(ab)n|n0第27页，共166页，编辑于2022年，星期六例5-2 L=wcwT|w(a，b)*识别语言识别语言第28页，共166页，编辑于2022年，星期六思想：将将w的各个字符压入栈后的各个字符压入栈后 栈中的内容从栈中的内容从栈顶到栈底栈顶到栈底的顺序的顺序 刚好是刚好是wT的顺序的顺序第29页，共166页，编辑于202

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

10、状态改变为q并用符号串并用符号串V代替代替D第32页，共166页，编辑于2022年，星期六（在本例中）用（在本例中）用Z代表任意的栈顶符号代表任意的栈顶符号 规则规则read，a，Z，read，AZ可以表示以下可以表示以下3条规则：条规则：read，a，Z0，read，AZ0read，a，A，read，AAread，a，B，read，AB第33页，共166页，编辑于2022年，星期六用下列的规则来描述用下列的规则来描述PDAread，a，Z，read，AZread，b，Z，read，BZread，c，Z，match，Zmatch，a，A，match，match，b，B，match，match，

11、Z0，match，第34页，共166页，编辑于2022年，星期六若串若串w是该语言的合法的串是该语言的合法的串 当且仅当当且仅当 w扫描结束后，扫描结束后，栈为空栈为空。第35页，共166页，编辑于2022年，星期六Z0符号栈符号栈串串abbcbba的处理过程的处理过程ABreadmatch=B第36页，共166页，编辑于2022年，星期六扫描到扫描到字母字母c 栈栈内内的的内内容容（从从栈栈顶顶到到栈栈底底）是是扫扫描描过的串的逆过的串的逆 与未扫描过的串的顺序相同与未扫描过的串的顺序相同此时，不作出栈和入栈操作，此时，不作出栈和入栈操作，仅仅把仅仅把PDA的的状态从状态从read改变到改变

12、到match。第37页，共166页，编辑于2022年，星期六接收语言接收语言L=anbn|n0q0，a，Z0，q0，AZ0q0，a，A，q0，AAq0，b，A，q1，q1，b，A，q1，q1，Z0，q1，第38页，共166页，编辑于2022年，星期六5.1.2 不确定的下推自动机不确定的下推自动机例例5-3 语言语言L=wwT|w(a,b)*第39页，共166页，编辑于2022年，星期六 没有中心点字符没有中心点字符 在在扫扫描描过过程程中中，就就没没有有确确定定的的位位置置进行状态的变换进行状态的变换 具有具有不确定不确定性。性。第40页，共166页，编辑于2022年，星期六使用规则使用规则

13、read，Z，match，Z 来代替来代替read，c，Z，match，Z即即在在read状状态态时时，可可随随时时改改变变为为match状状态态（栈的内容和扫描符号不变）（栈的内容和扫描符号不变）第41页，共166页，编辑于2022年，星期六read，a，Z，read，AZread，b，Z，read，BZread，Z，match，Zmatch，a，A，match，match，b，B，match，match，Z0，match，第42页，共166页，编辑于2022年，星期六该该PDA是是不确定不确定的的 处于状态处于状态read状态时状态时 随时随时都可以进行选择都可以进行选择:继续扫描，或状态

14、变换为继续扫描，或状态变换为match第43页，共166页，编辑于2022年，星期六一个串一个串w能够由能够由PDA所识别：所识别：仅当串是仅当串是wwT的形式的形式且且PDA状态在状态在中心点中心点进行了变换进行了变换第44页，共166页，编辑于2022年，星期六对于不确定的对于不确定的PDA和串和串w 若存在至少一个可能的扫描过程若存在至少一个可能的扫描过程 使得当串使得当串w扫描结束时，栈为空扫描结束时，栈为空 则称串则称串w能够被能够被PDA所所识别识别。第45页，共166页，编辑于2022年，星期六接收语言接收语言L=(ab)n|n0q1，a，Z0，q2，AZ0q2，b，A，q1，q

15、1，Z0，q1，第46页，共166页，编辑于2022年，星期六接收语言接收语言L=(ab)n|n0q0，a，Z0，q0，AZ0q0，b，A，q1，q1，a，Z0，q2，AZ0q2，b，A，q1，q1，Z0，q1，第47页，共166页，编辑于2022年，星期六定义5-1下推自动机下推自动机PDA是一个七元式：是一个七元式：M=(Q，q0，Z0，F)Q是一个有限状态的集合是一个有限状态的集合 是输入串的字母集合是输入串的字母集合 是栈内符号集合是栈内符号集合第48页，共166页，编辑于2022年，星期六q0Q是开始状态是开始状态Z0是栈底符号是栈底符号F Q是接收状态集合是接收状态集合第49页，共

16、166页，编辑于2022年，星期六：Q()Q*对于确定的对于确定的PDA，有，有 （q，x，D）=(q，V)对于不确定的对于不确定的PDA，有，有 (q，V)（q，x，D）第50页，共166页，编辑于2022年，星期六一般一般使用使用 表示表示函数函数第51页，共166页，编辑于2022年，星期六定义定义5-2 PDA格局格局(或瞬间描述或瞬间描述ID)格局代表某个时刻格局代表某个时刻PDA的情况的情况 PDA的格局是一个三元式的格局是一个三元式 (q，w，)其中，其中，q为状态为状态第52页，共166页，编辑于2022年，星期六w=x1x2xn 还没有被扫描到的串还没有被扫描到的串(将扫描将

17、扫描x1)=Z1Z2Zm 栈的内容栈的内容(Z1在栈顶在栈顶，Zm在栈底在栈底)第53页，共166页，编辑于2022年，星期六PDA初始格局为初始格局为 (q0，w，Z0)接收格局为接收格局为 (q，)其中其中:qQ（与接收状态无关）（与接收状态无关）第54页，共166页，编辑于2022年，星期六格局的转换是格局的转换是 由于状态转换函数的作用引起的由于状态转换函数的作用引起的第55页，共166页，编辑于2022年，星期六确定的确定的PDA 引起的格局转换为：引起的格局转换为：(q，xw，A)=(q1，w，A1A2 Ak)第56页，共166页，编辑于2022年，星期六不确定的不确定的PDA （

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

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

20、栈是否为空无关接收格局与栈是否为空无关只只要要当当串串w扫扫描描结结束束，而而PDA处处于于某某个个接收状态接收状态则串则串w被被PDA以终态方式以终态方式所接收。所接收。第64页，共166页，编辑于2022年，星期六定理5-1语言语言L被被PDA以终态方式以终态方式所接收所接收 当且仅当当且仅当 它被它被PDA以以空栈方式空栈方式所接收。所接收。即终态接收与空栈接收方式等价。即终态接收与空栈接收方式等价。第65页，共166页，编辑于2022年，星期六证明：证明：l略略第66页，共166页，编辑于2022年，星期六5.1.4广义广义PDA和单态和单态PDA定义定义5-5 广义的广义的PDA是七

21、元式是七元式 PDA=(Q,，q0，Z0，F)（除了（除了外，其余同一般的外，其余同一般的PDA）其中其中第67页，共166页，编辑于2022年，星期六Q是一个有限状态的集合是一个有限状态的集合是输入串的字母集合是输入串的字母集合是栈内符号集合是栈内符号集合q0Q是开始状态是开始状态Z0是初始的栈底符号是初始的栈底符号F Q是接收状态是接收状态(终止状态终止状态)集合集合第68页，共166页，编辑于2022年，星期六：Q()+Q*(q，x，B1 B2 Bk)=(q，C1 C2 Cn)一般形式为一般形式为 第69页，共166页，编辑于2022年，星期六一般的一般的PDA，栈顶只是一个符号，栈顶只

22、是一个符号广义广义PDA的的栈顶栈顶可以为可以为多个符号多个符号。第70页，共166页，编辑于2022年，星期六定理5-4若语言若语言L能由广义能由广义PDA所接收所接收 则则L能够由一般的能够由一般的PDA所接收。所接收。第71页，共166页，编辑于2022年，星期六证明思路 广义的广义的PDAPDA的一条规则的一条规则一般一般PDAPDA的多条规则的组合的多条规则的组合就是就是第72页，共166页，编辑于2022年，星期六证明：l对于广义的对于广义的PDA的任意一条规则的任意一条规则 增加状态增加状态r1，r2，rk-1，第73页，共166页，编辑于2022年，星期六改造为：改造为：第74

23、页，共166页，编辑于2022年，星期六l得到一般的得到一般的PDA 且且L=L(PDA)。第75页，共166页，编辑于2022年，星期六定义定义5-6单态单态PDA l仅有一个状态的仅有一个状态的PDA 规则简化为规则简化为 第76页，共166页，编辑于2022年，星期六(等价性等价性)问题问题l一个一个NFA是否可以是否可以转换转换为为 一个一个单态单态PDA？第77页，共166页，编辑于2022年，星期六思路思路 NFA=（Q，,，q0，F）将将NFA的的状态状态当作当作PDA的的栈内符号栈内符号构造单态的构造单态的PDA=（*，Q，*，q0，*)第78页，共166页，编辑于2022年，

24、星期六NFA：(q，x)=q1，q2，qn单态的单态的PDA：第79页，共166页，编辑于2022年，星期六lNFA：若若 q*(q0，w)l单态的单态的PDA：有有（*，w，q0）=*（*，q）第80页，共166页，编辑于2022年，星期六lNFA：若若(q，x)Fl 单态的单态的PDA：第81页，共166页，编辑于2022年，星期六因此因此NFA：*(q0，w)F单态的单态的PDA：（*，w，q0）=*（*，）即即 L(NFA)=L(PDA)第82页，共166页，编辑于2022年，星期六右线性文法右线性文法G=（，V，S，P）也可以对应一个单态的也可以对应一个单态的PDA，第83页，共16

25、6页，编辑于2022年，星期六l产生式产生式 AbB Ab PDA的规则的规则 第84页，共166页，编辑于2022年，星期六l将文法的开始符号将文法的开始符号S当作是单态当作是单态PDA的栈底符号，则的栈底符号，则 第85页，共166页，编辑于2022年，星期六对于文法对于文法G S=*w1A=w1bB=*w1bw2=w对于单态对于单态PDA (*，w1bw2，S)=*(*，bw2，A)=(*，w2，B)=*(*，)第86页，共166页，编辑于2022年，星期六例5-4 语言L=anbn|n1文法文法SaSBSaB Bb 单态单态PDA第87页，共166页，编辑于2022年，星期六l对对于于

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

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

28、是是一一个个上上下下文文无无关关文文法法，则则存存在在一一个个上上下文无关文法下文无关文法G，使得：，使得：L(G)=L(G)若若L(G)，则，则G没有空串产生式没有空串产生式第94页，共166页，编辑于2022年，星期六若若L(G)，则，则G有有S，且且S不出现在不出现在G的任何产生式的右边的任何产生式的右边G中没有中没有AB形式的产生式。形式的产生式。第95页，共166页，编辑于2022年，星期六证明证明前前3点是点是空串定理空串定理的内容的内容(见见2.6)第第4点证明参见点证明参见参考文献参考文献1。第96页，共166页，编辑于2022年，星期六5.2.1 Chomsky范式(CNF)

29、l定义定义5-7 上下文无关文法上下文无关文法G=(，V，S，P)若若G的每个产生式是下列形式之一：的每个产生式是下列形式之一：第97页，共166页，编辑于2022年，星期六 ABC A，B，CV Aa AV，a S 且且S不出现在产生式的右边不出现在产生式的右边则则G是是Chomsky范式范式(CNF)。第98页，共166页，编辑于2022年，星期六定理5-6 G是是一一个个上上下下文文无无关关文文法法，则则存存在在一一个个等等价的上下文无关文法价的上下文无关文法G 使得使得L(G)=L(G)，且，且G是是CNF。第99页，共166页，编辑于2022年，星期六证明证明l对于任意的上下文无关文

30、法对于任意的上下文无关文法G 首先使它满足首先使它满足定理定理5-5的要求的要求 对于文法中的任意的产生式对于文法中的任意的产生式 AB1B2Bm 第100页，共166页，编辑于2022年，星期六l假设每个假设每个Bi都是非终结符都是非终结符(若不是，则使用非终结符若不是，则使用非终结符Bi来代替来代替Bi，并增加产生式，并增加产生式BiBi)第101页，共166页，编辑于2022年，星期六AB1B2Bm若若m=2，满足了，满足了CNF要求；要求；m3，将它改造为，将它改造为m-1个产生式：个产生式：第102页，共166页，编辑于2022年，星期六AB1B2Bm AB1C1 C1B2C2 Cm

31、-3Bm-2Cm-2 Cm-2Bm-1Bm第103页，共166页，编辑于2022年，星期六l其中其中 C1，C2，Cm-2是新加的非终结符是新加的非终结符得到的文法得到的文法G是是CNF 且且L(G)=L(G)。证毕。证毕。第104页，共166页，编辑于2022年，星期六5.2.2 Greibach范式(GNF)l定义定义5-8上下文无关文法上下文无关文法G=(，V，S，P)是是GNF，若，若G的每个产生式形式为的每个产生式形式为 AbW b，WV*第105页，共166页，编辑于2022年，星期六定理5-7lG是是一一个个上上下下文文无无关关文文法法，则则存存在在一一个个等价的上下文无关文法等

32、价的上下文无关文法G，l使得使得L(G)=L(G)且且G中没有中没有直接左递归直接左递归的产生式，的产生式，即不存在即不存在AAv形式的产生式形式的产生式 其中：其中：AV，v(UV)+。第106页，共166页，编辑于2022年，星期六l没没有有直直接接左左递递归归的的文文法法也也称称为为无无直直接接左左递归范式（递归范式（NLR）。）。第107页，共166页，编辑于2022年，星期六证明l见见2.7。第108页，共166页，编辑于2022年，星期六l某些文法可能没有直接左递归，某些文法可能没有直接左递归，但可能会有但可能会有间接左递归间接左递归。第109页，共166页，编辑于2022年，星期

33、六定理定理5-8lG是一个上下文无关文法，则存在一个是一个上下文无关文法，则存在一个等价的上下文无关文法等价的上下文无关文法G，使得使得L(G)=L(G)且且G中没有间接左递归的产生式。中没有间接左递归的产生式。第110页，共166页，编辑于2022年，星期六l没有间接左递归的文法也称为无间没有间接左递归的文法也称为无间接左递归范式。接左递归范式。第111页，共166页，编辑于2022年，星期六证明证明l见见2.7。第112页，共166页，编辑于2022年，星期六定理5-9lG是是任任意意一一个个上上下下文文无无关关文文法法，则则存存在在一个等价的上下文无关文法一个等价的上下文无关文法G，使得

34、使得L(G)=L(G)且且G是是Greibach范式范式(GNF)。第113页，共166页，编辑于2022年，星期六l对对于于任任意意的的上上下下文文无无关关文文法法G，产产生生式式形式为形式为 AiAjw Aiaw或或第114页，共166页，编辑于2022年，星期六假设假设w包含的字符全为非终结符包含的字符全为非终结符对于对于Aiaw，本身就是，本身就是GNF的形式的形式第115页，共166页，编辑于2022年，星期六对于对于AiAjw l利利用用消消除除左左递递归归的的算算法法，在在消消除除左左递递归归的的以以后后，从从An-1开开始始，将将An代代入入到到An-1，将将An-1代入到代入

35、到A n-2，直至，直至A1，再再将将增增加加的的非非终终结结符符的的产产生生式式的的开开头头符符号代替掉，得到号代替掉，得到GNF。第116页，共166页，编辑于2022年，星期六5.3 PDA与上下文无关语言与上下文无关语言lPDA识别的语言是上下文无关语言。识别的语言是上下文无关语言。第117页，共166页，编辑于2022年，星期六定理5-10l对于上下文无关语言对于上下文无关语言L和文法和文法G 若若L=L(G)，则，则语言语言L能被能被(广义广义)不确定的不确定的PDA所接收所接收第118页，共166页，编辑于2022年，星期六证明：l假设文法是假设文法是GNF范式范式 构造一个单态

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

37、*w1第122页，共166页，编辑于2022年，星期六l现在用归纳法证明现在用归纳法证明（对串（对串w1的长度进行归纳）的长度进行归纳）（*,w1w2，S）=*（*,w2，）iff S=*w1第123页，共166页，编辑于2022年，星期六证明证明基础：当基础：当w1=，有两种情况：，有两种情况：a）（）（*，w2，S）=*（*，w2，S）iff S=*S 是成立的；是成立的；b）若）若S在在G中，则有中，则有 （*,w2，S）=*（*，w2，）iff S=*是成立的；是成立的；第124页，共166页，编辑于2022年，星期六l假设：当假设：当w1时，长度为时，长度为n时；时；（*,w1w2，

38、S）=*（*,w2，）iff S=*w1l令令=A，w2=aw3，（将将w1a当当作作新新的的w1，长度为，长度为n+1），则），则第125页，共166页，编辑于2022年，星期六l(*,w1aw3，S）=*（*,aw3，A）iff S=*w1Al而而（*，aw3，A）=（*，w3，）iff Aa第126页，共166页，编辑于2022年，星期六因此因此(*，w1aw3，S)=*(*，w3，)iff S=*w1al所以：假设成立，证毕。所以：假设成立，证毕。第127页，共166页，编辑于2022年，星期六例5-10文法文法G为为 S(L|L(LL|)对于串：对于串：()()第128页，共166页

39、，编辑于2022年，星期六l构造的单态的构造的单态的PDA（栈底为（栈底为S）为：）为：S(LS L(LLL)第129页，共166页，编辑于2022年，星期六l对于单态的对于单态的PDA 可以构造对应的上下文无关文法可以构造对应的上下文无关文法G 使得使得L(M)=L(G)第130页，共166页，编辑于2022年，星期六例5-11有单态的PDA：第131页，共166页，编辑于2022年，星期六构构造造上上下下文文无无关关文文法法G（用用Z代代替替Z0作作为为开始符号）为：开始符号）为：ZaAZ|bBZ|AaAA|b BbBB|a第132页，共166页，编辑于2022年，星期六例5-12构造PD

40、A 接收接收语语言言 L=w2wT|w0,1*第133页，共166页，编辑于2022年，星期六解法1：lread-match第134页，共166页，编辑于2022年，星期六解法2：GNF=PDAl产生产生L的上下文无关文法：的上下文无关文法：S2|0S0|1S1第135页，共166页，编辑于2022年，星期六将文法转化成GNF S2|0SA|1SB A0 B1第136页，共166页，编辑于2022年，星期六构造单态PDA /S0SA /S1SB /S2 /A0 /B1第137页，共166页，编辑于2022年，星期六定理定理5-11l对于单态的对于单态的PDA 存在一个上下文无关文法存在一个上下

41、文无关文法G 使得使得L（G）=L(PDA)且且G为为GNF范式形式。范式形式。第138页，共166页，编辑于2022年，星期六证明证明 PDA 文法文法 Ba Ba 第139页，共166页，编辑于2022年，星期六l根据单态的根据单态的PDA 可以得到对应的可以得到对应的GNF。而而多多态态的的PDA，不不可可以以直直接接得得到到GNF。第140页，共166页，编辑于2022年，星期六问题问题多态多态PDA如何得到对应的上下文无关文法如何得到对应的上下文无关文法？第141页，共166页，编辑于2022年，星期六定理5-12l对对于于多多态态PDA，存存在在上上下下文文无无关关文文法法G，使得

42、，使得L(G)=L(M)。第142页，共166页，编辑于2022年，星期六证明证明l构造上下文无关文法构造上下文无关文法G 思思路路为为用用文文法法的的一一个个推推导导模模拟拟PDA的一个动作的一个动作。l具体过程参考具体过程参考P135。第143页，共166页，编辑于2022年，星期六对于对于多态PDAl得得到到对对应应的的上上下下文文无无关关文文法法的的产产生生式具有如下的形式：式具有如下的形式：AaA1A2An AA1A2An Aa A第144页，共166页，编辑于2022年，星期六定理5-13l若若M是是多多态态的的PDA，则则存存在在一一个个单单态态PDA，使得，使得 L(PDA)=

43、L(PDA)第145页，共166页，编辑于2022年，星期六证明证明l略。略。第146页，共166页，编辑于2022年，星期六总之总之l对于一个对于一个PDA 存存在在一一个个上上下下文文无无关关文文法法G，使使得得L(M)=L(G)。第147页，共166页，编辑于2022年，星期六注意注意确定确定PDA和不确定和不确定PDA不等价。不等价。第148页，共166页，编辑于2022年，星期六例例 构造构造PDA接收接收l语言语言L=w|wa,b*w中中a的个数为的个数为b的的2倍倍 且且a必须成对出现必须成对出现 第149页，共166页，编辑于2022年，星期六思路：l将一个将一个a当作一个成对

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

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