《第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子串的所有串 答案:注意正规式不唯一