资源描述：
《第4章词法分析作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章词法分析作业参考答案4.7练习（P72）1．构造下列正规式相应的DFA：(4)b((ab)*
2、bb)*ab解：先将正规式转换为NFA，转换过程如下：以下为最终所得的NFA图：然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0={1}ΦT1={2,4}T1={2,4}T2={5,6}T3={3}T2={5,6}ΦT4={2,4,7}T3={3}ΦT1={2,4}T4={2,4,7}T2={5,6}T3={3}所得DFA图如下：最后，将此DFA化简后如下：4、把图4.21（a）和（b）分别确定化和最小化：(a)图【解】子集法：IaIb{0}{0,1}{
3、1}{0,1}{0,1}{1}{1}{0}-重命名：IaIb01211220¢确定化的DFA为：(b)图【解】 【解】初始划分得Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组进行分割：{1,2,3,4,5}a={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和状态
4、3不等价，得新划分：Π3：{0}，{2}，{3}，{4}，{1,5}这是最后划分最小DFA：7．给文法G[S]：S→aA
5、bQA→aA
6、bB
7、bB→bD
8、aQQ→aQ
9、bD
10、bD→bB
11、aAE→aB
12、bFF→bD
13、aE
14、b构造相应的最小的DFA。【解】首先，将正规式转换成NFA如下：然后，将此NFA转换为DFA：转换关系矩阵如下表：CTaTbT0={S}T1={A}T2={Q}T1={A}T1={A}T3={Z,B}T2={Q}T2={Q}T4={Z.D}T3={Z,B}T2={Q}T5={D}T4={Z.D}T1={A}T6={B}T5={D}T1={A}T6={B
15、}T6={B}T2={Q}T5={D}所得DFA图如下：化简后的最后划分为：T0={T0},T1={T1,T2},T3={T3,T4},T5={T5,T6},其中T3为终态。最后，将此DFA化简后如下：8．给出下述文法所对应的正规式：S→0A
16、1BA→1S
17、1B→0S
18、0【解】由题意得：A=>1S
19、1，B=>0S
20、0，S→0A
21、1B，将A，B右端代入S的产生式得：S→0(1S
22、1)
23、1(0S
24、0)=01S
25、01
26、10S
27、10=(01
28、10)
29、(01
30、10)S∴S→(01
31、10)
32、(01
33、10)S∴S=(01
34、10)
35、(01
36、10)*∴该文法所对应的正规式为：(01
37、1
38、0)
39、(01
40、10)*9将图4.22的DFA最小化，并用正则式描述所识别的语言。【解释】初始划分得Π0：{6，7}，{1，2，3，4，5}{1，2}a={3，4}{1，2}b={2，4}{1，2}c，d=空{3，4}a=空{3，4}b={6，7}{3，4}c={3}{5}a={4}{5}b=空{5}d=空{6，7}b={6}{6，7}a，d，c=空最终划分为：1={1，2}，2={3，4}，3={5}，4={6，7}最小化DFA是：正则式为:b*a(c*
41、(da)*)bb*【本章其他作业参考答案】1.构造正规式1(0
42、1)*101相应的DFA.【答案】先构造NFA 确
43、定化01XAAAABABACABACAABYABYACAB重新命名，令AB为B、AC为C、ABY为D01XAAABBCBCADDCBDFA：3.将下图确定化： 【答案】01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQUZZZZ重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。01SABACBBDECFFDFECEFFFDFA：5..构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。【答案】按题意相应的正规表达式是0*(0
44、10)*0*或0*(100*)*0*构造相
45、应的DFA，首先构造NFA为用子集法确定化II0I1S01{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}12342244333DFA： 可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4为等价状态，可合并。【补充】为下边所描述的串写正规式，字母表是{a,b}.a)以ab结尾的所有串b)包含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个a的所有串e)包含a
