编译原理 第2章习习题课

1、1.构造正规式的DFA。（1）1(0|1)*1010YXCADBE首先构造NFA：0X11E1DCBA1NFA化为DFA：状态转换表：Q10X AABC BABC BBCD CBC DBCD CBCD CBCE EBC DBCD CBC DBCE EBCDY YBC DBCDY YBCD CBCE E1状态转换图：0110110YABCDE10 初态010ABBCDCCEDCDEYDYCE化简后得：01ABEY1101001C（2）(a|b)*(aa|bb)(a|b)*X12345Yaabbabab NFA化为DFA：QabX 1 21 2 31 2 41 2 31 2 3 5 Y1 2 4

2、1 2 41 2 31 2 4 5 Y1 2 3 5 Y1 2 3 5 Y1 2 4 Y1 2 4 5 Y1 2 3 Y1 2 4 5 Y1 2 4 Y1 2 3 Y1 2 4 5 Y1 2 3 Y1 2 3 5 Y1 2 4 Ya所以，DFA为：X123456ababbabbabaab化简得：1XY2baababab01BCDYXA10（3）（0|11*0）*NFA到DFA：Q10X A Y XB C D AA Y BB C D AC D YA Y BA Y BB C D AA Y BC D YC D YA Y BABYX10100110化简后得；XA10012.将下图确定化和最小化。aa&

3、#222; 0 1 a,b解: 首先取A=-CLOSURE(0)=0, NFA确定化后的状态矩阵为:QabA00,11B0,10,11C10NFA确定化后的DFA为：aaÞABabbC将A,B 合并得:abÞ ACa3.构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。解：按题意相应的正规表达式是0*(0 | 10)*0* 构造相应的DFA，首先构造NFA为 0 0 03 1 0 X Y 1 02 用子集法确定化II0I1S01X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y22/21234224

4、4333DFA为 01 02 1 1 0 13 4 04.给出NFA等价的正规式R。 方法一：首先将状态图转化为BYCBAX11消去得0,1YCAX 11 消去其余结点、0，1YX（0|1）*11NFA等价的正规式为（0|1）*11方法二：NFA右线性文法正规式A0A|1A|1BB1CCA=0A+1A+1BB=1A=0A+1A+11A=(0+1)*11(0|1)*115.试证明正规式（a|b）*与正规式（a*|b*）*是等价的。 a证明：(1)Y1X正规式(a|b)*的NFA为 => b abX, 1,y1,y1,y1,y1,y1,yaA 其最简DFA为 =>b(2)正规式（a*|

5、b*）*的 NFA为：3a其最简化DFA为：aA2Y1 => X =>bb DFA的状态转换表：abx,1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|b*)*。6.设字母表=a,b,给出上的正规式R=b*ab(b|ab)*。（1） 试构造状态最小化的DFA M，使得L（M）=L（R）。（2） 求右线性文法G，使L（G）=L（M）。解: (1)构造NFA:X123Ybab456abb (2)将其化为DFA,转换矩阵为:QabX,1,2 13 21,2 33 24,5,Y

6、41,2 33 21,2 34,5,Y 46 55,Y 66 55,Y 65,Y 66 55,Y 6123456abbababbba再将其最小化得:XWYabbab（2）对应的右线性文法G=（X,W,Y,a,b,P,X）P: XaW|bX WbY|b yaW|bY|b 文法G单词为：单词-标识符|整数标识符-标识符字母|标识符数字|字母整数-数字|整数数字字母-A|B|C数字|->1|2|3（1）改写文法G为G，使L(G)=L(G)。（2）给出相应的有穷自动机。解：（1）令D代表单词，I代表标识符，Z代表整数，有G（D）：DI | Z IA | B | C | IA | IB | IC

7、| I1 | I2 | I3Z1 | 2 | 3 | Z1 | Z2 | Z3(2) 左线性文法G所对应的有穷自动机为：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)=I f(S,1)=Z f(S,2)=Z f(S,3)=Z f(I,A)=I f(I,B)=I f(I,C)=If(I,1)=I f(I,2)=I f(I,3)=I f(I, )=If(Z,1)=Z f(Z,2)=Z f(Z,3)=Z f(Z, )=D给出下述文法所对应的正规式。S0A|1BA1S|1B0S|0解: 相应的正规式方程组为：S=0A+1B A=1S

8、+1 B=0S+0 将，代入，得S=01S+01+10S+10 对使用求解规则，得 (01|10)* （01|10）为所求。给出文法GS，构造相应最小的DFA。S->aS|bA|bA-> aS 方法一：S=aS+bA+bA=aS S=aS+baS+b S=(a+ba)*b即：S=(a|ba)*b 正规式(a|ba)*b对应的NFA：X1Y2ab3ab正规式(a|ba)*b对应的DFA：QabX 1 2 X1 2 13Y Y1 2 11 2 13 Y Y3Y Y1 2 1X1Yaabab化简后： XY1baa方法二：P43 右线性正规文法到有穷自动机的转换。文法S->aS|bA

9、|bA-> aS 对应的NFA为： M=(S,A,D,a,b,f,S,D)其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S 其NFA图为：aÞ S bAabDNFA确定化后的状态矩阵为: Qab1SS A,D2A,D SNFA确定化后的DFA为：abÞ 12a给出下述文法所对应的正规式：S->aAA->bA+aB+bB->aA解：将文法改为：S=aA A=bA+aB+b B=aA将代入，得A=bA+aaA+b 将用求解规则，得A= (b|aa)*b ,带入得，S= a(b|aa)*b,故文法所对应的正规式为R= a

10、(b|aa)*b。给出与下图等价的正规文法G。aÞ AaBb Cb abDb答: 该有穷自动机为:M=(A,B,C,D,a,b,f,A,C,D)其中f(A,a)=B, f(A,b)=D, f(B,a)=, f(B,b)=C,f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D根据其转换规则，与其等价的正规文法G为G=（A,B,C,D,a,b,P,A）,其中P : AaB|bD BbC CaA|bD| DaB|bD|.解释下列术语和概念：(1)确定有穷自动机答：一个确定有穷自动机M是一个五元组M=（Q，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个

11、状态；是一个有穷输入字母表，每个元素称为一个输入字符；f是一个从Q*到Q的单值映射；f（qi,a）=qj (qi,qjQ,a)表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj称为 qi 的一个后继状态。我们说状态转换函数是单值函数，是指 f（qi,a） 惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。SQ，是惟一的一个初态；Z 真包含于Q，是一个终态集。（2）非确定有穷自动机一个非确定有穷自动机M是一个五元组M=（Q，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个状态；是一个有穷输入字母表，每个元素称为一个输入字符；状态转换函数是

12、一个多值函数。f（qi,a）=某些状态的集合(qiQ)，表示不能由当前状态、当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。S 包含于 A，是非空初态集。Z 真包含于 Q，是一个终态集。（3）正规式和正规集有字母表=a1,a2,an，在字母表上的正规式和它所表示的正规集可用如下规则来定义：（1）是是的正规式，它所表示的正规集是，即空集。（2）是上的正规式，它所表示的正规集仅含一空符号串，即 。（3）是上的一个正规式，它所表示的正规集是由单个符号ai 所组成，即ai。（4）e1和e2是是的正规式，它们所表示的正规集分别为L(e1)和L(e2),则e1 |

13、e2是上的一个正规式，它所表示的正规集为 L(e1 | e2)=L(e1)L(e2).e1e2是上的一个正规式，它所表示的正规集为 L(e1e2)=L(e1)L(e2).(e1)*是上的一个正规式，它所表示的正规集为 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 1 a,b(a)b baÞ 02b3aaaabba145b（b）构造一个DFA，他接收=0，1上所有满足如下条件的字符串，每个1都有0直接跟在右边。给出文法GS，构造相应最小的DFA。 SaS | bA | b AaS给出下述文法所对应的正规式：S->AaA->bA+aB+bB->aA给出与下图等价的正规文法G。aÞ AaBb Cb abDb给出与图中的NFA等价的正规式R。 文法G单词为：单词标识符| 整数标识符标识符字母| 标识符数字|字母整数数字|整数数字字母 A | B | C数字1 | 2 | 3（1） 改写文法G为G，使L(G)=L(G).（2） 给出相应