编译原理第2章习地训练题目课

1.构造正规式的 DFA 。NFA 化为 DFA :状态转换表：Q10XAABCBABCBBCDCBCDBCDCBCDCBCEEBCDBCDCBCDBCEEBCDYYBCDBCDYYBCDCBCEE1初态10ABBCDCCEDCDEYDYCE化简后得：0(2) (a|b)*(aa|bb)(a|b)*aNFA 化为 DFA :QabX 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 Y1 2 4 Y所以，DFA为:a化简得:011 .NFA 至U DFA :Q10X A YXB C DAA YBB C DAC DYA YBA YBB C DAA YBC DYC DYA YB精彩文档A1010B化简后得;2. 将下图确定化和最小化解：首先取A= &CLOSURE(0)=0, NFA确定化后的状态矩阵为Q'abA00,11B0,10,11C100NFA确定化后的DFA为:C将A,B合并得:3. 构造一个DFA，它接受刀二0 , 1上所有满足如下条件的字符串, 每个1都有0直接跟在后边。解：按题意相应的正规表达式是0*(0 | 10)*0*构造相应的DFA，首先构造NFA为>k用子集法确定化IIoIiS01X,0,1,3,Y0,1,3,Y21230,1,3,Y0,1,3,Y222321,3,Y/341,3,Y1,3,Y2443DFA为二* 1 0 24. 给出NFA等价的正规式R。消去0, 1(0|1 ) *11NFA等价的正规式为（叩）*11方法二：NFA 右线性文法正规式A0A|1A|1BB 1CA=0A+1A+1BB=1A=0A+1A+11A=(0+1) *11 (0|1) *115. 试证明正规式（a|b ） *与正规式（a*|b*） *是等价的证明:正规式 (a|b)abX, i,yi,yi,yi,yi,yi,y其最简DFA为正规式(a*|b*bNFA 为:其最简化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:b324,5,Y41,23321,234,5,Y4655,Y66505,Y65,Y6655,Y6再将其最小化得：2XWabb(2)对应的右线性文法 G= (X,W,Y,a,b,P ,X)P: XaW|bX WbY|by aW|b Y|b3.8文法G单词为：单词-标识符|整数标识符-标识符字母|标识符数字|字母 整数-数字|整数数字字母-A|B|C数字卜1|2|3(1 )改写文法G为G '使L(G ' )=L(G)。(2 )给出相应的有穷自动机。解：(1 )令D代表单词，I代表标识符，Z代表整数，有G'( D):D I | ZIA | B | C | IA | IB | IC | 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)=If(S,1)=Zf(S,2)=Zf(S,3)=Zf(I,A)=If(I,B)=If(I,C)=If(I,1)=If(I,2)=If(I,3)=If(I,e) = If(Z,1)=Zf(Z,2)=Zf(Z,3)=Zf(Z,沪D3.10给出下述文法所对应的正规式St 0A|1BA t 1S|1Bt 0S|0解：相应的正规式方程组为：S=0A+1BA=1S+1B=0S+0将，代入，得S=01S+01+10S+10对使用求解规则，得（01|10） * （ 01|10 ）为所求。3.4给出文法 GS，构造相应最小的 DFA。S->aS|bA|bA-> aS方法一：S=aS+bA+bA=aSAS=aS+baS+bS=(a+ba)*b即: S=(a|ba)*b正规式ba)*b 对应的NFA :正规式(a|ba)*b 对应的DFA :QabX 1 2X1 213Y丫1 2 11 213 Y0 丫3丫丫1 21化简后:方法二：P43右线性正规文法到有穷自动机的转换文法 S->aS|bA|bA-> aS对应的NFA为：M=(S,A,D,a,b,f,S,D)f(A,a)=S其中：f (S,a)=S,f(S,b)=A,f(S,b)=D,其NFA图为:a1 F精彩文档DNFA确定化后的状态矩阵为Q'ab1SS A,D2A,D S0NFA确定化后的DFA为:1愛23.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,a)=B, f(D,b)=D根据其转换规则，与其等价的正规文法G为G= (A,B,C,D,a,b,P ,A)，其中P : A t aB|bD B bC C aA|bD| £ D aB|bD| £3.12.解释下列术语和概念：(1)确定有穷自动机答：一个确定有穷自动机 M是一个五元组M= (Q,，f, S, Z),其中：Q是一个有穷状态集合，每一个元素称为一个状态；工是一个有穷输入字母表，每个元素称为一个输入字符；f是一个从Q*工到Q的单值映射； f (qi,a) =q j (qi,qj Q,a 习表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj 称为qi的一个后继状态。我们说状态转换函数是单值函数，是指f(qi,a) 惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入 字符不同。S Q，是惟一的一个初态；Z真包含于Q , 是一 -个终态集(2)非确定有穷自动机一个非确定有穷自动机 M 是一个五元组 M= (Q,，f,