第三章词法分析及有穷自动机.ppt

例4，将下列状态图所示的自动机确定化，最小化。解：先构造对应的状态矩阵S01ABFBGCCACDCGEHFFCGGGEHGC由矩阵或状态图可看出D为无用状态，即由初态A开始永远也达不到D。则对删除D的自动机最小化。第126页，共127页，星期日，2025年，2月5日首先划分为终态和非终态集：{A,B,E,F,G,H},{C} 因为{A,B,E,F,G,H}0中的{F}0={C},即没有落入{A,B,E,F,G,H}中，进行第二次划分：{A,B,E,G,H},{F},{C}同理，{A,B,E,G,H}1中的{B,H}1={C},没有落入{A,B,E,G,H}中，继续划分：{A,E,G},{B,H},{F},{C}而{A,E,G}0分别落入{A,E,G}和{B,H}中，再次划分为： {A,E},{G},{B,H},{F},{C}至此已是最小划分，按顺序重新命名为A1,B1,C1,D1和E1,则得状态矩阵和状态图：S01A1C1D1B1B1A1C1B1E1D1E1B1E1A1E1第127页，共127页，星期日，2025年，2月5日令f(A,a)=D;(注意：D是终结状态)(4)对G中每一形如:A∷=ε的产生式(A∈VN),令f(A,ε)=D; 显然，这样构造的M是具有一个开始状态的NFA。例：构造下列右线性文法G[Z]的有穷自动机。Z∷=0AA∷=0A|0BB∷=1A|1则构造等价自动机M=({Z,A,B,D},{0,1},f,{Z},{D}),其中：f(Z,0)={A},f(A,0)={A,B},f(B,1)={D},f(B,1)={A}右线性文法构造状态图ABZD01010第94页，共127页，星期日，2025年，2月5日状态矩阵表示：2.左线性正规文法到有穷自动机的转换设给定义左线性正规文法G=(VN,VT,P,S),则相应的有穷自动机M=(Q,∑,f,q0,Z).(1)新增加一个初始状态q0,且q0VN;将VT中每个非终止状态视作M中的状态，令Q=VN∪{q0},并将G的开始符号S看成终结状态，即Z={S},∑=VT;(2)对G中每一形如:A∷=Ba的产生式(A,B∈VN,a∈VT∪{ε}),令f(B,a)=A;01Z{A}ΦA{A,B}ΦBΦ{A,D}DΦΦ第95页，共127页，星期日，2025年，2月5日(3)对G中每一形如:A∷=a的产生式(A∈VN,a∈VT∪{ε}),令f(q0,a)=A;例，构造G[A]的自动机A∷=A1|B1B∷=B0|0根据转换方法，与G对应的自动机M=({S,A,B},{0,1},f,S,{A}),其中：f(A,1)=A,f(B,1)=A,f(B,0)=B,f(S,0)=B其状态图：它为确定的，且识别的语言为：L(M)=L(G[A])=00*11*第96页，共127页，星期日，2025年，2月5日二、有穷自动机到正则文法的转换给定有穷自动机M=(Q,∑,f,q0,Z),按下列方法构造对应右线性文法G=(VN,VT,P,S):(1)令VN=Q，VT=∑，S=q0;(2)若f(A,a)=B,且B不是终结状态,则将A∷=aB加到p中；(3)若f(A,a)=B,且B是终结状态,则将A∷=aB|a或A∷=aB,B∷=ε加到p中；(4)若G的开始符号S是一个终结状态，则将S∷=ε加到p中。例：设DFAM=({A,B,C,D},{0,1},f,A,{B}),其中：f(A,0)=B,f(B,1)=C,f(C,0)=B, 第97页，共127页，星期日，2025年，2月5日（1）根据函数式构造右线性正规文法G[A]：A→0B|0,B→1C,C→0C|0或A∷=0B,B∷=1C|ε,C∷=0B（2）将函数式换成状态图，然后转换成右线性正规文法。由函数式得到等价的DFAM:根据状态转换图，所求右线性文法G=({A,B,C},{0,1},P,A),P为：A∷=0B|0,B∷=1C,C∷=0B|0或A∷=0B,B∷=1C|ε,C∷=0B注：以开始状态作为开始符号，然后依弧的方向写出产生式右边的式子。若到达的是终结状态弧，则，该弧上的符号要作