有限自动机理论05章下推自动机.ppt-淘文阁

资源描述

《有限自动机理论05章下推自动机.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论05章下推自动机.ppt（166页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第五章第五章下推自动机下推自动机 PDAFA识别正则语言识别正则语言(右线性语言右线性语言)PDA识别识别上下文无关语言上下文无关语言 FA只能处理正则语言只能处理正则语言正则文法生成无穷语言正则文法生成无穷语言是由于是由于 A-wA不需要记录不需要记录w的个数的个数无关文法无关文法生成无穷语言生成无穷语言 A-A 需要记录需要记录和和之间的对应关系之间的对应关系无法用无法用FA的有穷个状态来表示。的有穷个状态来表示。为为FA扩充一个扩充一个无限容量无限容量的的栈栈用用栈栈的的内内容容和和FA的的状状态态结结合合起起来来就可以表示就可以表示无限存储。无限存储。这种模型就是下推自动机

2、这种模型就是下推自动机PDA PDA作作为为形形式式系系统统最最早早于于1961年年出现在出现在 Oettinger 的论文中。的论文中。与与上上下下文文无无关关文文法法的的等等价价性性由由Chomsky于于1962年年发现发现。与与FA比较比较PDA具有一个栈存储器具有一个栈存储器有两个操作：有两个操作：入栈入栈-将内容压入栈中将内容压入栈中出栈出栈-将栈顶元素移出将栈顶元素移出下推自动机下推自动机物理模型物理模型a1a2a3 aj anan+1FSC存储带存储带栈存储器栈存储器栈存储器栈存储器存放存放不同于不同于字母的符号字母的符号只能对只能对栈顶栈顶元素进行操作。元素进行操作。下推

3、自动机动作下推自动机动作根据 FSC当前的当前的状态状态输入带上的当前输入带上的当前字符字符栈顶符号栈顶符号进行进行状态改变状态改变和入栈或出栈和入栈或出栈操操作作将读头向右将读头向右移动移动一个单元一个单元5.1.1 确定的下推自动机确定的下推自动机例例5-1 语言语言 L=w|w(a,b)*，且且a、b个个数数相相等等暂时不考虑状态暂时不考虑状态 (或或PDA仅有一个状态仅有一个状态)初始初始栈为空栈为空从左到右逐个扫描串从左到右逐个扫描串w(a，b)*入栈若栈为若栈为空空,当前符号是当前符号是a,则则A入栈入栈若栈为若栈为空空,当前符号是当前符号是b,则则B入栈入栈若栈顶为

4、若栈顶为A,当前符号是当前符号是a,则则A入栈入栈若栈顶为若栈顶为B,当前符号是当前符号是b,则则B入栈入栈出栈若栈顶为若栈顶为A,当前符号是当前符号是b，则则A出栈出栈若栈顶为若栈顶为B,当前符号是当前符号是a，则则B出栈出栈若串若串w有相同个数的有相同个数的a和和b 当且仅当当且仅当 w扫描结束后，扫描结束后，栈为空栈为空。注意注意PDA在在两种情况下停机两种情况下停机：串扫描结束串扫描结束没有对应的规则没有对应的规则串扫描结束栈如果为空栈如果为空就接收扫描过的串。就接收扫描过的串。对于非正式的对于非正式的算法算法，用用形式化形式化的方式进行描述：的方式进行描述：特殊的符号特殊的符号Z

5、0表示栈底表示栈底初始化时先压入栈初始化时先压入栈规则规则(指令指令)若若x是是w的当前符号的当前符号 D是栈顶符号是栈顶符号则用符号串则用符号串V代替代替D即将即将D弹出栈，而将串弹出栈，而将串V压入栈压入栈具体若若x是是w的的当当前前符符号号，栈栈顶顶符符号号为为D 将将D弹出栈弹出栈将将A压入栈，成为新的栈顶压入栈，成为新的栈顶一般地一般地若若x是是w的的当当前前符符号号，栈栈顶顶符符号号为为D 表示：表示：将将D弹出栈弹出栈将将串串A1A2 Ak压压入入栈栈(A1为为新新栈栈顶顶)例例5-1 算法的算法的形式化描述形式化描述规则规则表示将表示将w扫描结束后，扫描结束后，将栈置成

7、栈和出栈动作压栈和出栈动作增加两个增加两个状态状态-read 和和match PDA处于处于read状态时，状态时，处理整个串的前半部分，将对应处理整个串的前半部分，将对应的符号压的符号压入栈入栈扫描到字母扫描到字母c时时 PDA的状态转为的状态转为match开始处理整个串的后半部分，将栈开始处理整个串的后半部分，将栈中的内容中的内容出栈出栈。规则规则若若PDA处于状态处于状态q w的当前字母是的当前字母是x 当前栈顶符号为当前栈顶符号为D则自动机的状态改变为则自动机的状态改变为q并用符号串并用符号串V代替代替D（在本例中）用（在本例中）用Z代表任意的栈顶符号代表任意的栈顶符号规则规则r

8、ead，a，Z，read，AZ可以表示以下可以表示以下3条规则：条规则：read，a，Z0，read，AZ0read，a，A，read，AAread，a，B，read，AB用下列的规则来描述用下列的规则来描述PDAread，a，Z，read，AZread，b，Z，read，BZread，c，Z，match，Zmatch，a，A，match，match，b，B，match，match，Z0，match，若串若串w是该语言的合法的串是该语言的合法的串当且仅当当且仅当 w扫描结束后，扫描结束后，栈为空栈为空。Z0符号栈符号栈串串abbcbba的处理过程的处理过程ABreadmatch=B扫描到扫描

9、到字母字母c 栈栈内内的的内内容容（从从栈栈顶顶到到栈栈底底）是是扫扫描描过的串的逆过的串的逆与未扫描过的串的顺序相同与未扫描过的串的顺序相同此时，不作出栈和入栈操作，此时，不作出栈和入栈操作，仅仅把仅仅把PDA的的状态从状态从read改变到改变到match。接收语言接收语言L=anbn|n0q0，a，Z0，q0，AZ0q0，a，A，q0，AAq0，b，A，q1，q1，b，A，q1，q1，Z0，q1，5.1.2 不确定的下推自动机不确定的下推自动机例例5-3 语言语言L=wwT|w(a,b)*没有中心点字符没有中心点字符在在扫扫描描过过程程中中，就就没没有有确确定定的的位位置进行状态的变换

10、置进行状态的变换具有具有不确定不确定性。性。使用规则使用规则read，Z，match，Z 来代替来代替read，c，Z，match，Z即即在在read状状态态时时，可可随随时时改改变变为为match状态（栈的内容和扫描符号不变）状态（栈的内容和扫描符号不变）read，a，Z，read，AZread，b，Z，read，BZread，Z，match，Zmatch，a，A，match，match，b，B，match，match，Z0，match，该该PDA是是不确定不确定的的处于状态处于状态read状态时状态时随时随时都可以进行选择都可以进行选择:继续扫描，或状态变换为继续扫描，或状态变换为m

11、atch一个串一个串w能够由能够由PDA所识别：所识别：仅当串是仅当串是wwT的形式的形式且且PDA状态在状态在中心点中心点进行了变换进行了变换对于不确定的对于不确定的PDA和串和串w 若存在至少一个可能的扫描过程若存在至少一个可能的扫描过程使得当串使得当串w扫描结束时，栈为空扫描结束时，栈为空则称串则称串w能够被能够被PDA所所识别识别。接收语言接收语言L=(ab)n|n0q1，a，Z0，q2，AZ0q2，b，A，q1，q1，Z0，q1，接收语言接收语言L=(ab)n|n0q0，a，Z0，q0，AZ0q0，b，A，q1，q1，a，Z0，q2，AZ0q2，b，A，q1，q1，Z0，q1，定

12、义5-1下推自动机下推自动机PDA是一个七元式：是一个七元式：M=(Q，q0，Z0，F)Q是一个有限状态的集合是一个有限状态的集合是输入串的字母集合是输入串的字母集合是栈内符号集合是栈内符号集合q0Q是开始状态是开始状态Z0是栈底符号是栈底符号F Q是接收状态集合是接收状态集合：Q()Q*对于确定的对于确定的PDA，有，有（q，x，D）=(q，V)对于不确定的对于不确定的PDA，有，有 (q，V)（q，x，D）一般一般使用使用表示表示函数函数定义定义5-2 PDA格局格局(或瞬间描述或瞬间描述ID)格局代表某个时刻格局代表某个时刻PDA的情况的情况 PDA的格局是一个三元式的格局是一个

13、三元式 (q，w，)其中，其中，q为状态为状态w=x1x2xn 还没有被扫描到的串还没有被扫描到的串(将扫描将扫描x1)=Z1Z2Zm 栈的内容栈的内容(Z1在栈顶在栈顶，Zm在栈底在栈底)PDA初始格局为初始格局为 (q0，w，Z0)接收格局为接收格局为 (q，)其中其中:qQ（与接收状态无关）（与接收状态无关）格局的转换是格局的转换是由于状态转换函数的作用引起的由于状态转换函数的作用引起的确定的确定的PDA 引起的格局转换为：引起的格局转换为：(q，xw，A)=(q1，w，A1A2 Ak)不确定的不确定的PDA （情况（情况1）则则(q,xw,A)=(q1，w,A1A2 Ak)则则(q,

14、xw,A)=(q2，xw，B1B 2Bj)不确定的不确定的PDA （情况（情况2）则则(q,xw,A)=(q1，w，A1A2 Ak)则则(q,xw,A)=(q2，w，B1B 2Bj)用用=*代表格局的任意次变换代表格局的任意次变换不不确确定定PDA对对于于某某一一格格局局可可能会有不同的下一格局。能会有不同的下一格局。5.1.3 PDA接收语言的两种方式接收语言的两种方式定定义义5-3 PAD以以空空栈栈方方式式接接收收的的语语言为言为L(M），），且且 L(M)=w|(q0，w，Z0)=*(q,)qQ接收格局与接收状态无关接收格局与接收状态无关只要当只要当串串w扫描结束扫描结束，而，而栈

15、为空栈为空则串则串w被被PDA以以空栈方式空栈方式所接收。所接收。定义5-4PAD以以终终态态方方式式接接收收的的语语言言为为F(M)，且，且 F(M)=w|(q0,w，Z0)=*(q,)qF,*接收格局与栈是否为空无关接收格局与栈是否为空无关只只要要当当串串w扫扫描描结结束束，而而PDA处处于于某个某个接收状态接收状态则串则串w被被PDA以终态方式以终态方式所接收。所接收。定理5-1语言语言L被被PDA以终态方式以终态方式所接收所接收当且仅当当且仅当它被它被PDA以以空栈方式空栈方式所接收。所接收。即终态接收与空栈接收方式等价。即终态接收与空栈接收方式等价。证明：证明：l略略5.1.4广

16、义广义PDA和单态和单态PDA定义定义5-5 广义的广义的PDA是七元式是七元式 PDA=(Q,，q0，Z0，F)（除了（除了外，其余同一般的外，其余同一般的PDA）其中其中Q是一个有限状态的集合是一个有限状态的集合是输入串的字母集合是输入串的字母集合是栈内符号集合是栈内符号集合q0Q是开始状态是开始状态Z0是初始的栈底符号是初始的栈底符号F Q是接收状态是接收状态(终止状态终止状态)集合集合：Q()+Q*(q，x，B1 B2 Bk)=(q，C1 C2 Cn)一般形式为一般形式为一般的一般的PDA，栈顶只是一个符号，栈顶只是一个符号广义广义PDA的的栈顶栈顶可以为可以为多个符号多个符号。定理

17、5-4若语言若语言L能由广义能由广义PDA所接收所接收则则L能够由一般的能够由一般的PDA所接收。所接收。证明思路广义的广义的PDAPDA的一条规则的一条规则一般一般PDAPDA的多条规则的组合的多条规则的组合就是就是证明：l对于广义的对于广义的PDA的任意一条规则的任意一条规则增加状态增加状态r1，r2，rk-1，改造为：改造为：l得到一般的得到一般的PDA 且且L=L(PDA)。定义定义5-6单态单态PDA l仅有一个状态的仅有一个状态的PDA 规则简化为规则简化为 (等价性等价性)问题问题l一个一个NFA是否可以是否可以转换转换为为一个一个单态单态PDA？思路思路 NFA=（Q，

18、,，q0，F）将将NFA的的状态状态当作当作PDA的的栈内符号栈内符号构造单态的构造单态的PDA=（*，Q，*，q0，*)NFA：(q，x)=q1，q2，qn单态的单态的PDA：lNFA：若若 q*(q0，w)l单态的单态的PDA：有有（*，w，q0）=*（*，q）lNFA：若若(q，x)Fl 单态的单态的PDA：因此因此NFA：*(q0，w)F单态的单态的PDA：（*，w，q0）=*（*，）即即 L(NFA)=L(PDA)右线性文法右线性文法G=（，V，S，P）也可以对应一个单态的也可以对应一个单态的PDA，l产生式产生式 AbB Ab PDA的规则的规则 l将文法的开始符号将文法的开始符号

19、S当作是单态当作是单态PDA的栈底符号，则的栈底符号，则对于文法对于文法G S=*w1A=w1bB=*w1bw2=w对于单态对于单态PDA (*，w1bw2，S)=*(*，bw2，A)=(*，w2，B)=*(*，)例5-4 语言L=anbn|n1文法文法SaSBSaB Bb 单态单态PDAl对对于于串串anbn，单单态态的的PDA可可能能会会有有以以下的格局转换：下的格局转换：(*，anbn，S）=n(*，an-jbn，SBj）(*，anbn，S）=n（*，an-kbn，Bk）(*，anbn，S）=n（*，bn，Bn）其中：其中：是导出是导出和和的中间过程；的中间过程；会会导导致致停停机机，

20、因因为为没没有有合合适适的的规规则则可以完成最后的转换：可以完成最后的转换：（*，bn，Bn）=*（*，）使用使用n-1次规则次规则 1次规则次规则 n次规则次规则 5.1.5 下推自动机的存储技术下推自动机的存储技术l参考参考Turing的存储技术。的存储技术。l略略5.1.6 PDA扫描多个符号扫描多个符号l参考参考Turing的扫描多个符号技术。的扫描多个符号技术。l略略5.2 上下文无关文法和范式上下文无关文法和范式l范式是指标准的形式范式是指标准的形式l在在代代数数中中，2/4，3/6，的的范范式式是是1/2。本本节节讨讨论论在在上上下下文文无无关关文文法法的的几几个个重重要的要的范

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

22、列形式之一：ABC A，B，CV Aa AV，a S 且且S不出现在产生式的右边不出现在产生式的右边则则G是是Chomsky范式范式(CNF)。定理5-6 G是是一一个个上上下下文文无无关关文文法法，则则存存在在一一个等价的上下文无关文法个等价的上下文无关文法G 使得使得L(G)=L(G)，且，且G是是CNF。证明证明l对于任意的上下文无关文法对于任意的上下文无关文法G 首先使它满足首先使它满足定理定理5-5的要求的要求对于文法中的任意的产生式对于文法中的任意的产生式 AB1B2Bm l假设每个假设每个Bi都是非终结符都是非终结符(若不是，则使用非终结符若不是，则使用非终结符Bi来代来代替替

23、Bi，并增加产生式，并增加产生式BiBi)AB1B2Bm若若m=2，满足了，满足了CNF要求；要求；m3，将它改造为，将它改造为m-1个产生式：个产生式：AB1B2Bm AB1C1 C1B2C2 Cm-3Bm-2Cm-2 Cm-2Bm-1Bml其中其中 C1，C2，Cm-2是新加的非终结符是新加的非终结符得到的文法得到的文法G是是CNF 且且L(G)=L(G)。证毕。证毕。5.2.2 Greibach范式(GNF)l定义定义5-8上下文无关文法上下文无关文法G=(，V，S，P)是是GNF，若，若G的每个产生式形式为的每个产生式形式为 AbW b，WV*定理5-7lG是是一一个个上上下下文文无无

24、关关文文法法，则则存存在在一一个等价的上下文无关文法个等价的上下文无关文法G，l使得使得L(G)=L(G)且且G中没有中没有直接左递归直接左递归的产生式，的产生式，即不存在即不存在AAv形式的产生式形式的产生式其中：其中：AV，v(UV)+。l没没有有直直接接左左递递归归的的文文法法也也称称为为无无直直接接左递归范式（左递归范式（NLR）。）。证明l见见2.7。l某些文法可能没有直接左递归，某些文法可能没有直接左递归，但可能会有但可能会有间接左递归间接左递归。定理定理5-8lG是一个上下文无关文法，则存在一是一个上下文无关文法，则存在一个等价的上下文无关文法个等价的上下文无关文法G，使得使得

25、L(G)=L(G)且且G中没有间接左递归的产生式。中没有间接左递归的产生式。l没有间接左递归的文法也称为无没有间接左递归的文法也称为无间接左递归范式。间接左递归范式。证明证明l见见2.7。定理5-9lG是是任任意意一一个个上上下下文文无无关关文文法法，则则存存在一个等价的上下文无关文法在一个等价的上下文无关文法G，使得使得L(G)=L(G)且且G是是Greibach范式范式(GNF)。l对对于于任任意意的的上上下下文文无无关关文文法法G，产产生生式形式为式形式为 AiAjw Aiaw或或假设假设w包含的字符全为非终结符包含的字符全为非终结符对于对于Aiaw，本身就是，本身就是GNF的形式的形式

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

27、文法是GNF范式范式构造一个单态的构造一个单态的PDA来接收语言来接收语言L；l文文法法G中中有有3种种形形式式的的产产生生式式，它它们们分分别对应别对应PDA的规则：的规则：S Ab AbW其中：其中：AV，WV+，需要证明需要证明语言语言L=L(PDA)。为证明之，先证明为证明之，先证明（*，w1w2，S）=*（*，w2，）iff S=*w1即扫描串后即扫描串后w1，M栈内符号串为栈内符号串为；若上述成立，假设若上述成立，假设w2=，则，则（*，w1，S）=*（*，）iff S=*w1l现在用归纳法证明现在用归纳法证明（对串（对串w1的长度进行归纳）的长度进行归纳）（*,w1w2，S）=

28、*（*,w2，）iff S=*w1证明证明基础：当基础：当w1=，有两种情况：，有两种情况：a）（）（*，w2，S）=*（*，w2，S）iff S=*S 是成立的；是成立的；b）若）若S在在G中，则有中，则有（*,w2，S）=*（*，w2，）iff S=*是成立的；是成立的；l假设：当假设：当w1时，长度为时，长度为n时；时；（*,w1w2，S）=*（*,w2，）iff S=*w1l令令=A，w2=aw3，（将将w1a当当作作新新的的w1，长度为长度为n+1），），则则l(*,w1aw3，S）=*（*,aw3，A）iff S=*w1Al而而（*，aw3，A）=（*，w3，）iff Aa因此因

30、*解法1：lread-match解法2：GNF=PDAl产生产生L的上下文无关文法：的上下文无关文法：S2|0S0|1S1将文法转化成GNF S2|0SA|1SB A0 B1构造单态PDA /S0SA /S1SB /S2 /A0 /B1定理定理5-11l对于单态的对于单态的PDA 存在一个上下文无关文法存在一个上下文无关文法G 使得使得L（G）=L(PDA)且且G为为GNF范式形式。范式形式。证明证明 PDA 文法文法 Ba Ba l根据单态的根据单态的PDA 可以得到对应的可以得到对应的GNF。而而多多态态的的PDA，不不可可以以直直接接得得到到GNF。问题问题多态多态PDA如何得到对应的上

31、下文无关文法如何得到对应的上下文无关文法？定理5-12l对对于于多多态态PDA，存存在在上上下下文文无无关关文法文法G，使得使得L(G)=L(M)。证明证明l构造上下文无关文法构造上下文无关文法G 思思路路为为用用文文法法的的一一个个推推导导模模拟拟PDA的一个动作的一个动作。l具体过程参考具体过程参考P135。对于对于多态PDAl得得到到对对应应的的上上下下文文无无关关文文法法的的产产生式具有如下的形式：生式具有如下的形式：AaA1A2An AA1A2An Aa A定理5-13l若若M是是多多态态的的PDA，则则存存在在一一个个单态单态PDA，使得，使得 L(PDA)=L(PDA)证明证明l

32、略。略。总之总之l对于一个对于一个PDA 存存在在一一个个上上下下文文无无关关文文法法G，使得使得L(M)=L(G)。注意注意确定确定PDA和不确定和不确定PDA不等价。不等价。例例构造构造PDA接收接收l语言语言L=w|wa,b*w中中a的个数为的个数为b的的2倍倍且且a必须成对出现必须成对出现思路：l将一个将一个a当作一个成对的当作一个成对的aa:构造上下文无关文法构造上下文无关文法G为：为：ZaCAZ|bBZ|AaCAA|bBbBB|aCCa有单态PDA：例5-16构造构造(广义广义)PDA接收接收语言语言 L=w|wa,b*且且w中中a的个数为的个数为b的的2倍倍考虑出栈情况基本

展开阅读全文