第四章 作业讲解参考答案docx.docx

1、第四章 作业讲解参考答案docx第四章作业讲解(参考答案)1.构造下列正规式相应的DFA。(1)1(011)*101(2)1(1010*11(010)*1)*0(3)a(a|b)*|ab*a)*b(4)b(ab)*|bb)*ab确定化01XAAAABABACABACAABYABYACAB重新命名，令AB为B、AC为C、ABY 为 D01XAAABBCBCADDCB(2)解：先构造NFAM1010*11(010)*11(010)*1再构造状态转换矩阵表:I10IIS01X1,2,4X11,2,4y5,9,10,111Y25,9,10,116,124,22346,122,4,7,8,13354,2

2、y5,9,10,114Y22.4.7.8.13 2,4,8,10,11,y5,9,10,115622,4,2,4,&12,y2,4,5,9,10,116782,4,8,12,y2,4,&y5,9,10,11,1379102,4,5,9,10,116,12,y2,4,5,9,10,1181182,4,&y2,4,&y5,9,10,119925,9,10,11,136,10,11,122,4101446,12,y2,4,7,8,131156,10,11,12122,4,7,&13141551213151213(10,11121310,11122,413154(yY1解:Eb确定化:lalb-SAA

3、ABAZABABABZ+ AZABAZ+ ABZABABZ重新命名，以 0、1、2、3、4 代替 S , A, AB , AZ , ABZ得 DFA 其中0为初态，3, 4为终态。rzlaFEZ1匚23FZ22I2IDFA图省略确定化省略3、P72题3,图4.20确定化 解：01SVQQUVQVZQUQUVQUZVZZZVQUZZ重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。01sABACBBDECFFDFECEFFF(b)化简下列DFA为最小化。Vn与Vt分开只有4输入a进0,其他不会。2输入a进1, 1,3,5输入a进本身。P3= 0), 4 , 2, 3, 1,5

4、) 1,5 输入 b 进 4, 3 输入 b 进 2。所以，1和5是等价的点。DFA如下:D如果改为:结果为：Po=(0,1，2,3,4,5) Vn与 Vt分开Pi= (0,1, 2,4, 3,5)5、构造一个DFA,它接受=0,1上所有满足如下条件的字符串：每个1都有 0直接跟在右边，并写出相应的正规式和正规文法。解：按题意相应的正规表达式是0*(0 I 10)*0*或0*( 100*)*0*构造相应的DFA,首先构造NFA为用子集法确定化IIoIis01X,0,l,3,Y0丄3,丫21230,l,3,Y0 丄 3,Y22231,3,Y/341,3,Y1,3,Y2443DFA为可最小化,终态

5、组为1,2,4,非终态组为3, l,2,4（）u 1,2,4, 1,2,4】u 3,所以1,2,4 为等价状态，可合并。相应正规文法:SOSlsS-*1AAOS7、对以下文法构造相应最小的DFAS-*aA|bQA-*aA|bB|bB-*bD|aQQ-*aQ|bD|bD-*bB|aAE-*aB|bFF-*bD|aE|b解：1）化简文法，E和F是不可到达的，应删除。文法为:S-*aA|bQA-*aA|bB|bB-*bD|aQQ-*aQ|bD|bD-*bB|aA2）按正规文法到NFA转化方法，得到下图NFA：3）对NFA确定化，再最小化。得DFA如下:8、给出下述文法所对应的正规式:S0AI1BA-

6、1S|1B-OS|O解：SnOAnOl SnOAnOlSSnlBnlOSnlEnlOS 丿SnOlIlOSnOlSIlOS0(01)*1(10)*因此，Sn(01+10) +正规式：L(S) = (01|10) +PO=(6,7,1,2,3,4,5)PO=(6,7,1,2, 3,4,5) 输入 b 进入不同状态。PO=(6,7,1,2, 3,4,5) 3, 4 对 d 有定义,5 没有定义最小化DFA如下：正规式为：b*a(clda)*bb*10、构造下述文法GS的自动机：S-A0A-A0IS1I0解：SnAOnOOSnAOnAOOnOOOS=.=0 0SnAOnSlOnAOlOnOOlOSnAOnAOOnSlOOnAOlOOn S10100 n A010100 =0010100得出相应正规式：L(G(S)=(OI1)+,且由00开头，每一个1后面至少有一个012、证明下列正规表达式是等价的（用DFA方法）(alb)*a(sla)b*)*