形式语言自动机——上下文无关文法与下推自动机四学习教案

1、会计学1形式语言自动机形式语言自动机上下文无关上下文无关(wgun)文法与下推自动机四文法与下推自动机四第一页，共23页。2 构造方法构造方法 设设 CFG G = (N, T, P , S ) ，构造一个空栈接受方式构造一个空栈接受方式(fngsh)的的 PDA M（Q，T，q0，z0，F）其中其中 Qq, =NT, q0q，z0S, F (以空栈接受以空栈接受)即即 M = ( q , T, NT, , q, S , F) , 转移函数转移函数 定义如下：定义如下： (1) 对每一对每一 AN, (q, , A) = (q,)A”P ; （即将栈顶的（即将栈顶的A换为换为） (2) 对每一

2、对每一 aT, (q, a, a) = (q, ) . （即若栈顶为终结符，则退栈）（即若栈顶为终结符，则退栈） 从上下文无关从上下文无关(wgun)文法构造等价的下推文法构造等价的下推自动机自动机第2页/共23页第二页，共23页。3q，z0z0S/S/ 若若SPSP ，A/ A/ 若若APAP a,a/ a,a/ a T, 从上下文无关从上下文无关(wgun)文法构造等价的下推自动机文法构造等价的下推自动机用图形用图形(txng)(txng)表示：表示： 例例1 对右边产生式所代表对右边产生式所代表 CFG， 依上述方法依上述方法(fngf)构造的构造的 PDA 为为E EOE (E) v

3、dO ( q , v,d,+, ,(,) , E,O,v,d,+, , , q, E, ) , 其中其中 定义为定义为 (q, , E) =(q,EOE), (q,(E), (q,v),(q,d),(q,), (q, ), (q, , O) = (q, ) , (q, v, v) = (q, d, d)= (q, ) (q,) = (q, , ) = (q,(,( ) = (q,),) )= 第3页/共23页第三页，共23页。4自顶向下的分析自顶向下的分析(fnx)过程过程定理的物理意义：利用下推自动机进行自顶向下的分析，定理的物理意义：利用下推自动机进行自顶向下的分析， 检查检查一个句子的最

4、左推导过程一个句子的最左推导过程(guchng)。 步骤如下：步骤如下： (1) 初始时，将文法开始符号压入空栈初始时，将文法开始符号压入空栈. (2) 如果栈为空，则分析完成如果栈为空，则分析完成. (3) 如果栈顶为一非终结符，先将其从栈中弹出如果栈顶为一非终结符，先将其从栈中弹出. 选择下选择下 一个相应于该非终结符的产生式，并将其右部一个相应于该非终结符的产生式，并将其右部 符号从符号从 右至左地一一入栈右至左地一一入栈. 如果没有可选的产生式，则转出如果没有可选的产生式，则转出 错处理错处理. (4) 如果栈顶为一终结符，那么这个符号必须与当前输入如果栈顶为一终结符，那么这个符号必须

5、与当前输入 符号相同，将其弹出栈，读下一符号，转第符号相同，将其弹出栈，读下一符号，转第(2)步；否步；否 则，回溯到第则，回溯到第(3)步步.第4页/共23页第四页，共23页。5例例2：利用下推自动机进行：利用下推自动机进行(jnxng)自顶向下的分析自顶向下的分析过程过程E EOE (E) v dO EEOEEOvEOE EE)(E)E)OEE)OvE)OE)E)d)v ( v d )q，z z0 0E E/ / 若若EPEP ，O/O/* *a,a/ a a,a/ a (,),v,d,+, (,),v,d,+,* * ，O/+O/+第5页/共23页第五页，共23页。6定理定理(dngl)

6、(dngl)的证明的证明 证明思路证明思路(sl) 欲证，对任何欲证，对任何 wT*, wL(G) wL(M). 先证明如下结论先证明如下结论, if A w, then (q,w,A)*(q, , ). 归纳于归纳于 A w 的步数的步数 n. . 基础基础(jch) n=1，Aw 必为产生式，必为产生式， (q,w,A) (q,w,w) *(q, , ).归纳归纳 设第一步使用产生式设第一步使用产生式 AX1X2Xm ，必有必有 w=w1w2wm ， (q,w,A) (q,w, X1X2Xm ) * (q, w2wm , X2Xm) * (q, w3wm , X3Xm)* * (q, ,

7、).所以所以: if S w, then (q,w,S)*(q, , ). 即即, w L(G) w L(M). 第6页/共23页第六页，共23页。7定理定理(dngl)(dngl)的证明的证明 先证明如下结论先证明如下结论, if (q, w,A)*(q, , ), then A w. 归纳归纳(gun)于于 (q, w,A)*(q, , ) 的步的步数数 n.归纳归纳(gun) n1，设第一步使用产生式，设第一步使用产生式 AX1X2Xm ， 可以将可以将w 分为分为 w = w 1 w 2 w m ，满足，满足 (q, wi , Xi )*(q, , )，所以所以: 对任何对任何 w T

8、*, if (q,w,S)*(q, , ), then S w. 即即, w L(M) w L(G). 因此因此 ，A X1X2Xm ， w 1 w 2 w m = w 无论无论 Xi 为终结符，还是非终结符，都有为终结符，还是非终结符，都有 Xi w i . 基础基础 n=1，必有必有 w = ，且且 A 为为 G 的产生式，所以的产生式，所以 A w. 第7页/共23页第七页，共23页。8例：构造一个例：构造一个PDA MPDA M，使，使L(M)= L(G)L(M)= L(G)。其中。其中G G是我们常用来生成是我们常用来生成算术表达式的文法：算术表达式的文法：G G（N N，T T，P

9、 P，E E） N N E,T,F , T = +, E,T,F , T = +,* *,(,),a , S = E ,(,),a , S = E P: EE+TT ; TT P: EE+TT ; TT* *FF; F( E )aFF; F( E )a解：构造解：构造M M（qq，T T，q q，E E，） 定义定义(dngy)(dngy)为：为： (q,E) (q,E) (q, E+T ), (q, T) (q, E+T ), (q, T) (q,T) (q,T) (q, T (q, T* *F ), (q, F) F ), (q, F) (q,F) (q,F) (q, (E) ), ( q

10、, a) (q, (E) ), ( q, a) (q, b,b) (q, b,b) (q, ) (q, ) 对所有对所有 b a,+, b a,+,* *,(,) ,(,) 例例3: 从文法从文法(wnf)构造等价的下推自动机构造等价的下推自动机第8页/共23页第八页，共23页。9用格局说明句子用格局说明句子(j zi)分析过程分析过程 例如例如 以以a+aa+a* *a a作为输入作为输入(shr)(shr)，则，则M M在所有可能移动中可作下列在所有可能移动中可作下列移动（用到文法移动（用到文法G G中从中从E E出发的最左派生的一系列规则）出发的最左派生的一系列规则） （q q，a aa

11、 a* *a, Ea, E） (q (q，a aa a* *a, E+T)a, E+T) (q (q，a aa a* *a, T+T)a, T+T) (q (q，a aa a* *a, F+T)a, F+T) (q (q，a aa a* *a, a+T)a, a+T) (q (q，a a* *a, +T)a, +T) (q (q，a a* *a, T)a, T) (q (q，a a* *a, Ta, T* *F)F) (q (q，a a* *a, Fa, F* *F)F) 第9页/共23页第九页，共23页。10从下推自动机构造从下推自动机构造(guzo)等价的上下文无关文法等价的上下文无关文法

12、G G导出导出PDAPDA，其逆定理也成立。，其逆定理也成立。 PDA PDA导出文法导出文法G G）：）：设下推自动机设下推自动机M M，以空栈形式接受语言，以空栈形式接受语言 L(M L(M），则存在），则存在(cnzi)(cnzi)一个上下文无关文法一个上下文无关文法G G，产生语言，产生语言L(G), L(G), 使使L(G)= L(ML(G)= L(M） 。证明：设证明：设M M（ Q Q，T T，q0q0，z0z0，） 思路：构造文法思路：构造文法G G，使，使串在串在G G中的一个最左推导直接对应于中的一个最左推导直接对应于PDA PDA M M 在处理在处理时所做的一系列移动时

13、所做的一系列移动 。第10页/共23页第十页，共23页。11从下推自动机构造等价从下推自动机构造等价(dngji)的上下文无关的上下文无关文法文法采用形如采用形如qq，z,z,的非终结符的非终结符, q, q，QQ，zz q q，z,z,的物理意义的物理意义(yy)(yy)：在在q q状态，栈顶为状态，栈顶为z z时，接受某个字符时，接受某个字符( (可为可为)后将变换后将变换到到状态，并保证状态，并保证 qq，z, z, 当且仅当（当且仅当（q,zq,z）* *（,）. .第11页/共23页第十一页，共23页。12从下推自动机构造等价的上下文无关从下推自动机构造等价的上下文无关(wgun)文

14、法文法 构造构造(guzo)(guzo)方法方法 设设 PDA M PDA M（ Q Q，T T，q0q0，z0z0，） , , 构造构造(guzo)CFG G(guzo)CFG G（N,T,P,SN,T,P,S） 其中其中 N N q,z,q,Q q,z,q,Q，zSzS 产生产生(chnshng)式集合式集合 P 定义如下：定义如下：对于每个对于每个qQ，将，将Sq0，z0, q 加入到产生加入到产生(chnshng)式中。式中。 若若（q，a，z）含有（）含有（,），则将），则将q,z,a加入到产生加入到产生(chnshng)式中。式中。若若（q，a，z）含有（）含有（，B1,B2, B

15、k）k1，Bi，则对，则对Q中的每一个状态序列中的每一个状态序列q1,q2,qk,(qiQ),把形如把形如q,z,qka,B1,q1q1,B2,q2qk-1,Bk,qk的产生的产生(chnshng)式加入到式加入到P中。其中，中。其中，a T 或或 a = 第12页/共23页第十二页，共23页。13（书P169170）由PDA M构造(guzo)文法G设PDA M（q0,q1,a,b,A,z0,q0,z0,）定义为：（q0,a,z0）=( q0,Az0) （q0,a,A）=( q0,AA) （q0,b,A）=( q1,) （q1,b,A）=( q1,) （q1,A）=( q1,) （q1,z0

16、）=( q1,) 例例1: 从下推自动机构造等价从下推自动机构造等价(dngji)的上下文无关的上下文无关文法文法第13页/共23页第十三页，共23页。14 q0 b, A/ q1 a, z0/Az0 b, A/ a, A/AA , A/ , z0/解：（1） q0,q1Q， 构造(guzo) Sq0,z0,q0; Sq0,z0,q1 （2）对式，可构造(guzo)由（q0,b,A）=( q1,) 得 q0,A,q1b 由（q1,b,A）=( q1,) 得q1,A,q1b由（q1,A）=( q1,)得 q1,A,q1由（q1,z0）=( q1,)得 q1,z0,q1第14页/共23页第十四页，

17、共23页。15 q0 b, A/ q1 a, z0/Az0 b, A/ a, A/AA , A/ , , z0/（3） 对式（q0,a,z0）=( q0, A z0) ，所有可能(knng)的状态序列为：q0q0，q1q0，q0q1，q1q1可构造出产生式： q0,z0,q0 a q0,A, q0 q0,z0, q0 q0,z0,q0 a q0,A, q1 q1,z0, q0 q0,z0,q1 a q0,A, q0 q0,z0, q1 q0,z0,q1 a q0,A, q1 q1,z0, q1 第15页/共23页第十五页，共23页。16 q0 b, A/ q1 a, z0/Az0 b, A/

18、a, A/AA , A/ , , z0/对式（q0,a,A）=( q0, AA) ，所有可能的状态序列为：q0q0，q1q0，q0q1，q1q1可构造(guzo)出产生式： q0,A,q0 a q0,A, q0 q0,A, q0 q0,A,q0 a q0,A, q1 q1,A, q0 q0,A,q1 a q0,A, q0 q0,A, q1 q0,A,q1 a q0,A, q1 q1,A, q1 第16页/共23页第十六页，共23页。17(4)删除无用符号 q0,A,q1 和 q1,z0,q0及相应(xingyng)产生式 重命名 q0,z0,q1为A SA q1,A,q1为B AaCD q0,

19、A,q1为C 得 Bb q1,z0,q1为D CaCBb D注: 构造生成式时，可从S生成式出发，以避免生成无用产生式。第17页/共23页第十七页，共23页。18定理定理(dngl)的关键：的关键： 当存在当存在(q，a，z)含有（含有（，B1B2Bk）则对则对Q中的每个可能的状态序列中的每个可能的状态序列q1 q2 qk排成一条产生式排成一条产生式q, z, qka, B1, q1 q1, B2,q2qk-1,Bk,qk 这是一个猜测过程，实质是写出从这是一个猜测过程，实质是写出从q出发，栈出发，栈顶为顶为Z，经过一系列推导走到，经过一系列推导走到qk的所有可能的所有可能的状态序列，其中必有

20、一条路径是正确的。的状态序列，其中必有一条路径是正确的。 第18页/共23页第十八页，共23页。19M（q，T，q，E，） 定义为：定义为： (q,E) (q, E+T ), (q, T) (q,T) (q, T*F ), (q, F) (q,F) (q, (E) ), ( q, a) (q, b,b) (q, ) 对所有对所有 b a,+,*,(,) 算术算术(sunsh)表达式的文法表达式的文法 G（N，T，P，E） N E,T,F , T = +,*,(,),a , S = E P: EE+T T ; TT*F F; F( E ) a练习：针对算术表达式的练习：针对算术表达式的PDA反向

21、反向(fn xin)构造其等价文法构造其等价文法第19页/共23页第十九页，共23页。20练习练习: 从从PDA构造等价的上下文无关构造等价的上下文无关(wgun)文法文法对于右下图的对于右下图的 PDA，构造，构造(guzo)CFG G = (N,0,1,P,S) ， 其中其中 N = S p,Y,qp,qq0,q1,q2 YZ0,X Start0, Z0 / XZ00, X / XXq2 q1 q0 Z0 , /1, X / 1, X / 产生式集合产生式集合(jh) P 定义如下：定义如下： (1) S q0 , Z0 , q0 ; S q0 , Z0 , q1 ; S q0 , Z0 , q2 ; (5)由由(q0,XZ0) (q0, 0, Z0) 得得 q0Z0qj 0q0Xq