编译原理-第2章习题课

1、1.构造正规式的 DFAQ10XAABC B0ABC BBCD CBC DBCD CBCD CBCE EBCDBCD CBC DBCE EBCDY YBC DBCDY YBCD CBCE E10ABBCDCCEDCDEYDYCE化简后得:2(a|b)*(aa|bb)(a|b)*所以，DFA为:NFA化为DFAQabX 1 21 2 31 2 41 2 31 2 3 5 Y1 2 4 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

2、Y1 2 4 YQ10X A Y XB C D AA YBB C D AC DYA YBA YBB C D AA YBC DYC DYA YB3 0|11*0*£0NFA到 DFA0D£CA1BA101Y0B0化简后得;12.将以下列图确定化和最小化aaa,b解：首先取A=£ -CLOSURE(0)=0,NFA确定化后的状态矩阵为Q'abA00,11B0,10,11C100NFA确定化后的DFA为:3.构造一个DFA它承受刀=0 , 1上所有满足如下条件的字符串,每个1都有0直接跟在后边。解：按题意相应的正规表达式是0*(0 | 10)*0*构造相应的DF

3、A首先构造NFA为1 0用子集法确定化II 011S01X,0,1,3,Y0,1,3,Y21230,1,3,Y0,1,3,Y222321,3,Y/341,3,Y1,3,Y2443DFA为144.给出NFA等价的正规式R 方法一：首先将状态图转化为NFA等价的正规式为0|1*11方法二：NFL右线性文法正规式A 0A|1A|1BB 1CC£A=0A+1A+1BB=1A=0A+1A+11A=(0+1)*11(0|1) *115. 试证明正规式a|b*与正规式a*|b*是等价的aNFA 为=>证明:正规式 a|bbabX, i,yi,yi,yi,yi,yi,ya其最简DFA为=>

4、;b正规式a*|b*的NFA为:a其最简化DFA为：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=bab(b|ab)。(1) 试构造状态最小化的DFAM使得L M =L F(2) 求右线性文法G,使LG=L解：(1)构造NFA:b将其化为DFA转换矩阵为：QabX,1,21321,23324,5,Y41,23321,234,5,丫4655,Y665r 5,y65,Y6655,Y6b再将其

5、最小化得2对应的右线性文法 G= X,W,Y,a,b,P,XP: X aW|bXWAbY|b y aW|bY|b3.8文法G单词为：单词-标识符|整数标识符-标识符字母|标识符数字|字母整数-数字|整数数字字母-A|B|C数字卜1|2|31改写文法G为G ,使L(G' )=L(G)。2给出相应的有穷自动机。解：1令D代表单词，I代表标识符，Z代表整数，有G D:D I | ZI A | B | C | IA | IB | IC | I1 | I2 | I3Z 1 | 2 | 3 | Z1 | Z2 | Z3(2)左线性文法G所对应的有穷自动机为：M=(S,D,I,Z,1,2,3,A,B

6、,C,f,S,D)f: f(S,A)=I, f(S,B)=I, f(S,C)=If(S,1)=Z f(S,2)=Z f(S,3)=Zf(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)=Zf(Z,3)=Z f(Z,& )=D3.10给出下述文法所对应的正规式St 0A|1BA 1S|1Bt 0S|0解：相应的正规式方程组为：S=0A+1B A=1S+1B=0S+0将，代入，得S=01S+01+10S+10 对使用求解规那么，得01|10 * 01|10丨为所求。3.4给出文法

7、GS，构造相应最小的DFAS->aS|bA|bA-> aS方法一：S=aS+bA+bA=aSS=aS+baS+b a+ba)*b即：S=(a|ba)*b正规式(a|ba)*b 对应的NFA正规式(a|ba)*b 对应的DFAQabX 1 2 X1 2 13Y Y1 2 11 2 13 Y Y3Y Y1 2 1中b方法二：P43右线性正规文法到有穷自动机的转换。文法 S->aS|bA|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)=SNFA确定化后的DFA为: abNFA

8、确定化后的状态矩阵为Q'ab1SS A,D2A,D S03.5给出下述文法所对应的正规式:S->aAA->bA+aB+bB->aA解：将文法改为：S=aAA=bA+aB+bB=aA将代入，得A=bA+aaA+b将用求解规那么，得A= (b|aa) *b ，带入得，S= a(b|aa) *b, 故文法所对应的正规式为R= a(b|aa) *b。3.6给出与以下列图等价的正规文法G答：该有穷自动机为：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

9、,a)=B, f(D,b)=D根据其转换规那么，与其等价的正规文法G为G= A,B,C,D,a,b,P,A 丨，其中P : A taB|bD B 宀bC CaA|bD| £ D aB|b D £3.12.解释以下术语和概念：(1)确定有穷自动机答：一个确定有穷自动机 M是一个五元组M=Q工，f , S, Z， 其中：Q是一个有穷状态集合，每一个元素称为一个状态； 工是一个有穷输入字母表，每个元素称为一个输入字符； f是一个从Q*2到Q的单值映射； f qi,a=q (q i,qj Q,aX)表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj 称为q i的

10、一个后继状态。我们说状态转换函数是单值函数，是指f qi,a 惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输 入字符不同。S Q 是惟一的一个初态；Z真包含于Q, 是一2非确定有穷自动机一个非确定有穷自动机 M是一个五元组M=Q,X, f，S, Z，其中： Q是一个有穷状态集合，每一个元素称为一个状态； 工是一个有穷输入字母表，每个元素称为一个输入字符； 状态转换函数是一个多值函数。fqi ,a=某些状态的集合(q i Q),表示不能由当前状态、 当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态 对同一输入字符有不同的输出边。S 包含于A，是非空初态集。Z真包含于Q

11、3正规式和正规集有字母表工=a1,a2,an,在字母表 工 上的正规式和它所表示 的正规集可用如下规那么来定义：10是工是的正规式，它所表示的正规集是 0，即空集。2&是工上的正规式，它所表示的正规集仅含一空符号串，即汀。3是工上的一个正规式，它所表示的正规集是由单个符号 ai所组 成，即ai。4el和e2是工是的正规式，它们所表示的正规集分别为L(e1)和L(e2),那么 e1 | e2是工上的一个正规式，它所表示的正规集为L(e1 | e2)=L(e1) U L(e2). e1e2是工上的一个正规式，它所表示的正规集为L(e1e2)=L(e1)L(e2). (e1)*是工上的一个正

12、规式，它所表示的正规集为L(e1)*)=L(e1)*3. 1构造以下正规式相应的DFA(1) 1 ( 0 | 1)*101(2) ( a | b )*( aa | bb )( a | b )*(3) ( 0 | 1 )* | ( 11 )*(4) ( 0 | 11*0 )*3. 2将下面图(a)和(b)分别确定化和最小化aaa,baaababba 丿b3.3构造一个DFA他接收刀=0 , 1上所有满足如下条件的字符串，每个1都有0直接跟在右边。3.4给出文法GS，构造相应最小的 DFASaSbA | bAaS3.5给出下述文法所对应的正规式：S->AaA->bA+aB+bB->aA3.6给出与以下列图等价的正规文法G3.8文法G单词为：单词标识符| 整数标识符标识符字母| 标识符数字|字母整数数 _整数数字字母A | >B | C数字1 | 2->(1) 改写文法G为G',使L(G' )=L(G).(2) 给出相应的有穷自动机。3.9试证明