1.1.构造正规式的构造正规式的 DFADFA。1 11(0|1)*1011(0|1)*101首先构造首先构造 NFANFA：1XANFANFA 化为化为 DFADFA：状态转换表：状态转换表：QX AABC BBCD CBC DBCE EBCDY Y状态转换图：状态转换图：A1 1初态初态ABCDEY化简后得：化简后得：A1B00B1C1 1D0E1 1Y1ABC BBCD CBCD CBCD CBCDY YBCD C10CB1 10 0D01BCCCYC011C0E101Y0DEDDE1 11 10 0YE1 10 0BC DBCE EBC DBC DBCE E01 / 172 2(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*aX1b？NFA 化为 DFA：QX 1 21 2 31 2 41 2 3 5 Y1 2 4 5 Y1 2 4 Y1 2 3 Y3a2b4ba5aYba1 2 31 2 3 5 Y1 2 31 2 3 5 Y1 2 3 Y1 2 3 Y1 2 3 5 Y1 2 41 2 4 1 2 4 5 Y1 2 4 Y1 2 4 5 Y1 2 4 5 Y1 2 4 Yba所以，DFA 为：aabX13aabbbb24ab化简得：a1aaabXYbb2b2 / 175ba603 3 0|11*00|11*0* *XA1BC1NFANFA 到到 DFADFA：QX A Y XB C D AA Y BC D Y1X0化简后得；化简后得；0X0DY1B C D AC D YB C D AC D Y0A Y BA Y BA Y BA Y BA10B011Y010A13 / 172.2.将以下图确定化和最小化。将以下图确定化和最小化。aa 0 1a,b解解: : 首先取首先取 A=A=-CLOSURE(0)=0,NFA-CLOSURE(0)=0,NFA 确定化后的状态矩阵为确定化后的状态矩阵为: :ABCQ00,11a0,10,10b11NFANFA 确定化后的确定化后的 DFADFA 为：为：aaABabbC将将 A,BA,B 合并得合并得: :ab ACa4 / 173.3.构造一个构造一个 DFADFA，它承受，它承受=0=0，11上所有满足如下条件的字符串，上所有满足如下条件的字符串，每个每个 1 1 都有都有 0 0 直接跟在后边。直接跟在后边。解：按题意相应的正规表达式是0*(0 | 10)*0*构造相应的 DFA，首先构造 NFA 为 0 0 0YX013 1 02用子集法确定化IX,0,1,3,Y0,1,3,Y21,3,YI00,1,3,Y0,1,3,Y1,3,Y1,3,YI122/2S1234022441333DFA 为 01 02 1 1 0 143 05 / 174.给出给出 NFANFA 等价的正规式等价的正规式 R R。方法一：首先将状态图转化为方法一：首先将状态图转化为X1 1ABC消去Y得B 11X、*0|1 11X0,1消去其余结点AC0，1YYNFANFA 等价的正规式为等价的正规式为0|1*11方法二：方法二：NFANFA右线性文法正规式右线性文法正规式A A0A|1A|1B0A|1A|1BB B1C1CC CA=0A+1A+1BA=0A+1A+1BB=1B=1A=0A+1A+11A=0A+1A+11A=(0+1)A=(0+1)* *1111(0|1)(0|1)* *11116 / 175.5.试证明正规式试证明正规式a|ba|b* *与正规式与正规式a a* *|b|b* * *是等价的。是等价的。证明：证明：(1)(1)正规式正规式(a|b)(a|b)的的 NFANFA 为=Xb1,ya1,yb1,y1,yX, 1,y1,ya其最简其最简 DFADFA 为为* *a1Y=bA(2)(2)正规式正规式a*|b*a*|b* *的的 NFA NFA 为：为：a其最简化其最简化 DFADFA 为：为：3a = X=1bYAbDFADFA 的状态转换表：的状态转换表：x,1,2,3,y1,2,3,y由于这两个正规式的最小由于这两个正规式的最小 DFADFA 一样，所以正规式一样，所以正规式(a|b)*(a|b)*等价于正规式等价于正规式(a*|b*)*(a*|b*)*。7 / 17a1,2,3,y1,2,3,yb1,2,3,y1,2,3,y26.6.设字母表设字母表=a,b,=a,b,给出上的正规式给出上的正规式 R=bR=b* *ab(b|ab)ab(b|ab)* *。（1 1）试试构造状态最小化的构造状态最小化的 DFA MDFA M，使得，使得 L LM M=L=LR R 。（2 2）求求右线性文法右线性文法 G G，使，使 L LG G=L=LM M 。解解:(1):(1)构造构造 NFA:NFA:6bX1b2a3b45aYb(2)(2)将其化为将其化为 DFA,DFA,转换矩阵为转换矩阵为: :QX,1,2 13 21,2 34,5,Y 46 55,Y 68 / 173 26 56 5a3 2b1,2 34,5,Y 41,2 35,Y 65,Y 65,Y 62a1b3bab4a5bb6ba再将其最小化得再将其最小化得: :aXbWbaYb2 2对应的右线性文法对应的右线性文法 G=G=X,W,Y,a,b,P,XX,W,Y,a,b,P,XP: XP: XaW|bXWaW|bXWbbY|b yY|b yaaW|bY|bW|bY|b9 / 173.8 文法文法 GG单词单词 为：为：单词单词- - 标识符标识符| |整数整数标识符标识符- - 标识符标识符 字母字母| |标识符标识符 数字数字| |字母字母整数整数- - 数字数字| |整数整数 数字数字字母字母- -A|B|CA|B|C数字数字|-1|2|3|-1|2|31 1改写文法改写文法 G G 为为 G，使G，使 L(G)=L(G)。L(G)=L(G)。2 2给出相应的有穷自动机。给出相应的有穷自动机。解：解： 1 1令令 D D 代表单词，代表单词，I I 代表标识符，代表标识符，Z Z 代表整数，有代表整数，有 G GD D ：D DI | ZI | ZI IA | B | C | IA | IB | IC | I1 | I2 | I3A | B | C | IA | IB | IC | I1 | I2 | I3Z Z1 | 2 | 3 | Z1 | Z2 | Z31 | 2 | 3 | Z1 | Z2 | Z3(2)(2)左线性文法左线性文法 GG所对应的有穷自动机为：所对应的有穷自动机为：M=(S,D,I,Z,1,2,3,A,B,C,f,S,D)M=(S,D,I,Z,1,2,3,A,B,C,f,S,D)f: f(S,A)=I, f(S,B)=I, f(S,C)=If: f(S,A)=I, f(S,B)=I, f(S,C)=I f(S,1)=Z f(S,2)=Z f(S,3)=Z f(S,1)=Z f(S,2)=Z f(S,3)=Zf(I,A)=I f(I,B)=I f(I,C)=If(I,A)=I f(I,B)=I f(I,C)=If(I,1)=I f(I,2)=I f(I,3)=I f(I,f(I,1)=I f(I,2)=I f(I,3)=I f(I,)=I)=If(Z,1)=Z f(Z,2)=Zf(Z,3)=Z f(Z,f(Z,1)=Z f(Z,2)=Zf(Z,3)=Z f(Z,)=D)=D10 / 173.103.10 给出下述文法所对应的正规式。给出下述文法所对应的正规式。S S0A|1B0A|1BA A1S|11S|1B B0S|00S|0解解: :相应的正规式方程组为：相应的正规式方程组为：S=0A+1BS=0A+1BA=1S+1A=1S+1B=0S+0B=0S+0将，代入，得将，代入，得S=01S+01+10S+10S=01S+01+10S+10对使用求解规那么，得对使用求解规那么，得 (01|10) (01|10)* *11 / 1701|1001|10为所求。为所求。3.43.4 给出文法给出文法 GSGS，构造相应最小的，构造相应最小的 DFADFA。S-aS|bA|bS-aS|bA|bA- aSA- aS方法一：方法一：S=aS+bA+bS=aS+bA+bA=aSA=aSS=aS+baS+b S=(a+ba)*bS=aS+baS+b S=(a+ba)*b即：即：S=(a|ba)*bS=(a|ba)*b正规式正规式(a|ba)*b(a|ba)*b 对应的对应的 NFANFA：aX1b3正规式正规式(a|ba)*b(a|ba)*b 对应的对应的 DFADFA：QX 1 2 X1 2 13Y YaX化简后：化简后：aaXba1 2 11 2 11 2 1b3Y Y3 Y Ya2bYa1abYbY12 / 17方法二：方法二：P43P43 右线性正规文法到有穷自动机的转换右线性正规文法到有穷自动机的转换。文法文法 S-aS|bA|bS-aS|bA|bA- aSA- aS对应的对应的 NFANFA 为：为： M=(S,A,D,a,b,f,S,D) M=(S,A,D,a,b,f,S,D)其中：其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=Sf (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S其其 NFANFA 图为：图为：a S bAabDNFANFA 确定化后的状态矩阵为确定化后的状态矩阵为: :12NFANFA 确定化后的确定化后的 DFADFA 为：为：ab 12a13 / 17QSA,D aSSb A,D3.5 给出下述文法所对应的正规式：给出下述文法所对应的正规式：S-aAS-aAA-bA+aB+bA-bA+aB+bB-aAB-aA解：将文法改为：解：将文法改为：S=aAS=aAA=bA+aB+bA=bA+aB+bB=aAB=aA将代入，得将代入，得A=bA+aaA+bA=bA+aaA+b将用求解规那么，得将用求解规那么，得* * *A= (b|aa)A= (b|aa) b b, ,带入得，带入得，S= a(b|aa)S= a(b|aa) b,b,* *故文法所对应的正规式为故文法所对应的正规式为 R= a(b|aa)R= a(b|aa) b b。3.63.6 给出与以下图等价的正规文法给出与以下图等价的正规文法 G G。a AaBb Cb abDb答答: : 该有穷自动机为该有穷自动机为: :M=(A,B,C,D,a,b,f,A,C,D)M=(A,B,C,D,a,b,f,A,C,D)其中其中 f(A,a)=B, f(A,b)=D, f(B,a)=f(A,a)=B, f(A,b)=D, f(B,a)=, f(B,b)=C, f(B,b)=C,f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=Df(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D根据其转换规那么，与其等价的正规文法根据其转换规那么，与其等价的正规文法 G G 为为G=G=A,B,C,D,a,b,P,AA,B,C,D,a,b,P,A, ,其中其中P : AP : AaB|bD BbC CaA|bD| DaB|baB|bD BbC CaA|bD| DaB|bD D|14 / 173.12.3.12.解释以下术语和概念：解释以下术语和概念：(1)(1)确定有穷自动机确定有穷自动机答：一个确定有穷自动机答：一个确定有穷自动机 M M 是一个五元组是一个五元组 M=M=Q Q，f f，S S，Z Z ，其中：其中：Q Q 是一个有穷状态集合，每一个元素称为一个状态；是一个有穷状态集合，每一个元素称为一个状态；是一个有穷输入字母表，每个元素称为一个输入字符；是一个有穷输入字母表，每个元素称为一个输入字符；f f 是一个从是一个从 Q*Q* 到到 Q Q 的单值映射；的单值映射；f fq qi i,a,a=q=qj j (q (qi i,q,qj jQ,a)Q,a)表示当前状态为表示当前状态为 q qi i， 输入字符为输入字符为 a a 时，时， 自动机将转换到下一个状态自动机将转换到下一个状态 q qj j,q,qj j称为称为 q qi i的一个后继状态。的一个后继状态。 我们说状态转换函数是单值函数，我们说状态转换函数是单值函数， 是指是指 f f q qi i,a,a惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。入字符不同。SQ，是惟一的一个初态；SQ，是惟一的一个初态；Z Z 真包含于真包含于 Q Q，是一个终态集。，是一个终态集。2 2非确定有穷自动机非确定有穷自动机一个非确定有穷自动机一个非确定有穷自动机 M M 是一个五元组是一个五元组 M=M=Q Q， f f，S S，Z Z ，其中：其中：Q Q 是一个有穷状态集合，每一个元素称为一个状态；是一个有穷状态集合，每一个元素称为一个状态；是一个有穷输入字母表，每个元素称为一个输入字符；是一个有穷输入字母表，每个元素称为一个输入字符；状态转换函数是一个多值函数。状态转换函数是一个多值函数。f fq qi i,a,a=某些状态的集合某些状态的集合(q(qi iQ)，表示不能由当前状态、Q)，表示不能由当前状态、当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。对同一输入字符有不同的输出边。S S包含于包含于 A A，是非空初态集。，是非空初态集。Z Z 真包含于真包含于 Q Q，是一个终态集。，是一个终态集。3 3正规式和正规集正规式和正规集有字母表=a1,a2,an，在字母表有字母表=a1,a2,an，在字母表 上的正规式和它所表示上的正规式和它所表示的正规集可用如下规那么来定义：的正规集可用如下规那么来定义：1 1是是 是的正规式，它所表示的正规集是是的正规式，它所表示的正规集是，即空集，即空集。2 2 是是 上的正规式，它所表示的正规集仅含一空符号串，即上的正规式，它所表示的正规集仅含一空符号串，即 。 。3 3是是 上的一个正规式，上的一个正规式，它所表示的正规集是由单个符号它所表示的正规集是由单个符号 aiai 所组所组成，即成，即aiai。4 4e1e1 和和 e2e2 是是 是的正规式，它们所表示的正规集分别为是的正规式，它们所表示的正规集分别为 L(e1)L(e1)和和L(e2),L(e2),那么那么e1 | e2e1 | e2 是是 上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为L(e1 | e2)=L(e1)L(e2).L(e1 | e2)=L(e1)L(e2). e1e2e1e2 是是 上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为 L(e1e2)=L(e1)L(e2). L(e1e2)=L(e1)L(e2). (e1)*(e1)*是是 上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为15 / 17 L(e1)*)=L(e1)*.31 构造以下正规式相应的DFA。(1) 1 ( 0 | 1)*101(2) ( a | b )*( aa | bb )( a | b )*(3) ( 0 | 1 )* | ( 11 )*(4) ( 0 | 11*0 )*32 将下面图(a)和(b)分别确定化和最小化.aa 0 1a,b(a)b ba 02b3aaaabba145bb3.3 构造一个 DFA，他接收=0，1上所有满足如下条件的字符串， 每个 1 都有 0 直接跟在右边。3.4 给出文法 GS，构造相应最小的 DFA。 SaS | bA | b AaS3.5 给出下述文法所对应的正规式：S-AaA-bA+aB+bB-aA3.6 给出与以下图等价的正规文法G。a AaBb Cb ab16 / 17Db3.8 文法 G单词为：单词 标识符| 整数标识符 标识符 字母| 标识符 数字|字母整数 数字|整数 数字字母 A | B | C数字1 | 2 | 3（1）改写文法 G 为 G，使 L(G)=L(G).（2）给出相应的有穷自动机。3.9 试证明正规式a|b*与正规式a*|b*是等价的。310 给出下述文法所对应的正规式： S 0A | 1BA 1S | 1B 0S | 0311 设字母表=a,b，给出上的正规式 R=b*ab(b | ab)*.(1) 试构造状态最小化的 DFA M，使得 LM=LR 。(2) 求右线性文法 G，使 LG=LM 。312 解释以下术语和概念。（1）确定有穷自动机（2）非确定有穷自动机（3）正规式和正规集17 / 17