第4章词法分析作业参考答案.doc

第4章词法分析作业参考答案4.7练习（P72）1构造下列正规式相应的DFA：(4) b(ab)*|bb)*ab解：先将正规式转换为NFA，转换过程如下：以下为最终所得的NFA图：然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0=1T1=2,4T1=2,4T2=5,6T3=3T2=5,6T4=2,4,7T3=3T1=2,4T4=2,4,7T2=5,6T3=3所得DFA图如下：最后，将此DFA化简后如下：4、把图4.21（a）和（b）分别确定化和最小化：(a)图【解】子集法：IaIb 00,110,10,1110-重命名：IaIb01211220确定化的DFA为：(b)图【解】【解】 初始划分得0：终态组0，非终态组1,2,3,4,5 对非终态组进行分割： 1,2,3,4,5a =0,1,3,5 而0,1,3,5既不属于0，也不属于1,2,3,4,5 4 a 0，所以得新划分1：0，4，1,2,3,5 对1,2,3,5进行分割： 1,5 b 4 2,3 b 1,2,3,5，故得新划分 2：0，4，1, 5，2,3 1, 5 a 1, 5 2,3 a 1,3，故状态2和状态3不等价，得新划分： 3：0，2，3，4，1, 5这是最后划分最小DFA：7给文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAEaB|bFFbD|aE|b构造相应的最小的DFA。【解】首先，将正规式转换成NFA如下：然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0=ST1=AT2=QT1=AT1=AT3=Z,BT2=QT2=QT4=Z.DT3=Z,BT2=QT5=D T4=Z.DT1=AT6=BT5=D T1=AT6=BT6=BT2=QT5=D 所得DFA图如下：化简后的最后划分为：T0=T0,T1=T1,T2,T3=T3,T4,T5=T5,T6,其中T3为终态。最后，将此DFA化简后如下：8给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0【解】由题意得：A=1S|1，B=0S|0 ，S0A|1B，将A，B右端代入S的产生式得：S0(1S|1)|1(0S|0)=01S|01|10S|10=(01|10)| (01|10)SS(01|10)| (01|10)SS=(01|10)| (01|10)*该文法所对应的正规式为：(01|10)| (01|10)*9将图4.22的DFA最小化，并用正则式描述所识别的语言。【解释】初始划分得0：6，7，1，2，3，4，51，2a=3，4 1，2b=2，4 1，2c，d=空3，4a=空 3，4b=6，7 3，4c=35a=4 5b=空 5d=空6，7b=6 6，7a，d，c=空最终划分为：1=1，2，2=3，4，3=5，4=6，7 最小化DFA是：正则式为:b*a(c*|(da)*)bb*【 本章其他作业参考答案】1.构造正规式1(0|1)*101相应的DFA. 【答案】 先构造NFA 确定化 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB 重新命名，令AB为B、AC为C、ABY为D 0 1 X A A A B B C B C A D D C B DFA： 3.将下图确定化：【答案】 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z QUZ VZ QUZ Z Z Z 重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 0 1 S A B A C B B D E C F F D F E C E F F F DFA： 5. .构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。 【答案】 按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0* 构造相应的DFA，首先构造NFA为用子集法确定化 I I0 I1 S 0 1 X,0,1,3,Y 0,1,3,Y 2 1,3,Y 0,1,3,Y 0,1,3,Y 1,3,Y 1,3,Y 2 2 / 2 1 2 3 4 2 2 4 4 3 3 3 DFA： 可最小化，终态组为1,2,4，非终态组为3，1,2,40 1,2,4，1,2,41 3，所以1,2,4为等价状态，可合并。【补充】为下边所描述的串写正规式，字母表是 a,b. a) 以ab 结尾的所有串 b) 包含偶数个b但不含a的所有串 c) 包含偶数个b且含任意数目a的所有串 d) 只包含一个a的所有串 e) 包含ab子串的所有串