下推自动机

第五章下推自动机PDAFA识别正则语言(右线性语言)PDA识别上下文无关语言FA只能处理正则语言正则文法生成无穷语言是由于A-wA不需要记录w的个数无关文法生成无穷语言A-αAβ需要记录α和β之间的对应关系无法用FA的有穷个状态来表示。为FA扩充一个无限容量的栈用栈的内容和FA的状态结合起来就可以表示无限存储。这种模型就是下推自动机PDAPDA作为形式系统最早于1961年出现在Oettinger的论文中。与上下文无关文法的等价性由Chomsky于1962年发现。与FA比较PDA具有一个栈存储器有两个操作：入栈---将内容压入栈中出栈---将栈顶元素移出下推自动机物理模型a1a2a3…aj…anan+1…FSC…存储带栈存储器栈存储器存放不同于字母的符号只能对栈顶元素进行操作。下推自动机动作根据FSC当前的状态输入带上的当前字符栈顶符号进行状态改变和入栈或出栈操作将读头向右移动一个单元5.1.1确定的下推自动机例5-1语言L={w|w∈(a,b)*，且a、b个数相等}暂时不考虑状态(或PDA仅有一个状态)初始栈为空从左到右逐个扫描串w∈(a，b)*入栈若栈为空,当前符号是a,则A入栈若栈为空,当前符号是b,则B入栈若栈顶为A,当前符号是a,则A入栈若栈顶为B,当前符号是b,则B入栈出栈若栈顶为A,当前符号是b，则A出栈若栈顶为B,当前符号是a，则B出栈若串w有相同个数的a和b当且仅当w扫描结束后，栈为空。注意PDA在两种情况下停机：串扫描结束没有对应的规则串扫描结束栈如果为空就接收扫描过的串。对于非正式的算法，用形式化的方式进行描述：特殊的符号Z0表示栈底初始化时先压入栈x，D，V规则(指令)若x是w的当前符号D是栈顶符号则用符号串V代替D即将D弹出栈，而将串V压入栈具体若x是w的当前符号，栈顶符号为Dx，D，ε将D弹出栈x，D，AD将A压入栈，成为新的栈顶一般地若x是w的当前符号，栈顶符号为Dx，D，A1A2…Ak表示：将D弹出栈将串A1A2…Ak压入栈(A1为新栈顶)例5-1算法的形式化描述a，Z0，AZ0b，Z0，BZ0a，A，AAb，B，BBa，B，εb，A，εε，Z0，ε规则ε，Z0，ε表示将w扫描结束后，将栈置成空也表示该PDA可以接收空串ε思考：如何接收语言L={w|w∈(a,b)+,且a和b个数相等}?例：语言L={anbn|n≥0}定义：a，Z0，AZ0a，A，AAb，A，εε，Z0，ε则还可以接收语言{(ab)n|n≥0}，或{ambm(ab)n|m≥0,n≥0}等语言。思考：如何接收语言L={anbn|n0}L={anbn|n≥0}L={(ab)n|n0}L={(ab)n|n≥0}例5-2L={wcwT|w∈(a，b)*}识别语言思想：将w的各个字符压入栈后栈中的内容从栈顶到栈底的顺序刚好是wT的顺序为了区别压栈和出栈动作增加两个状态----read和matchPDA处于read状态时，处理整个串的前半部分，将对应的符号压入栈扫描到字母c时PDA的状态转为match开始处理整个串的后半部分，将栈中的内容出栈。规则q，x，D，q′，V若PDA处于状态qw的当前字母是x当前栈顶符号为D则自动机的状态改变为q′并用符号串V代替D（在本例中）用Z代表任意的栈顶符号规则〈read，a，Z，read，AZ可以表示以下3条规则：〈read，a，Z0，read，AZ0〈read，a，A，read，AA〈read，a，B，read，AB用下列的规则来描述PDA〈read，a，Z，read，AZ〈read，b，Z，read，BZ〈read，c，Z，match，Z〈match，a，A，match，ε〈match，b，B，match，ε〈match，ε，Z0，match，ε若串w是该语言的合法的串当且仅当w扫描结束后，栈为空。Z0符号栈串abbcbba的处理过程ABreadmatch=B扫描到字母c栈内的内容（从栈顶到栈底）是扫描过的串的逆与未扫描过的串的顺序相同此时，不作出栈和入栈操作，仅仅把PDA的状态从read改变到match。接收语言L={anbn|n0}〈q0，a，Z0，q0，AZ0〈q0，a，A，q0，AA〈q0，b，A，q1，ε〈q1，b，A，q1，ε〈q1，ε，Z0，q1，ε5.1.2不确定的下推自动机例5-3语言L={wwT|w∈(a,b)*}没有中心点字符在扫描过程中，就没有确定的位置进行状态的变换具有不确定性。使用规则〈read，ε，Z，match，Z来代替〈read，c，Z，match，Z即在read状态时，可随时改变为match状态（栈的内容和扫描符号不变）〈read，a，Z，read，AZ〈read，b，Z，read，BZ〈read，ε，Z，match，Z〈match，a，A，match，ε〈match，b，B，match，ε〈match，ε，Z0，match，ε该PDA是不确定的处于状态read状态时随时都可以进行选择:继续扫描，或状态变换为match一个串w能够由PDA所识别：仅当串是wwT的形式且PDA状态在中心点进行了变换对于不确定的PDA和串w若存在至少一个可能的扫描过程使得当串w扫描结束时，栈为空则称串w能够被PDA所识别。接收语言L={(ab)n|n≥0}〈q1，a，Z0，q2，AZ0〈q2，b，A，q1，ε〈q1，ε，Z0，q1，ε〉接收语言L={(ab)n|n0}〈q0，a，Z0，q0，AZ0〈q0，b，A，q1，ε〈q1，a，Z0，q2，AZ0〈q2，b，A，q1，ε〈q1，ε，Z0，q1，ε定义5-1下推自动机PDA是一个七元式：M=(Q，∑，Г，δ，q0，Z0，F)Q是一个有限状态的集合∑是输入串的字母集合Г是栈内符号集合q0∈Q是开始状态Z0∈Г是栈底符号FQ是接收状态集合δ：Q×(∑∪{ε})×Г→Q×Г*对于确定的PDA，有δ（q，x，D）=(q′，V)对于不确定的PDA，有(q′，V)∈δ（q，x，D）一般使用q，x，D，q′，V表示δ函数定义5-2PDA格局(或瞬间描述ID)格局代表某个时刻PDA的情况PDA的格局是一个三元式(q，w，σ)其中，q为状态w=x1x2…xn还没有被扫描到的串(将扫描x1)σ=Z1Z2…Zm栈的内容(Z1在栈顶，Zm在栈底)PDA初始格局为(q0，w，Z0)接收格局为(q，ε，ε)其中:q∈Q（与接收状态无关）格局的转换是由于状态转换函数的作用引起的确定的PDAq，x，A，q1，A1A2…Ak引起的格局转换为：(q，xw，Aσ)=(q1，w，A1A2…Akσ)不确定的PDA（情况1）①q，x，A，q1，A1A2…Ak则(q,xw,Aσ)=(q1，w,A1A2…Akσ)②q，ε，A，q2，B1B2…Bj则(q,xw,Aσ)=(q2，xw，B1B2…Bjσ)不确定的PDA（情况2）①q，x，A，q1，A1A2…Ak则(q,xw,Aσ)=(q1，w，A1A2…Akσ)②q，x，A，q2，B1B2…Bj则(q,xw,Aσ)=(q2，w，B1B2…Bjσ)用=*代表格局的任意次变换不确定PDA对于某一格局可能会有不同的下一格局。5.1.3PDA接收语言的两种方式定义5-3PAD以空栈方式接收的语言为L(M），且L(M)={w|(q0，w，Z0)=*(q,ε,ε)q∈Q}接收格局与接收状态无关只要当串w扫描结束，而栈为空则串w被PDA以空栈方式所接收。定义5-4PAD以终态方式接收的语言为F(M)，且F(M)={w|(q0,w，Z0)=*(q′,ε,σ)q′∈F,σ∈Г*}接收格局与栈是否为空无关只要当串w扫描结束，而PDA处于某个接收状态则串w被PDA以终态方式所接收。定理5-1语言L被PDA以终态方式所接收当且仅当它被PDA以空栈方式所接收。即终态接收与空栈接收方式等价。证明：略5.1.4广义PDA和单态PDA定义5-5广义的PDA是七元式PDA=(Q,∑，Г，δ，q0，Z0，F)（除了δ外，其余同一般的PDA）其中Q是一个有限状态的集合∑是输入串的字母集合Г是栈内符号集合q0∈Q是开始状态Z0∈Г是初始的栈底符号FQ是接收状态(终止状态)集合δ：Q×(∑∪{ε})×Г+→Q×Г*(q，x，B1B2…Bk)=(q′，C1C2…Cn)一般形式为q，x,B1B2…Bk，q′，C1C2…Cn一般的PDA，栈顶只是一个符号广义PDA的栈顶可以为多个符号。定理5-4若语言L能由广义PDA所接收则L能够由一般的PDA所接收。证明思路广义的PDA的一条规则一般PDA的多条规则的组合就是证明：对于广义的PDA的任意一条规则q,x,B1B2…Bk，q′，C1C2…Cn增加状态r1，r2，…，rk-1，q，x，B1B2…Bk，q′，C1C2…Cn改造为：q，x，B1，r1，εr1，ε，B2，r2，ε…rk-1，ε，Bk，q′，C1C2…Cn得到一般的PDA′且L=L(PDA′)。定义5-6单态PDA仅有一个状态的PDA规则简化为x，D，V(等价性)问题一个NFA是否可以转换为一个单态PDA？思路NFA=（Q，∑,δ，q0，F）将NFA的状态当作PDA的栈内符号构造单态的PDA=（{*}，∑，Q，δ′，*，q0，{*})NFA：δ(q，x)={q1，q2，…qn｝单态的PDA：x，q，q1x，q，q2…x，q，qnNFA：若q∈δ*(q0，w)单态的PDA：有（*，w，q0）=*（*，ε，q）NFA：若δ(q，x)∩F≠ф单态的PDA：x，q，ε因此NFA：δ*(q0，w)∩F≠ф单态的PDA：（*，w，q0）=*（*，ε，ε）即L(NFA)=L(PDA)右线性文法G=（∑，V，S，P）也可以对应一个单态的PDA，产生式A→bBA→bPDA的规则b，A，Bb，A，ε将文法的开始符号S当作是单态PDA的栈底符号，则对于文法GS=*w1A=w1bB=*w1bw2=w对于单态PDA(*，w1bw2，S)=*(*，bw2，A)=(*，w2，B)=*(*，ε，ε)例5-4语言L={anbn|n≥1}文法S→aSBS→aBB→ba，S，SBa，S，Bb，B，ε单态PDA对于串anbn，单态的PDA可能会有以下的格局转换：①(*，anbn，S）=n(*，an-jbn，SBj）②(*，anbn，S）=n（*，an-kbn，Bk）③(*，anbn，S）=n（*，bn，Bn）其中：①是导出②和③的中间过程；②会导致停机，因为没有合适的规则a，B，？③可以完成最后的转换：（*，bn，Bn）=*（*，ε，ε）使用n-1次规则a，S，SB1次规则a，S，Bn次规则b，B，ε5.1.5下推自动机的存储技术参考Turing的存储技术。略5.1.6PDA扫描多个符号参考Turing的扫描多个符号技术。略5.2上下文无关文法和范式范式是指标准的形式在代数中，2/4，3/6，…的范式是1/2。本节讨论在上下文无关文法的几个重要的范式。定理5-5G是一个上下文无关文法，则存在一个上下文无关文法G′，使得：①L(G)=L(G′)②若ε≠L(G)，则G′没有空串产生式③若ε∈L(G)，则G′有S′→ε，且S′不出现在G′的任何产生式的右边④G′中没有A→B形式的产生式。证明前3点是空串定理的内容(见2.6)第4点证明参见参考文献1。5.2.1Chomsky范式(CNF)定义5-7上下文无关文法G=(∑，V，S，P)若G的每个产生式是下列形式之一：A→BCA，B，C∈VA→aA∈V，a∈∑S→ε且S不出现在产生式的右边则G是Chomsky范式(CNF)。定理5-6G是一个上下文无关文法，则存在一个等价的上下文无关文法G′使得L(G)=L(G′)，且G′是CNF。证明对于任