资源描述：
《编译原理第3章习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章习题解答1.构造正规式1(0
2、1)*101相应的DFA.[答案]先构造NFA确定化01XAAAABABACABACAABYABYACAB重新命名，令AB为B、AC为C、ABY为D01XAAABBCBCADDCB转化成DFA：==============================================================2.将下图确定化：[答案]01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQUZZZZ重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。0
3、1SABACBBDECFFDF ECEFFF转化为DFA：================================================================3.把下图最小化：[答案]（1）初始分划得Π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}，所以得新分划（2）Π1：{0}，{4}，{1,2,3,5}对{1,2,3,5}进行审查：∵{1,5}
4、b{4}{2,3}b{1,2,3,5}，故得新分划（3）Π2：{0}，{4}，{1,5}，{2,3}{1,5}a{1,5}{2,3}a{1,3}，故状态2和状态3不等价，得新分划（3）Π3：{0}，{2}，{3}，{4}，{1,5}这是最后分划了（4）最小DFA：=======================================4.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。[答案]按题意相应的正规表达式是0*(100*)*0*X
5、123456Y0εε10εε07εε0ε构造相应的DFA，首先构造NFA为用子集法确定化II0I1{X,1,2}S{1,2}A{3}B{4,5,6,2,7,Y}C{5,6,2,7,Y}D{1,2}A{1,2}A{4,5,6,2,7,Y}C{5,6,2,7,Y}D{5,6,2,7,Y}D{3}B{3}B/{3}B{3}BSABDC000111001DFA：可最小化，终态组为G1={C,D}，非终态组为G2={S,A,B}对于G2分析：f(S,0)=A,f(A,0)=A,后继状态均属于G2而f(B,0)=C,后继状态属于G
6、1将G2分割成G21={S，A}，G22={B}经检查DFA最小状态集有三个，可用S、B、D表示。或：按题意相应的正规表达式是0*(0
7、10)*0*首先构造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}1234224433 3DFA：可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4为等价状态，可合并。======
8、=======================================5．给出下列文法所对应的正规式：S->0A
9、1BA->1S
10、1B->0S
11、0[答案]解方程组S的解：S=0A
12、1BA=1S
13、1B=0S
14、0将A、B产生式的右部代入S中S=01S
15、01
16、10S
17、10=（01
18、10）S
19、（01
20、10）所以：S=(01
21、10)*(01
22、10)=================================================6.为下边所描述的串写正规式，字母表是{a,b}.a)以ab结尾的所有串b)包
23、含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串[答案]注意正规式不唯一a)(a
24、b)*abb)(bb)*c)(a*ba*ba*)*d)b*ab*e)(a
25、b)*ab(a
26、b)*f)b*a*======================================7.请描述下面正规式定义的串.字母表S={0，1}.a)0*(10+)*0*b)(0
27、1)*(00
28、11)(0
29、1)*c)1(0
30、1)*0[答案]a)每个1至少有一个0
31、跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和0结尾的串==========================================8.构造有穷自动机.a)构造一个DFA，接受字母表S={0,1}上的以01结尾的所有串b)构造一个DFA，接受字母表S={0,1}上的不包含01子串的所有串.c)构造一
