《第04章词法分析》由会员分享，可在线阅读，更多相关《第04章词法分析（14页珍藏版）》请在金锄头文库上搜索。
1、第4章词法分析第1题构造下列正规式相应的DFA.(1 ) 1(011)1*101(2 ) 1(1010*11(010)*1) *0(3 ) a(alb)*lab*a)*b(4 ) b(ab)*lbb)*ab01XAAAABABACABACAABYABYACAB01XAAABBCBCADDCB的终态)，所以D为终态。DFAlWtWr 先构造NFA：WX, A夕卜，重新命名其它状态,令AB为B、AC为C、ABY为因为D音有Y (NFAe01XXTo=XAAABFLT1=ABFLYCGYYCGCGJt2=yT3= CGJDHKDHDHKABFKLt4=dhElElABEFILt5=abfklYCGt
2、6= abefilEJYCGEJYABEFGJLYt7= abefgjlyEHYCGKEHYABEFHLYCGKABCFGJKLt8=abefhlyEYCGIEYABEFLYCGICGJIt9=abcfgjklDHYCGKDHYDHYTw= ABEFLYEYCGTn= CGJIDHJKDHJDHJTi2= DHYElti3=dhjEIKEIKABEFIKLT14= abefiklEJYCG将To、T1、T2、T3、T4、T5、丁6、丁7、丁8、T9、Tio、T11 、T12、T13、T14重新命名,分别用0、1、2、3、4、5、6、7、8、9、10、11、12、13、14 表示。因为2、7、8
3、、10、12 中含有Y, 所以它们 都为终态。0101123234546523673789810119129101031113512613141473用子集法将NFA确定化EabXXT0=XAAABCDTi=ABCDBEBYBEABCDEBYABCDYt2=abcdeBEFBEYBEFABCDEFBEYABCDEYt3=abcdyBEBYt4=abcdefBEFBEYt5=abcdeyBEFBEY将To、Ti、T2、T3、T4、T5重新命名，分别用0、I、2、3、4、5表示。因为3、5中含有Y, 所以它们都为终态。ab01123245323445545用子集法将NFA确定化:eabXXT0=X
4、AAABDEFTi=ABDEFCIGCICIGGt2=ciDYDYABDEFYt3=gHHABEFHt4=abdefyCIGt5=abefhCIG将To、Ti、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y, 所以它为终态。ab011232435423523DFA的状态图:(4) 先构造NFA：第2题已知NFA = (x,y,z,0,l,M,x,z)其中：M(x,0)=z, M(y,0)=x,y, ,M(z,0)=x,z, M(x,l)=x, M(y,l)=d, M(z,l)=y,构造相应的DFA。答案：先构造其矩阵01XZXyx,yZx,zy用子集法将NFA
5、确定化:01XzXzxzyxzxzxyyxyxyxyzXxyzxyzxy将X、z xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C F 中含有z,所以它为终态。01ABABCDCCEDEEFAFFE0DFA的狀態圖:第3题将下图确定化:01SVQVVQQVQVzzVzQVQzzz重新命名状态子集，令VQ厉AQUB、VZ为C、V为D、QUZ为E、Z孑F。01SABACBBDECFFDFECEFFF将下图的(a)和(b)分别确定化和最小化: 答案：初始分划得no：终态组0,非终态组1,2,3,4.5对非终态组进行审查：1,2,3,4,5a 口0丄3,5而0,1,3,5既
6、不属于0,也不属于123,4,54au 0,所以得到新分划ni： 0, 4, 1,2,3,5对1,2,3,5进行审查；1,5吐42,3 b u 123,5,故得到新分划112： 0, 4, 1,5, 2,31,5 a ul,52,3 a ul,3,故状态2和状态3不等价，得到新分划113： 0, 2,，4, 1,5这是最后分划了最小DFA：DFA的状态图:第5题 构造一个DFA,它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并 给出该语言的正规式。答案：按题意相应的正规表达式是(0* 10)*0*,或0*(0门0)*0*构造相应的DFA,首先构造NFA为用子集法确定化:I
7、10IIX,O,1,3,Y0 丄 3,Y20 丄 3,Y0,l,3,Y221,3,Y重新命名状态集：S0112322334DFA的状态图:可将该DFA最小化：终态组为1,2,4,非终态组为，1,2,40 1,2,4, 1,2,4 1 3,所以1,2,4为等价状 态，可合 并。第6题 设无符号数的正规式为e:0 =dd* I dd* .dd* I .dd* I dd* 10( s I e )dd*ll0(s I e ) dd*l.dd*10(s I e ) dd*ldd*.dd*10( s I e )dd* 化简 e,画出 o 的DFA，其中d=0,l,2,-,9, s= + , -答案： 先构
8、造NFA：用子集法将NFA确定化:s10dXXAT0=XABFABBFFGAATi=BCCCt2=fgGHGGHHT3=ABFAt4=cDCDDEt5=gHt6=hHt7=deEYEEYYt8=eYt9=yYs10d012314256312347456667898999将XA、B、FG、A、C、G、H、DE、E、Y 重新命名，分别用0、1、2、3、4、5、6、7、8、9 表示。终态有0、3、4、6、9。DFA的状态图:第7题给文法GS： S-aAlbQDb BlaA EaBIbF构造相应的最小的DFA。 答案：Af aAlbBIbF-bDlaElbBbDIaQQaQIbDIb先构造其NFA：用
9、子集法将NFA确定化:abSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、 4中含有z,所以它们为终态。ab012113224325416516625DFA的状态图:令Po= ( 0,1,2,5,6 , 3,4)用b进行分割：Pi= ( 0,5,6 , 1,2 , 3,4)再用b进行分割：P2=( 0 , 5,6 , 1,2 , 3,4)再用a、b进行分割，仍不变。再令 0 为A, 1, 2为B, 3, 4为C, 5,6为D。最小化为：第8题给出下述文法所对应的正规式：S-0AI1B A1SI1BOSIO
10、答案：解方程组s的解：S=OAI1B A=1SI1B=OSIO将A、B产生式的右部代入S中S=O1SIO1I1OSI1O= (OHIO) SI (OHIO)所以：s= (01110)*(01110)第9题将下图的DFA最小化，并用正规式描述它所识别的语言。答案：令Po= ( 123,4,5 , 6,7)用b进行分割：Pi= ( 1,2 , 3,4 , 5 , 6,7)再用a、 b、c、d进行分割，仍不变。再令1,2为A, 3, 4为B, 5为C, 6, 7为D。最小化为:r=b*a(c I da)*bb*=b*a( c I da)*b*附加题问题1：为下边所描述的串写正规式，字母表是a,b.a) 以ab结尾的所有串b) 包含偶数个b但不含a的所有串c) 包含偶数个b且含任意数目a的所有串d) 只包含一个a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串 答案：注意正规式不唯一
