编译原理 3章.ppt

《编译原理 3章.ppt》由会员分享，可在线阅读，更多相关《编译原理 3章.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章有穷自动机编译原理陈炬桦isscjhmail,有穷自动机的形式定义有穷自动机的形式定义定义定义3.1一个确定型有穷自动机DFA是一个五元组DFA=（Q,t,q0,F）Q：非空有穷状态集；：有穷输入字母表；t：是一个单值映射q0：开始状态，q0QF：非空终止状态集DFA状态转换(左表)图abq0q1q3q1q0q2q2q3q1q3q2q0有穷自动机的扩充的映射 定义定义 3.2DFA=（Q,t,q0,F）扩充的映射t：定义为t(q,)=qt(q,a)=t(t(q,a),)定义定义 3.3DFA=（Q,t,q0,F），如果t(q0,)=qF，称为DFA接收。定义定义 3.4两个有穷自动机A1

2、和A2，如果L(A1)=L(A2)，则称自动机A1与A2等价。非确定型有穷自动机NDFA定义定义 3.5一个非确定型有穷自动机NDFA是一个五元组NDFA=(Q,t,Q0,F)t：是一个多值映射Q0：开始状态集,Q0Q例3.6NDFANDFA到到DFA的转换的转换空移环路的寻找和消除空移环路的寻找和消除NDFA到到DFA的转换的转换消除空移消除空移 如果B是终止状态，置A为终止状态；如果A是开始状态，置B为开始状态；确定化确定化子集法子集法设NDFAA=（Q,t,Q0,F）设一个非确定型有穷自动机，它的语言为L（A）,可以构造一个与它等价的确定型有穷自动机DFAA=（Q,t,q0,F）,L（A

3、）=L（A）确定化确定化造表法造表法xyq0q1,q2q0q1,q2q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q1,q3q1,q2,q3q0,q1,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3xyq0q1,q2q0q1,q2q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q3q1,q2,q3q0,q1,q3q1,q2,q3q0,q1,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3q0,q1,q2,q3NDFA的确定化的确定化ND

4、FA=（Q,t,Q0,F）定义定义 3.8 状态子集I的-闭包，-closure(I)=q|t(I,)=q定义定义 3.9 Ia=-closure(J)，其中J=t(I,a)NDFA的确定化举例的确定化举例IxIyS1,2,31,2,342,3,546,7,82,3,54,6,7,82,3,56,7,87,84,6,7,87,86,7,87,87,8DFA的化简的化简终止状态与非终止状态可区分的，分成子集对所有子集对所有输入符号判断，如果可区分则分解子集如果有分解子集，转，否则结束。从化简的从化简的DFA到程序设计到程序设计DFA的化简举例的化简举例xy0,20|21,3,4,51|3,4,5

5、B1D3,4,5A0C2正规文法与有穷自动机正规文法与有穷自动机从正规文法到从正规文法到FAG=VN，VT，P，SFA=（Q,t,q0,F）q0=Sq0=S=VT=VT在在FAFA增加一个终止状态增加一个终止状态Z Z，F=Z,Q=VNFF=Z,Q=VNFAaBAaB=t(A,a)=B=t(A,a)=B；Aa=t(A,a)=Z Aa=t(A,a)=Z正规文法与有穷自动机举例正规文法与有穷自动机举例从正规文法到从正规文法到FA例例3.14G19S：SaS|aA|bBAbA|cCBaB|dDCcC|cDdD|d正规文法与有穷自动机正规文法与有穷自动机从从FA到正规文法到正规文法 FA=（Q,t,q

6、0,F)G=(VN，VT，P，S)VN=QVT=S=q0T(A,a)=B=AaB,如果AF,A正规文法与有穷自动机举例正规文法与有穷自动机举例从从FA到正规文法到正规文法 例例3.15G20S：SxA|yBAyA|yC|xBBxC|yC|yA|C正规表达式的定义正规表达式的定义定义定义 3.12 字母表上的正规表达式正规表达式和正正规集规集递归定义如下符号正规表达式正规集aaae1与e2L(e1)与L(e2)e1|e2L(e1|e2)=L(e1)L(e2)e1.e2L(e1.e2)=L(e1)L(e2)(e1)*L(e1)*)=L(e1)*正规表达式到正规表达式到NDFA的转换的转换正规表达式

7、到正规表达式到NDFA的转换举例的转换举例NDFA到正规表达式的转换到正规表达式的转换NDFA到正规表达式的转换到正规表达式的转换(x!yy)(y|xy)*(y|x(x|y)|(y|xy*x)(yy*x)*(yy*y|x|y)正规文法到正规表达式正规文法到正规表达式规则：UV，V转换为UUU|转换为U*U|转换为U|正规文法到正规表达式举例正规文法到正规表达式举例SaS|aA|bBAbA|cCBaB|dDCcC|cDdD|dSaS|(ab*cc*c|ba*dd*d)a*ab*cc*c|a*ba*dd*dAbA|cc*cb*cc*cBaB|dd*da*dd*dCc*cDd*d举例构造该正则式所对

8、应的NFA(画出转换图)设字母表：a,b，给出上的一个正则式aa*bb*(ab*)*b。构造该正则式所对应的NFA(画出转换图)将所求的NFA确定化(画出DFA的转换图)将所求的DFA最小化(画出极小化后的转换图)；将所求的NFA确定化(画出DFA的转换图)abq0Sq11,2,3q11,2,3q22,3q34,5,6,7,10q22,3q22,3q34,5,6,7,10q34,5,6,7,10q48,9,7,10q55,6,710,Zq48,9,7,10q48,9,7,10q69,7,10,Zq55,6,710,Zq48,9,7,10q55,6,710,Z最小化q0,q1,q2,q3q4,q

9、5,q6区分得到：q0,q1,q2,q3q4,q5,q6举例构造该正则式所对应的NFA(画出转换图)设字母表：0，1，给出上的一个正则式1（01）*(10|1)*0*。构造该正则式所对应的NFA(画出转换图)；将所求的NFA确定化(画出DFA的转换图)；将所求的DFA最小化(画出极小化后的转换图)；确定化01A SB 1,2,4,5,7,8,ZB 1,2,4,5,7,8,ZC 3,8,ZD 5,6,7,8,ZC 3,8,ZE 8,ZF 2,4,5,7,8,ZD 5,6,7,8,ZG 5,7,8,ZD 5,6,7,8,ZE 8,ZE 8,ZF 2,4,5,7,8,ZC 3,8,ZD 5,6,7,8,ZG 5,7,8,ZE 8,ZD 5,6,7,8,Z最小化01aAbB,D,FbB,D.FcC,GbB,D,FcC,GeEbB,D,FeEeE第3章习题作业3.23.4练习设字母表：a,b，给出上的一个正则式b*abb*(a*bb)*。构造该正则式所对应的NFA(画出转换图)；将所求的NFA确定化(画出DFA的转换图)；将所求的DFA最小化(画出极小化后的转换图)；