《计算理论04PDA_NCF教材》由会员分享，可在线阅读，更多相关《计算理论04PDA_NCF教材（28页珍藏版）》请在金锄头文库上搜索。
1、计算理论 wbfeng 今天课程 Chapter 2: 2.2 (Pushdown automata) 2.3 Non-CF languages 2.3 CFL pumping lemma Closure properties of CFL Date 1 计算理论 wbfeng 2.2 Pushdown Automata, ep101, cp66 Pushdown automata are for context-free languages what finite automata are for regular languages. PDA :描述CFL的设备 PDAs are recog
2、nizing automata that have a single stack (= memory): “硬件” 增加了栈 Last-In First-Out pushing and popping 对应于 可用 if ，goto, 读，和栈操作 的C程序 Difference: PDAs are inherently nondeterministic. (They are not practical machines.) 天生不确定 Date 2 计算理论 wbfeng Informal Description PDA (1) 与ep102， cp66 图稍有不同 input w = 00
3、100100111100101 内部状态集合 State set Q x y y z x stack The PDA M 读带 w and 且 作栈操作. Depending on - input wi ,输入字母表 - stack sj ,栈字母表 - state qk Q 状态集合 the PDA M: - jumps to a new state, - pushes an element (nondeterministically) Date 3 计算理论 wbfeng Informal Description PDA (2) ep102 input w = 00100100111100
4、101 internal state set Q x y y z x stack After the PDA has read complete input, M will be in state Q 当读完W且进入终止态， 则接受w, 栈用来作简单记 忆历史和对比， 只是栈顶元素可见，能力 有限，且不灵活 If possible to end in accepting state FQ, then M accepts w Date 4 计算理论 wbfeng Formal Description PDA定义2.8 ep103 形式化定义 cp67 A Pushdown Automata M
5、is defined by a six tuple (Q,q0,F), with Q finite set of states 有限个状态（寄存器） finite input alphabet 字母表 finite stack alphabet 可压栈字符表 q0 start state Q F set of accepting states Q 接受态 transition function 状态转移函数 相当于3种语句goto, push ,pop : Q P (Q ) Date 5 计算理论 wbfeng PDA for L = 0n1n | n0 ep104 cp67 例c3.9 Ex
6、ample e2.9 c3.9: 背景 检查左右括号(0,1)是否配对 The PDA first pushes “ $ 0n ” on stack. $ 栈底符号，压 箱钱 ，表示后来压入栈的存款用完了。 Then, while reading the 1n string, the zeros are popped again. 栈顶对比，左右括号配对，则同归于尽， If, in the end, $ is left on stack, then “accept” 下页释图 q1 q3 q2 q4 , $ , $ 1, 0 1, 0 0, 0 Date 6 计算理论 wbfeng PDA f
7、or L = 0n1n | n0 ep104 cp67 例c3.9 0-左括号，1右括号 q1读，栈顶变箱底钱 q2遇左括号0，压0栈入栈 q1 q3 q2 q4 , $ , $ 1, 0 1, 0 0, 0 弹出压箱钱，栈空 在q3 ,遇右括号1，弹出左括号，1，0兑消 在q2遇1，弹 出0, 兑消 绿框 表示 栈顶 字符 变化 Date 7 计算理论 wbfeng Machine Diagram for 0n1n ep103 cp67 例c3.9 q1 q3 q2 q4 , $ , $ 1, 0 1, 0 0, 0 例 接受 w = 000111 (state; stack) evolut
8、ion: (q1; ) (q2; $) (q2; 0$) (q2; 00$) (q2; 000$) (q3; 00$) (q3; 0$) (q3; $) (q4; ) This final q4 is an accepting state 练习 ，手写跟踪这一例题 状态 栈内值 Date 8 计算理论 wbfeng Machine Diagram for 0n1n ep 103 q1 q3 q2 q4 , $ , $ 1, 0 1, 0 0, 0 例 拒绝 w = 0101 (state; stack) evolution: (q1; ) (q2; $) (q2; 0$) (q3; $) (q
9、4; ) But we still have part of input “01”. There is no accepting path. 理解为用括号配对比较直观 状态 栈内值 Date 9 计算理论 wbfeng PDAs versus CFL ep106 ，cp 69， 计划自学内容 Theorem C3.12: A language L is context-free if and only if there is a pushdown automata M that recognizes L. L是CFL L被PDA接受 Two step proof: 1) Given a CFG
10、 G, construct a PDA MG 部分 2) Given a PDA M, make a CFG GM 部分 若干教材都说可以证明而略去证明，此书的证明 适合静心自学，不适合课堂讲解 或者承认结论， 读第二遍时再深入理解 Date 10 计算理论 wbfeng 2.3 Non-CF Languages ep115 cp74 先讲思想 The language L = anbncn | n0 does not appear to be context-free. 这个语言不是CFL证 明此事需要新的泵定理（言多必重复） Informal: The problem is that ev
11、ery variable can (only) act by itself (context-free). 比喻：前后文无关的人格，我行我素，不受舆论左右， 两岸猿声啼不住，轻舟已过万重山，则某些爱好和行为就 会重复 The problem of A * vAy : If S * uAz * uvAyz * uvxyz L, then S * uAz * uvAyz * * uviAyiz * uvixyiz L as well, for all i=0,1,2, Date 11 计算理论 wbfeng “Pumping Lemma c3.19 for CFLs” ep115 与RL不同，CF
12、L 两处打圈，至少一处是真圈， 先讲思想 Idea: If we can prove the existence of derivations for elements of the CFL L that use the step A * vAy, then a new form of v-y pumping holds: A * vAy * v2Ay2 * v3Ay3 * ) 要点：证明存在如上的 “中递归” 派生，反复调用 Observation: We can prove this existence if the parse-tree is tall enough. 当派生树足够高，用
13、尽了资源，就会出现重复 Date 12 计算理论 wbfeng Remember Parse Trees ep 116 cp75 ，先讲思想 Parse tree for S AbbcBa * cbbccccaBca cbbccccacca 当树足够高时，有限的变量符就会被重复使用 S b b ac A c c ca A c c c B B Date 13 计算理论 wbfeng Pumping a Parse Tree ep116 ，先讲思想 A A uvxyz If s = uvxyz L is long, then its parse-tree is tall. Hence, there
14、 is a path on which a variable A repeats itself. We can pump this AA part. S 路径高度超 过变量个数 时，至少一 个变量符号 被重复 Date 14 计算理论 wbfeng A Tree Tall Enough ep116 cp75，先讲思想 Let L be a context-free language, and let G be its grammar with maximal b symbols on the right side of the rules: A X1Xb A parse tree of dep
15、th h produces a string with maximum length of bh. Long strings implies tall trees. Let |V| be the number of variables of G. If h = |V|+2 or bigger, then there is a variable on a top-down path that occurs more than once. 变量个数V 树高h=v+2时 Date 15 计算理论 wbfeng uvxyz L 派生树足够高，分段记号, ep116 cp75 A A uvxyz By repeating the AA part we get S 期待的 中递归 Date 16 计算理论 wbfeng uv2xy2z L , i=2 ep116 在上页基础上A再自己派生一次，先讲思想 A u v x y z R A A vx y while removing the A-A gives S Date 17 计算理论 wbfeng uxz L, i=0, ep116 cp
