第七章：下推自动机.ppt

7.1 基本定义 δ3(q1，2，A)={(q2，A)} 状态转移 δ3(q1，2，B)={(q2，B)} δ3(q2，0，A)={(q2，ε)} δ3(q2，1，B)={(q2，ε)} 匹配 δ3(q2，0，B)={(qt，ε)} （正确、错误） δ3(q2，1，A)={(qt，ε)} δ3(q2，ε，Z0)={(qf，ε)} 终止 此时有：N(M3)=L(M3)=L。 7.1 基本定义 M3=({q0，q1，q2，qf，qt}，{0，1，2}，{ A，B， Z0}，δ3，q0，Z0，{qf}) M4=({q0，q1，q2 }，{0，1，2}，{ A，B， Z0}，δ4，q0，Z0，Φ) 7.1 基本定义 不追求让PDA同时用终止状态和空栈接受同样的语言，还可以删除状态qf。这样我们可以得到PDA M4 。 M4=({q0，q1，q2 }，{0，1，2}，{ A，B， Z0}，δ4，q0，Z0，Φ) δ4(q0，0，Z0)={(q1，A)} δ4(q0，1，Z0)={(q1，B)} 起始 δ4(q0，2，Z0)={(q2，ε)} 7.1 基本定义 δ4(q1，0，A)={(q1，AA)} δ4(q1，1，A)={(q1，BA)} 记录 δ4(q1，0，B)={(q1，AB)} δ4(q1，1，B)={(q1，BB)} δ4(q1，2，A)={(q2，A)} 状态转移 δ4(q1，2，B)={(q2，B)} δ4(q2，0，A)={(q2，ε)} 匹配 δ4(q2，1，B)={(q2，ε)} 7.1 基本定义 思考：是否可以q2让作为终止状态。 7.1 基本定义 思考：构造一个PDA用来识{ω2ω|ω∈{0,1}*} 事实上不可能的，首先在栈内变量的倒序是不可能的；其次，该语言不是CFL具体证明过程在第八章。 确定的(deterministic)PDA ?(q，a，Z)∈Q×∑×Γ |δ(q，a，Z)|+|δ(q，ε，Z)|≤1 PDA在每一个状态q和一个栈顶符号下的动作都是惟一的。 关键 对于?(q，Z)∈Q×Γ，M此时如果有非空移动，就不能有空移动。 每一种情况下的移动都是惟一的。 7.1 基本定义 例 7-2 构造接受L={ωωT|ω∈{0,1}*}的PDA。 差异 δ(q0，0，A)={(q0，AA)，(q1，ε)} 0是w中的0或者是wT的首字符0； δ(q0，1，B)={(q0，BB)， (q1，ε)} 1是w中的1或者是wT的首字符1。 具体的状态转移函数δ参考课本P200 7.1 基本定义 思考：如何判断进入匹配状态。 7.2 PDA与CFG等价 在证明PDA与CFG等价之前，我们要先证明 对于任意PDA M1，存在PDA M2，使得L(M2)=N(M1)； 对于任意PDA M1，存在PDA M2，使得N (M2)= L (M1)。 注意：是任意一个而不是同一个PDA存在N (M1)= L (M1)。 CFL可以用空栈接受语言的PDA接受。 PDA接受语言可以用CFG描述。 7.2 PDA与CFG等价 证明思路： 1、证明PDA与CFG等价 2、先证明 对于任意的PDA存在L(M2)=N(M1)或者N (M2)= L (M1)即：PDA用空栈接受和用终止状态接受等价。 3、证明上面的命题，先构造等价的PDA 7.2.1 PDA用空栈接受和用终止状态接受等价 定理 7-1 对于任意PDA M1，存在PDA M2，使得N (M2)= L (M1)。 证明要点：构造等价的运转状态 注意两个问题 1.当ω引导M1进入终止状态后，M1的栈不空，此时M2必须将栈清空，以达到接受状态。 2.M1在运行的过程中没有进入终止状态，但是此时的栈已经空，M2要能够避免出现这种状况时出现误接受。（解释） 解决办法：需要引入一个状态，解决问题1，它来完成清栈工作。 7.2.1 PDA用空栈接受和用终止状态接受等价 解决办法：还需要一个状态和栈符号来解决问题2，M1未进入终止状态而栈已空的M2误接受。 （1） 构造：在已知M1的基础上构造M2 设PDA M1 = (Q，∑，Γ，δ1，q01，Z01，F) 取PDA M2 = (Q∪{q02，qe}，∑，Γ∪{Z02}，δ，q02，Z02，F) 其中Q∩{q02，qe}=Γ∩{Z02}=Φ。 7.2.1 PDA用空栈接受和用终止状态接受等价 .δ2(q0