1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory胡春明胡春明 邓婷邓婷 赵永望赵永望第第七七章章 下推自动机下推自动机2第七章第七章 下推自动机下推自动机 下推自动机（下推自动机（ PDA ）下推自动机的构造下推自动机的构造PDA 两种接受语言方式的等价两种接受语言方式的等价确定的下推自动机（确定的下推自动机（DPDA）PDA 与与 CFG 等价等价第七章第七章 下推自动机下推自动机正则文法与有穷状态自动机正则文法与有穷状态自动机 例：构造与给定右正则文法等价的例：构造与给定右正则文法等价的 FA。M=(Q, , , q0, F, ),Q
2、=E, A, B, C, Z =0,1 (E, 0)=A, (E, 1)=B, (A, 1)=Z, (A,1)=C, (B, 0)=Z, (B, 0)=C, (C, 0)=B, (C, 1)=A F=Z文法及机器：文法及机器：有有穷状态自动机穷状态自动机(FA) - 正则语言正则语言(RL)下推自动机下推自动机(PDA) - 上下文无关语言上下文无关语言(CFL)上下文无关文法与下推自动机上下文无关文法与下推自动机（ PDA ）PDA提出的思路：提出的思路： 对于对于CFG, 当它是当它是GNF的时候的时候, 派生总是从左往右进行派生总是从左往右进行, 而且右边变量而且右边变量后缀的长度是不定
3、的后缀的长度是不定的,想用有穷状态来表示这些后缀不一定总是可能的。想用有穷状态来表示这些后缀不一定总是可能的。 按照最左派生来分析句子的情况下按照最左派生来分析句子的情况下,可以考虑用可以考虑用栈栈来保存来保存A a, A aA1A2 Am 定义定义 6 - 12： 如果如果 CFG G =（V, T, P, S）中所有产生式都有如下形式：）中所有产生式都有如下形式：A a ，其中，其中， A V ，a T， V ，则则 G 被称为格雷巴赫范式（被称为格雷巴赫范式（ GNF ）AmA2A1PDA 装置模型装置模型PDA的动作的动作 在有穷状态控制器的控制下根据它的在有穷状态控制器的控制下根据它
4、的当前状态、栈顶当前状态、栈顶符号、以及输入符号符号、以及输入符号作出相应的作出相应的动作动作有时有时,不不需要考虑输入需要考虑输入符号符号为何为何称下称下推自推自动机？动机？存放输入符号串存放输入符号串的的输入带输入带存放文法符号的存放文法符号的栈栈有穷状态有穷状态控制器控制器格雷巴赫范式：格雷巴赫范式：S 2 | 0SA | 1SB A 0 B 1接受串：接受串：110020011S 1SB 11SBB 110SABB 1100SAABB 11002AABB 110020ABB 100200BB 11002001B 110020011PDA 装置执行过程举例装置执行过程举例SBSBBSBB
5、ASBBAABBABBBBBAAS最左派生 定义定义 7-1：下推自动机：下推自动机(pushdown automaton, PDF) 是一个七元组是一个七元组 M = ( Q, , , , q0, Z0, F ), 其中其中 Q: 状态的非空有穷集合；状态的非空有穷集合； : 输入字母表；输入字母表； : 栈字母表；栈字母表； q0: 初始状态初始状态, （ q0 Q） ； Z0: 开始符号开始符号 或栈或栈底底符号符号,（ Z0 ）； F: 终止状态终止状态集合集合, F Q; : 状态转移函数状态转移函数,Q ( ) 2Q * 。对于对于 ( q, a , Z ) Q ( ) 1、 (
6、q, a, Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) 2、 ( q, , Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) 下推自动机（下推自动机（ PDA ）1、 ( q, a, Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) 在在状态状态 q下下, 栈栈顶符号为顶符号为 Z, 读入读入字符字符 a 时时, M 可选择将状态可选择将状态变为变为 pi （i =1, 2, , m,） 栈栈顶符号顶符号 Z 弹弹出出,将将 i 中的符号中的符号从右到左从右到左依此压入依此压入栈栈, 将将读头向右移
7、动一个读头向右移动一个字符字符, 指向指向输入串的下一个字符输入串的下一个字符。 下推自动机（下推自动机（ PDA ）-状态转移函数状态转移函数约定：约定： 1） i 的最左边符号被置于栈的最高位置；最右符号在最低位置上的最左边符号被置于栈的最高位置；最右符号在最低位置上。 2）在一个动作中不允许同时选择状态在一个动作中不允许同时选择状态 pi 和符号串和符号串 j , i j。piq aaZ i i= bcdbcd 2、 ( q, , Z ) = ( p1, 1 ), ( p2, 2 ), , ( pm, m ) M 进行一次空移动进行一次空移动：状态：状态为为 q, 栈顶符号为栈顶符号为Z
8、时时未未对任何输入字符进行对任何输入字符进行扫描扫描,也也可选择将状态变为可选择将状态变为 pi ( i=1, 2, , m)将将栈顶符号栈顶符号 Z 弹弹出出,将将 i 中的符号从右到左依此压入中的符号从右到左依此压入栈栈,输入输入头不向头不向前移动。前移动。 约定：约定： 1） i 最左边符号被置于栈的最高位置；最右符号在最低位置上。最左边符号被置于栈的最高位置；最右符号在最低位置上。 2）在一个动作中不允许同时选择状态）在一个动作中不允许同时选择状态 pi 和和 符号串符号串 j , i j。下推自动机（下推自动机（ PDA ）-状态转移函数状态转移函数piq aaZ i下推自动机（下推
9、自动机（ PDA ）约定约定 - 按以下方式规定按以下方式规定 PDA 中符号：中符号：英文字母较前面的英文字母较前面的小写字母小写字母,如如 a,b,c,表示表示输入符号输入符号；英文字母较后面英文字母较后面的小写字母的小写字母,如如 x,y,z,表示表示输入符号串输入符号串;英文字母表的英文字母表的大写字母大写字母,如如 X, Y, Z, , 表示堆栈中符号表示堆栈中符号;西腊字母西腊字母 , , ,表示表示堆栈中符号串堆栈中符号串。2、空动作（称为空动作（称为 动作动作 - 没有输入符号）没有输入符号）： ( q2, , R ) = ( q2, ) 1、非空动作非空动作（有输入符号）有输
10、入符号）： ( q1, 0, R ) = ( q1, BR ) ( q1, c, R ) = ( q2, R ) ( q1, 0, B ) = ( q1, ) ( q1, 0, ) = ( q1, R ) 把把R压进压进栈顶栈顶下推自动机（下推自动机（ PDA ）弹出栈顶符号弹出栈顶符号 R, BR 压入栈压入栈 改变控制器改变控制器状态状态弹弹栈栈弹栈。弹栈。下推自动机多种转移动作举例：下推自动机多种转移动作举例：PDA 的两个基本概念：的两个基本概念： 1、瞬时描述；、瞬时描述； 2、PDA 接受的句子方式接受的句子方式下推自动机（下推自动机（ PDA ）定义定义 7 - 2： 设设 PD
11、A M = ( Q, , , , q0, Z0, F ), ( q, w, ) ( Q, *, *) 称为称为 M 的一的一个即时描述个即时描述 (instantaneous description, ID),下推自动机（下推自动机（ PDA ）lq是控制器的当前状态是控制器的当前状态lw 是当前尚未处理的输入字符串是当前尚未处理的输入字符串。 M 在状态在状态 q 下下,正注正注 视视输入字符串输入字符串 w 的首的首字符字符,l栈栈中符号串为中符号串为 , 的的最左最左符号为栈顶符号为栈顶符号符号, 最最右符号为栈底右符号为栈底符号符号,较左的符号在栈的较上面较左的符号在栈的较上面, 较右
12、的符号在栈的较下面较右的符号在栈的较下面qab = bcdcdbcw = abc下推自动机（下推自动机（ PDA ）：）：即时转移描述即时转移描述(1) 如果如果（p, ） （ q, a, Z ）, 且且M 在状态在状态 q, 栈栈顶为顶为 Z,读读 入入 a 时时 , 选择选择进入状态进入状态 p, 用用 替换栈顶替换栈顶 Z, 读读头指向头指向 w 的的首首字符字符,记记为：为： （q, aw, Z ） （p, w, ）此时此时, M 做了一次做了一次非空非空移动移动,其其 ID 由由（ q, aw, Z ）变为变为 （p, w, ）。Mpq aaZ w =bcde b c d e b c
13、 d e(2) 如果如果（p, ） （ q, , Z ）, 表示当前表示当前 M 在状态在状态 q,栈栈顶为顶为 Z时时,不不读读字符字符,选择选择进入状态进入状态 p,用用 替换栈顶替换栈顶 Z,读读头位头位置置不变不变,记记为：为： （q, w, Z ） （p, w, ）此时此时, M 做了一次做了一次空空移动移动, 其其 ID 由（由（ q, w, Z ） 变为变为 （p, w, ）。）。Mpq aaZ w=abcde b c d e b c d e下推自动机（下推自动机（ PDA ）:瞬时转移序列描述瞬时转移序列描述（ q1, w1, 1 ） （qn, wn, n ）：）：表示表示 M
14、 的的 ID 从（从（ q1, w1, 1 ）出发出发, 经过经过 n 次次移动移动, 变为变为 (qn, wn, n ), 亦即亦即, 存在存在一个一个 ID 序列：序列： （ q1, w1, 1 ） （ q2, w2, 2） . （qn, wn, n ）其中其中, 对于对于字符串字符串 w1, w2, wn, 当当 i j 时时, w j 是是 w i 的后缀的后缀。nMMMM下推自动机（下推自动机（ PDA ）:特殊的瞬时转移序列描述特殊的瞬时转移序列描述 这里这里,1、字符串、字符串 x 是是w 的后缀；的后缀；（ q, w, ） （ p, x, ）：）：表示表示 M 的的 ID 从（
15、从（ q, w, ）出出发发, 经过经过若干次（包含零次）若干次（包含零次）移动移动,变成变成（ p, x, ）M（ q, w, ） （ p, x, ）：）：表示表示 M 的的 ID 从（从（ q, w, ）出发出发,经经过过至少一次至少一次移动移动,变成变成（ p, x, ）+Mn2、意义清楚、意义清楚时时,可可省去省去 ID 推导符中的推导符中的 M, 分别分别记为：记为：两个基本概念：两个基本概念： 1、PDA 的瞬时描述；的瞬时描述； 2、PDA 接受的句子方式接受的句子方式下推自动机（下推自动机（ PDA ）下推自动机（下推自动机（ PDA ）定义定义 7 - 3： 设有设有PDA
16、M=(Q, , , , q0, Z0, F ), 则则M具有具有两种接受语言的两种接受语言的方式方式: 1、用、用终态方式终态方式接受接受语言语言, 定义定义为：为： L(M)= w | ( q0, w, Z0 ） ( p, , ) 且且 p F ； * 2、 用用空栈方式空栈方式接受接受语言语言,定义定义为：为： N(M)= w | ( q0, w, Z0） ( p, , ) *到达终止状态,栈不一定为空栈为空,不一定到达终止状态例：例：构造接受语言构造接受语言 L = w2wR | w 0,1* 的的 PDA。二、下推自动机的构造二、下推自动机的构造解：解：1、构造产生、构造产生 L 的的
17、 CFG G1：S 0S0 | 1S1 | 2。 2、将文法、将文法 G1 转换成转换成格雷巴赫范式格雷巴赫范式（ GNF ） G2： S 0SA | 1SB | 2 A 0 B 1根据根据 GNF 定义各种识别语言定义各种识别语言 L 的的 PDA 。解解1：构造空栈方式接受语言的：构造空栈方式接受语言的 PDA G2： S 0SA | 1SB | 2A 0B 1派生派生产生规则产生规则M应该完成的动作应该完成的动作S0SAS0SA从从q0启动启动,读入读入0,将将S弹出栈弹出栈,将将SA压入栈压入栈,状态不变状态不变01SBAS1SB在状态在状态q0,读入读入1,将将S弹出栈弹出栈,将将S
18、B压入栈压入栈,状态不变状态不变 010SABA S0SA在状态在状态q0,读入读入0,将将S弹出栈弹出栈,将将SA压入栈压入栈,状态不变状态不变0102ABA A0在状态在状态q0,读入读入2,将将S弹出栈弹出栈,将将压入栈压入栈,状态不变状态不变01020BAB1在状态在状态q0,读入读入0,将将A弹出栈弹出栈,将将压入栈压入栈,状态不变状态不变010201AA0在状态在状态q0,读入读入1,将将B弹出栈弹出栈,将将压入栈压入栈,状态不变状态不变0102010在状态在状态q0,读入读入0,将将A弹出栈弹出栈,将将压入栈压入栈,状态不变状态不变模拟模拟 PDA M1识别句子识别句子 0102
19、010 过程：过程：1(q0,0,S)=(q0,SA)1(q0,1,S)=(q0,SB)1(q0,0,S)=(q0,SA)1(q0,2,S)=(q0,)1(q0,0,A)=(q0,)1(q0,1,B)=(q0,)1(q0,0,A)=(q0,)G2： S 0SA | 1SB | 2A 0B 1解解1：构造空栈方式接受语言的：构造空栈方式接受语言的 PDA PDA M1 = ( q0 , 0, 1, 2 , S, A,B , 1, q0, S, ) 。 1(q0,0,S)=(q0,SA)1(q0,1,S)=(q0,SB)1(q0,2,S)=(q0,)1(q0,0,A)=(q0,)1(q0,1,B)
20、=(q0,)N ( M1 ) = L；空栈标志：；空栈标志：( q0, , ) 根据最左派生过程定义状态转移：根据最左派生过程定义状态转移：当对应的文法变量派生出一个字符当对应的文法变量派生出一个字符时时,相应的相应的PDA读入这个字符读入这个字符,并将栈并将栈顶符号换成相应产生式右部除了首顶符号换成相应产生式右部除了首字符之外的后缀字符之外的后缀解解2-1：构造终态方式接受语言的构造终态方式接受语言的PDA。 PDA M2 = ( q0, q1, 0 , 1, 2 , S, A, B, Z, Z0 , 2, q0, Z0, q1 )L(M2)= L ；结束标志结束标志：终态终态 -（qf ,
21、 , ）实际上实际上 = L = w2wR | w 0,1* 设计思路：设计思路：在空栈接受方式下在空栈接受方式下,当栈空了当栈空了,字符串字符串又正好识别完毕又正好识别完毕,让它进入终止态让它进入终止态2(q1, ,Z0)=(q0,SZ)2(q0,0,S)=(q0,SA)2(q0,1,S)=(q0,SB)2(q0,2,S)=(q0,)2(q0,0,A)=(q0,)2(q0,1,B)=(q0,)2(q0,Z)=(qf,)其中其中, q1初始态初始态； q0工作态；工作态；qf- 终止态终止态；栈符号：栈符号： A-0；B-1； Z 栈底标志栈底标志, Z0/SZ0, S/SA 1, S/SB2
22、, S/q1q00, A/1, B/qf, Z/G2： S 0SA | 1SB | 2A 0B 1解解2-2：构造终态方式接受语言的构造终态方式接受语言的PDA。 PDA M2 = ( q0, qf, 0, 1, 2 , S, A, B, Z, Z0 , 2, q0, Z0, qf )其中其中, q0工作态；工作态；qf- 终止态终止态； 栈符号：栈符号： A-0；B-1； Z 栈底标志栈底标志L（M2）= L ；结束标志：终态结束标志：终态 -（qf , , ）实际上实际上 = L = w2wR | w 0,1* 2(q0,0,Z0)=(q0,SAZ)2(q0,1,Z0)=(q0,SBZ)2
23、(q0,2,Z0)=(qf,)2(q0,0,S)=(q0,SA)2(q0,1,S)=(q0,SB)2(q0,2,S)=(q0,)2(q0,0,A)=(q0,)2(q0,1,B)=(q0,)2(q0,Z)=(qf,)G2： S 0SA | 1SB | 2A 0B 1BBBBBABBAABBABBBL = w2wR | w 0,1* 回文： 110020011记录过程匹配过程解解3：将：将 PDA M 工作过程分为工作过程分为两个两个阶段阶段, 按按阶段划分状态：阶段划分状态：设计思路：设计思路：不考虑不考虑GNF,但从栈但从栈的特性来设计的特性来设计,栈是先入后出的栈是先入后出的0A1B1、读字
24、符读字符“2”之前为之前为“记录记录”阶段阶段：M 每读入一个每读入一个字符字符,则则在栈中做在栈中做一次一次记录记录读读 “0”, 在在栈中压入栈符号栈中压入栈符号 “A”；读读 “1”, 在在栈中压栈符号栈中压栈符号 “B”, 读读到到 “2” 时进入符号匹配阶段；时进入符号匹配阶段；解解3：将：将 PDA M 工作过程分为工作过程分为两个两个阶段阶段, 按按阶段划分状态：阶段划分状态：2、读字符读字符“2”之后为之后为“匹配匹配”阶段阶段：每读一个：每读一个字符字符,则则将其与栈顶符将其与栈顶符号相号相匹配匹配 栈栈顶符号为顶符号为 “A”,读读 “0” - 匹配匹配成功成功,读读 “1
25、” - 匹配失败匹配失败； 栈栈顶符号为顶符号为 “B”,读读 “1” - 匹配匹配成功成功,读读 “0” - 匹配失败；匹配失败；3、匹配失败表示匹配失败表示读入的字符号串不是语言的读入的字符号串不是语言的句子句子, 此时此时,可可让让 M 停机停机或进入或进入 “陷阱陷阱” 状态。状态。L = w2wR | w 0,1* 设计思路：设计思路：不考虑不考虑GNF,但从栈但从栈的特性来设计的特性来设计,栈是先入后出的栈是先入后出的回文的特点：110020011解解3-1：构造构造空栈方式空栈方式接受语言的接受语言的 PDA M3 = ( q0, q1, q2 , 0, 1, 2 , A, B,
26、 Z0 , 3 , q0, Z0, )其中其中, 状态状态定义：定义： q0：开始：开始状态状态 ; q1：记录状态；：记录状态； q2： 匹配状态。匹配状态。 栈符号：栈符号：A - 0；B - 1；Z0 -栈底符号栈底符号N(M3)= L ；结束标志：（结束标志：（ p, , ） L = w2wR | w 0,1* 3(q0,0,Z0)=(q1,A)3(q0,1,Z0)=(q1,B)3(q0,2,Z0)=(q2,)3(q1,0,A)=(q1,AA)3(q1,1,A)=(q1,BA)3(q1,0,B)=(q1,AB)3(q1,1,B)=(q1,BB)3(q1,2,A)=(q2,A)3(q1,
27、2,B)=(q2,B)3(q2,0,A)=(q2,)3(q2,1,B)=(q2,)记录阶段记录阶段判断是否读到字符判断是否读到字符2匹配阶段匹配阶段0A1BL = w2wR | w 0,1* 解解3-2：构造构造终态方式终态方式接受语言的接受语言的 PDA。M4 = ( q0, q1, q2 , qf, qt , 0, 1, 2 , A, B, Z0 , 4 , q0, Z0,qf )其中其中, q0: 初始态；初始态； qf: 终态终态；qt: 陷阱态陷阱态 q1: 记录状态；记录状态； q2: 匹配状态匹配状态 栈符号：栈符号：A - 0；B - 1；Z0 初始栈初始栈底底N（M4）= L
28、 ；结束标志：（结束标志：（ qf, , ） 实际上实际上 = 4(q0,0,Z0)=(q1, AZ0)4(q0,1,Z0)=(q1, BZ0)4(q0,2,Z0)=(qf, )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,0,B)=(qt, )4(q2,1,B)=(q2, )4(q2,1,A)=(qt, )4(q2,Z0)=(qf, )到达终止状态，且栈为空记录阶段记录阶段判断是否读到字
29、符判断是否读到字符2匹配阶段匹配阶段第七章第七章 下推自动机下推自动机下推自动机（下推自动机（ PDA ）PDA 两种接受语言方式的等价两种接受语言方式的等价确定的下推自动机（确定的下推自动机（DPDA）PDA 与与 CFG 等价等价定理定理 7 - 1：对于任意对于任意终态方式终态方式接受语言接受语言 L 的的 PDA M1,存在存在空栈方式空栈方式接受语接受语言言 L 的的 PDA M2, 使得使得 N (M2) = L(M1)。定理定理 7 - 2：对于任意对于任意空栈方式空栈方式接受语言接受语言 L 的的 PDA M1,存在存在终态终态方式方式接受语接受语言言 L 的的 PDA M2,
30、 使得使得 L ( M2 ) = N(M1) 。PDA 两种接受语言方式等价两种接受语言方式等价证明思路证明思路:给定给定M1，构造，构造M2模拟模拟M1 ： M1与与M2的基本动作应该是相同的的基本动作应该是相同的 两个问题：两个问题： w引导引导M1进入终止状态进入终止状态后后, M1的的栈未栈未空空,此时此时M2必须将必须将栈清空；栈清空； M1运行中未进入运行中未进入终止状态终止状态,而而此时此时M1的的栈已经空栈已经空了了, M2要能够避免出现这种情况时发生的误接受要能够避免出现这种情况时发生的误接受例：接受例：接受L = w2wR | w 0,1* 的的PDA 定理定理 7 - 1
31、：对于任意对于任意终态方式终态方式接受语言接受语言 L 的的 PDA M1,存在存在空栈方式空栈方式接受语言接受语言 L 的的 PDA M2, 使得使得 N (M2) = L(M1)。定理定理 7-1 的构造证明的构造证明 - 步骤步骤 1:设终态方式设终态方式 PDA M1 = ( Q, , , 1, q01, Z01, F ), 构造构造空栈方式空栈方式 PDA M2 = ( Q q02 , qe , , Z02 , 2, q02, Z02, ), 其中其中, Q q02 , qe = Z02 = ； 2 模拟转移函数定义模拟转移函数定义如下：如下： ( 1 ) 初始化初始化： 2 ( q
32、02, , Z02 ) = ( q01, Z01Z02 ) /转转M1运行运行 ( 2 ) M2完全模完全模拟拟 M1 的的非空移动非空移动：对于：对于 ( q, a, Z ) Q 2(q, a, Z)=1(q, a, Z) ( 3 ) M2在在非终止状态下非终止状态下完全模拟完全模拟M1的空移动：对于的空移动：对于 ( q, Z ) (Q F) , 2 ( q, , Z ) = 1 ( q, , Z ) qe 解决第一个问题q02 Z02解决第二个问题定理定理 7-1 的构造证明的构造证明 - 步骤步骤 1:设终态方式设终态方式 PDA M1 = ( Q, , , 1, q01, Z01,
33、F ), 构造构造空栈方式空栈方式 PDA M2 = ( Q q02 , qe , , Z02 , 2, q02, Z02, ), 其中其中, Q q02 , qe = Z02 = ； 2 模拟转移函数定义模拟转移函数定义如下如下(续续)：（4）M1在在终止状态终止状态下下, M2除了模拟除了模拟M1的空移动外的空移动外,还需模拟还需模拟M1的的“接受动作接受动作”。由于在此动作之后。由于在此动作之后, M1的栈可能仍然不空的栈可能仍然不空,故故M2需要进入清栈状态。需要进入清栈状态。 ( q, Z ) F , 2 ( q, , Z ) = 1 ( q, , Z ) ( qe, ) ( 5 )
34、 M1 栈已空栈已空, 并已进入终止状态并已进入终止状态, 所以所以, M2进入清栈状态进入清栈状态qe,准备将栈清空准备将栈清空 qF, 2(q, , Z02)= (qe, ) ( 6) M2完成清栈工作：完成清栈工作： 对于对于 Z Z02 , 2 ( qe, , Z ) = ( qe, ) 。 由于由于 q F, 故故根据根据 M2 构造定义构造定义 (4,5,6), 有有( q01, x , Z01Z02 ) ( q, , Z02 ) ( qe, , Z02 ) ( qe, , ) 且且 q FM 2M 2M 2根据根据 M2 构造定义构造定义 (2, 3, 4) , M2 可模拟可模
35、拟 M1的所有移动的所有移动操作操作, 故有故有, ( q01, x , Z01Z02 ) ( q, , Z02 ) 且且 q F。同理可证：同理可证： N（M1） L（M2）设任意字符串设任意字符串 x L（M1）, 根据根据 PDA 接受语言接受语言定义定义, 有有 ( q01, x , Z01 ) ( q, , ) 且且 q F。M 1定理定理 7-1 的构造证明的构造证明 ：步骤步骤 2：求证：求证 L（M1）= N（M2）首先证明：首先证明：L（M1） N（M2）。由由 M2 构造定义构造定义 (1) ：( q02, x , Z02 ) ( q01, x , Z01Z02 ) ( q
36、e, , ) 即由：即由：( q02, x , Z02 ) ( qe, , ) ,知知 x N ( M2 ), 得：得：L( M2 ) N( M1 ) M 2M2M 2M 2PDA 两种接受语言方式等价两种接受语言方式等价定理定理 7- 2 的证明思路的证明思路: 给定给定M1是空栈状态接受语言是空栈状态接受语言, 构造构造M2以终止状态接受相同的语言以终止状态接受相同的语言, 且且L(M1)=L(M2) 只要只要M2发现发现M1已将栈弹空就可以进入终止状态已将栈弹空就可以进入终止状态定理定理 7 - 2：对于任意对于任意空栈方式空栈方式接受语言接受语言 L 的的 PDA M1,存在存在存在存
37、在终态方式终态方式接接受语言受语言 L 的的 PDA M2, 使得使得 L ( M2 ) = N(M1) 。定理定理 7- 2 的构造证明的构造证明 - 步骤步骤 1:设空栈方式设空栈方式 PDA M1 = (Q, , , 1, q01, Z01, ), 构造构造终态方式终态方式 PDA M2 = ( Q q02 , qf , , Z02 , 2, q02, Z02, qf ) , 其中其中,Q q02 , qf = Z02 = ； 2 模拟转移函数定义模拟转移函数定义如下：如下： (1) 起始转移状态：起始转移状态： 2 ( q02, , Z02 ) = ( q01, Z01Z02 )。 (
38、2) 模拟模拟 M1 转移：转移： 对于对于 ( q, a, Z ) Q( ) , 2 ( q, a, Z ) = 1 ( q, a, Z ) 。 (3) 模拟结束：模拟结束： 若若 M1 栈已空栈已空,则则 M2 转转终态终态, 2 ( q, , Z02 ) = ( q f, ) 。步骤步骤 2： 求证求证 N ( M1 ) = L（M2）首先求证：首先求证：L（M2） N（M1） 设设 x L ( M2 ), 根据根据 M2 的定义以及构造的第一个移动的定义以及构造的第一个移动 ( 1 ) ： ( q02, x , Z02 ) ( qf , , )； ( q02, x , Z02 ) (
39、q01, x , Z01Z02 ) 有：有： ( q02, x , Z02 ) ( q01, x , Z01Z02 ) ( qf , , )； M 2M 2M 2M 2根据根据 M2 的构造的构造 ( 3 ), 必有一中间状态必有一中间状态 q Q,此时栈空此时栈空,使得使得, ( q01, x , Z01Z02 ) ( q, , Z02 ) 和和 ( q, , Z02 ) ( qf , , ) 成立。成立。M 2M 2由构造由构造(2) 知知, M1 移动与移动与 M2 移动移动相同相同, 故有故有: ( q01, x , Z01Z02 ) ( q, , Z02 )由于由于 Z02 仅是仅是
40、 M2 的栈的栈底底,与与 M1 的栈的栈无关无关,故此故此时应有：时应有： 故由故由( q01, x, Z01 ) ( q, , ) 可知可知 x L (M1), 得：得：L（M2） N（M1） M 1M 1同理可证：同理可证： N（M2） L（M1）PDA 两种接受语言方式等价两种接受语言方式等价第七章第七章 下推自动机下推自动机下推自动机（下推自动机（ PDA ）PDA 两种接受语言的方式两种接受语言的方式确定的下推自动机（确定的下推自动机（DPDA）PDA 与与 CFG 等价等价定义定义 7 - 4：确定的确定的 PDA M = ( Q, , , , q0, Z0, F ) 满足如下条
41、件满足如下条件:对于对于 ( q, a, Z ) Q ,有有| ( q, a, Z ) | + | ( q, , Z ) | 1；确定的确定的 PDA M 简记为简记为 DPDA M。确定的下推自动机（确定的下推自动机（DPDA）定义定义 7 4：确定的确定的 PDA M = ( Q, , , , q0, Z0, F ) 满足如下条件满足如下条件:1、对于、对于 q Q, Z ：若若 ( q, , Z）有有 定义定义, 则则 a , ( q, a, Z ) 无定义；无定义；2、对于对于 q Q,Z , a ： ( q, a, Z ) 最多有一个值；最多有一个值；则称则称 M 为一个确定的为一个
42、确定的 PDA M, 简记为简记为 DPDA M。确定的下推自动机（确定的下推自动机（DPDA）| ( q, a, Z ) | + | ( q, , Z ) | 1第七章第七章 下推自动机下推自动机下推自动机（下推自动机（ PDA ）PDA 两种接受语言的方式两种接受语言的方式确定的下推自动机（确定的下推自动机（DPDA）PDA 与与 CFG 等价等价定理定理 7-3 对于任意对于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模拟模拟GNF的最左派生的最左派生(1) 构造构造PDA。 设设L为不含为不含 的的CFL, 根据定理根据定理 6-10，存在，存
43、在GNF G=(V,T,P,S), 使使得得L(G)=L(G)。取取 PDA M=(q,T, V, , q, S, )对于任意的对于任意的AV, aT,(q, a, A)= (q, )| AaP 也就是说也就是说, (q,) (q, a, A)的充分必要条件是的充分必要条件是AaP。PDA 与与 CFG 等价等价GNF的最左派生过程中，变量决定派生如何进行，只需要一个状态 (q,) (q, a, A) 当且仅当当且仅当 A aP (q, ) (q, a, A) 当且仅当当且仅当 A aPa: 输入输入A: 栈顶符号栈顶符号：压入栈的符号串：压入栈的符号串定理定理 7-3 对于任意对于任意CFL
44、 L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模拟模拟GNF的最左派生的最左派生(2) 证明构造的正确性：证明构造的正确性：N(M)=L(G)。 施归纳施归纳于于 w 的的长度长度n, 证明证明 (q, w, S)Mn (q, , )的充分必要条件为的充分必要条件为Snw。 （必要性）（必要性） (a) 当当n=1时，有时，有(q, a, S)M (q, , )， aT, 且且（q, ） (q, a, S) 根据根据的定义，的定义， S a P, 因此因此Sa证明更一般的结论(q,) (q, a, A)的的充分必要条件是充分必要条件是AaP定理定理 7-3 对于任
45、意对于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模拟模拟GNF的最左派生的最左派生(2) 证明构造的正确性：证明构造的正确性：N(M)=L(G)。 施归纳于施归纳于w的长度的长度n, 证明证明 (q, w, S)Mn (q, , )的充分必要条件为的充分必要条件为Snw。（必要性（续必要性（续 ）（b）假设结论对假设结论对n=k成立成立, 下面下面证明结论对证明结论对n=k+1成立。成立。 取取w= xa, |x|=k, aT，则有，则有 (q, w, S) = (q, xa, S)Mk (q, a, )M(q, , ) 由由(q, a, )M(q,
46、 , ) 知知，必定存在，必定存在 A V, =A1, = 21， (q, 2) (q, a, A)。即即(q, a, )=(q, a, A1)M (q, , 21) =(q, , ) 弹弹出出A, 压入压入2又由又由(q, 2) (q, a, A)得得 A a2 P.再从再从(q, xa, S)Mk (q, a, ) 得得 (q, x, S)Mk (q, , )，由归纳假设知由归纳假设知 S kx , 注意到注意到=A1, 且且A a2P，得，得S kx A1 x a21即即S k+1w。（。（w=xa, =21）故结论对故结论对k+1成立。由归纳法原理，结论对任意成立。由归纳法原理，结论对
47、任意n成立。成立。同理可证充分性。同理可证充分性。由由的任意性，知的任意性，知(q, w, S)Mn (q, , )的充分必的充分必要条件为要条件为Snw，即，即N(M)=L(G).定理定理 7-3 对于任意对于任意CFL L, 存在存在PDA M, 使得使得N(M)=L。 思路：用思路：用PDA模拟模拟GNF的最左派生的最左派生(3)考虑考虑L的情况。的情况。 先先按照按照 (1)的构造方法构造出的构造方法构造出PDA M=(q, T, V, , q, S, )，使得，使得N(M)=L。然后然后取取M1=( q,q0, T, VZ, 1, q0, Z, )其中其中, q0q, Z V, 令令
48、 1(q0, , Z) = (q0,), (q,S) ,且对于且对于 (a, A)TV，有，有 1(q, a, A)=(q, a, A) ，可证可证N(M)=N(M) 。例：例：构造与如下构造与如下GNF等价的等价的PDA S aT | a T aT | aT | a | b(q, a, S)= (q, T), (q, ) (q, a, T)= (q, T), (q, ) (q, b, T)= (q, T), (q, ) (q, ) (q, a, A)的的充分必要条件是充分必要条件是AaPM=(q, T, V, , q, S, ), 其中其中定理定理 7-4 对于任意的对于任意的PDA M,
49、存在存在CFG G使得使得L(G) = N(M) 思路：用思路：用CFG G的派生来模拟相应的的派生来模拟相应的PDA M的移动的移动PDA 与与 CFG 等价等价q, A a q1, A1A2An（q, A与与q1, A1A2An看成两个看成两个变量）变量）(q1, A1A2An) (q, a, A) M在状态在状态 q，栈顶符号为，栈顶符号为A时时 读入字符读入字符a 将状态改为将状态改为q1 弹出栈顶符号弹出栈顶符号A 将符号将符号A1, , An从右至左依次压入栈从右至左依次压入栈存在的问题存在的问题：1. 以以q1, A1A2An为左为左边的产生式不好定义边的产生式不好定义2. 没有
50、体现没有体现A1A2An一一个个被弹出个个被弹出q, A a q1, A1 q2, A2 qn, An（q, A与每个与每个qi, Ai都看成一个变量）都看成一个变量）定理定理 7-4 对于任意的对于任意的PDA M,存在存在CFG G使得使得L(G)=N(M) 思路：用思路：用CFG G的派生来模拟相应的的派生来模拟相应的PDA M的移动的移动PDA 与与 CFG 等价等价(q1, A1A2An) (q, a, A) M在状态在状态 q，栈顶符号为，栈顶符号为A时读入字符时读入字符a 将状态改为将状态改为q1 弹出栈顶符号弹出栈顶符号A 将符号将符号A1,An依次压入栈依次压入栈q, A a
