资源描述：
《编译原理答案++陈意云+高等教育出版社》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《编译原理》习题参考答案(一)《编译原理》习题参考答案(一)Bugreport:zpli@mail.ustc.edu.cnOrfind:电一楼二楼全球计算实验室李兆鹏第二章2.3叙述由下列正规式描述的语言a)0(0
2、1)*0b)((ε
3、0)1*)*c)(0
4、1)*0(0
5、1)(0
6、1)d)0*10*10*10*e)(00
7、11)*((01
8、10)(00
9、11)*(01
10、10)(00
11、11)*)*Answer:a)以0开始和结尾，而且长度大于等于2的0、1串b)所有0,1串（含空串）c)倒数第三位是
12、0的0、1串d)仅含3个1的0、1串e)偶数个0和偶数个1的0、1串（含空串）2.4为下列语言写出正规定义：f)由偶数个0和偶数个1构成的所有0和1的串g)由偶数个0和奇数个1构成的所有0和1的串Answer:标准答案见《编译原理习题精选》P1-P21.1&1.2题2.7用算法2.4为下列正规式构造非确定的有限自动机，给出它们处理输入串ababbab的转换序列。c)（（ε
13、a）b*）*d)(a
14、b)*abb(a
15、b)*Answer:c)NFA：e2e3eeestart0e16e7b8e9e10ee
16、4a5eezpli@mail.ustc.edu.cn2004-3-7version1.1Page1of7《编译原理》习题参考答案(一)输入串ababbab的转换序列：01456789145678789145678910Or0145678914567891236789145678910d)NFA：ee2a312a13eeestart0e16e7a8b9b10e1116e17eee4b514b15ee输入串ababbab的转换序列：012361456789101112131611141516172.8
17、用算法2.2把习题2.7的NFA变换成DFA。给出它们处理输入串ababbab的状态转换序列。Answer://针对2.7(c)3个不同的状态集合：A={0,1,2,3,4,6,7,9,10}B={1,2,3,4,5,6,7,9,10}C={1,2,3,4,6,7,8,9,10}NFA的转换表:状态输入符号abABCBBCCBC子集构造法应用于2.7(c)得DFA:aBabastartAbCbzpli@mail.ustc.edu.cn2004-3-7version1.1Page2of7《编译原理》
18、习题参考答案(一)2.11我们可以从正规式的最简DFA同构来证明两个正规式等价。使用这种技术，证明下面正规式等价。(a)(a
19、b)*(b)(a*
20、b*)*(c)((ε
21、a)b*)*Answer:（c）NFA见2.7（c）用子集构造法化简得DFA见2.8。最简的DFA为：aStart0b同理可求出(a)(b)正规式对应的最简DFA亦是如此，故(a)(b)(c)等价。2.15修改算法2.4,使之尽可能少使用ε转换，并保持所产生的NFA只有一个接收状态。Answer:算法2.4改进(3)(a)N(s)N
22、(t)开始状态合并作为N(s
23、t)的开始状态N(s)N(t)接受状态合并作为N(s
24、t)的接受状态(3)(c)N(s)开始状态与接受状态合并成一个状态j。N(s)startijf注意：必须保留一个i和f，否则可能在算法递归产生NFA过程中会出问题zpli@mail.ustc.edu.cn2004-3-7version1.1Page3of7《编译原理》习题参考答案(一)第三章3.2考虑文法SaSbS
25、bSaS
26、ε（a）为句子abab构造两个不同的最左推导，以此说明该文法是二义的。（b）为abab构造
27、对应的最右推导。（c）为abab构造对应的分析树。（d）这个文法产生的语言是什么？Answer:(a)S⇒lmaSbSS⇒lmaSbS⇒lmabS⇒lmabSaSbS⇒lmabaSbS⇒lmabaSbS⇒lmababS⇒lmababS⇒lmabab---------○1⇒lmabab----------○2可知，对于句子abab存在两个不同的最左推导，所以该文法是二义的(b)S⇒rmaSbSS⇒rmaSbS⇒rmaSb⇒rmaSbaSbS⇒rmabSaSb⇒rmaSbaSb⇒rmabSab⇒rma
28、Sbab⇒rmabab----------○3⇒rmabab------------○4(c)○1○4对应的分析树：○2○3对应的分析树：εεεεεε(d)该文法产生a、b个数相等的ab串（含空串）zpli@mail.ustc.edu.cn2004-3-7version1.1Page4of7《编译原理》习题参考答案(一)3.4文法RR‘
29、’R
30、RR
31、R*
32、(R)
33、a
34、b产生字母表{a,b}上所有不含ε的正规式。注意，第一条竖线是正规式的符号“或”，而不是文法产生式右部各选择之间的分
