计算理论第2章_去某范式版.pptVIP

拒绝 w = 0101 （状态；堆栈）的变化过程： (q1; ?) ? (q2; $) ? (q2; 0$) ? (q3; $) ? (q4; ?) … 虽然具有输入的部分子串 “01”，但找不到整个字符串的接受路径 理解为用括号配对比较直观 状态 栈内值 q1 q3 q2 q4 ?, ??$ ?, $?? 1, 0?? 1, 0?? 0, ??0 w = 0101 例：构造一台识别下述语言的PDA M：｛aibjck ? i, j, k≥0 且 i=j 或 i=k} 例 例 ： 构造接受L={wwT|w∈{0,1}*}的PDA。 确定的(deterministic)PDA PDA在每一个状态q和一个栈顶符号下的动作都是惟一的。 关键 对于?(q，Z)∈Q×Γ，M此时如果有非空移动，就不能有空移动。 每一种情况下的移动都是惟一的。 非确定的PDA和确定型PDA识别能力不同，非确定型PDA能识别确定型PDA不能识别的语言 2.2.3与上下文无关文法的等价性 定理２.12: 一个语言是上下文无关的，当且仅当存在一台PDA识别它。 L是CFL ??L被PDA接受 两步: 1)引理２.１３ 如果一个语言是上下文无关的，则存在一台PDA识别它 ?部分 2)引理２.１5 如果一个语言被一台PDA识别，则它是上下文无关的 ?部分 若干教材都说 此定理容易证明 但又略去证明，此定理的证明 适合静心自学，不适合课堂讲解 。 可以先承认结论， 读第二遍时再深入理解 引理2.13 的证明（１） 引理2.13 如果一个语言是上下文无关的，则存在一台下推自动机识别它。 证明思路 设A 是CFL，根据定义，存在一个CFG G产生它。说明如何把G转换成一台等价的PDA P。 确定是否存在关于输入w的派生PDA P当G产生w时，接受这个输入。 派生是当文法产生一个字符串时的替换序列，派生的每一步产生一个变元和终结符的中间字符串。 设计P，以确定是否有一系列使用G的规则替换，能够从起始变元导出w 检验是否有关于w的派生。 困难在于判断要替换， PDA的非确定性使得它能够猜想出正确的替换序列， 在派生的每一步，非确定地选择关于某个变元的一条规则，并且对这个变元做替换。 P的非形式描述如下： 1) 把标记符$和起始变元放入栈中； 2）重复下述步骤： 如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串； 如果栈项是终结符a，则读输入中的下一个符号，并且把它与a进行比较。如果它们匹配，则重复，如果它们不匹配，则这个非确定性分支拒绝； 如果栈顶是符号$，则进入接受状态，如果此刻输入已全部读完，则接受这个输入。 1）初始化栈，把符号$和S推入栈； 2） a)栈顶是个变元；令δ(qloop, ?, A)＝{(qloop, w) ? A? w是R中的一条规则} b)栈顶是个终结符。令δ(qloop, a, a)＝ δ(qloop, ?) c)栈顶是空栈标记符$。令δ(qloop, ?, $)＝{(qaccept, ?) } CFG G 转换成PDA P例：把下述CFG G转换成一台PDA： S?aTb ? b T?Ta ? ?  引理2.15的证明（１）自学 引理2.15 如果一个语言被一台下推自动机识别，则它是上下文无关的。 证明思路 现有一台PDA P，要构造一个CFG G，它产生P接受的所有字符串。换言之，如果一个字符串能使P从它的起始状态转移到一个接受状态，则G应该产生这个字符串。 为了获得这个结果，我们设计一个能做更多事情的文法。对于P的每一对状态p和q，文法有一个变元Apq。它产生所有能够把P从p和空栈一块带到q和空栈的字符串。可以看出不管栈的内容是什么，这样的字符串也能够把P从p带到q，并且保持栈的内容在状态q和在状态p时—样。 引理2.15 的证明（２） 为简化工作，对P作修改，使其具有以下三个特点。 1）有唯一的接受状态qaccept 。 2）在接受之前清空栈。 3）每一个转移把一个符号推入栈(推入动作)，或者把一个符号弹出栈(弹出动作)，但不同时做这两个动作。 使P具有特点1和2较容易，使P具有特点3就要把每一个同时弹出和推入的转移替换成两个转移，中间要经过一个新的状态；把每一个既不弹出也不推入的转移替换成两个转移，先推入任意一个栈符号，然后再把它弹出。 引理2.1５ 证明（3） 设计G，使得Apq产生把P从p带到q并且以空栈开始和结束的所有字符串，了解P对这样的字符串如何运行。 对于任一的字符串x