资源描述：
《编译原理课后答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章2.3叙述由下列正规式描述的语言17(a)0(0
2、1)*0在字母表{0, 1}上,以0开头和结尾的长度至少是2的01串(b)((ε
3、0)1*)*在字母表{0, 1}上,所有的01串,包括空串(c)(0
4、1)*0(0
5、1)(0
6、1)在字母表{0, 1}上,倒数第三位是0的01串(d)0*10*10*10*在字母表{0, 1}上,含有3个1的01串17(e)(00
7、11)*((01
8、10)(00
9、11)*(01
10、10)(00
11、11)*)*在字母表{0, 1}上,含有偶数个0和偶数个1的01串2
12、.4为下列语言写正规定义 C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。 ［解答］ other → a
13、 b
14、 … other指除了*以外C语言中的其它字符 other1 → a
15、 b
16、 … other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */ (f) 由偶数个0和偶数个1构成的所有0和1的串。 ［解答］ 由题目分析可知
17、，一个符号串由0和1组成，则0和1的个数只能有四种情况： x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）； 所以， x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1） x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0
18、） x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3） x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0） x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2） x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1） 因为，所求为由偶数个0和偶数个1构成的所有0和1
19、的串，故状态0既为初始状态又为终结状态，其状态转换图： 由此可以写出其正规文法为： S0 → 1S1
20、 0S2
21、 ε S1 → 1S0
22、 0S3
23、 1 S2 → 1S3
24、 0S0
25、 0 S3 → 1S2
26、 0S1在不考虑S0 → ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1 所以： S0 = (00
27、11) S0 + (01
28、1
29、0) S3 + 11 + 00 (1) S3 = (00
30、11) S3 + (01
31、10) S0 + 01 + 10 (2) 解(2)式得： S3 = (00
32、11)* ((01
33、10) S0 + (01
34、10)) 代入(1)式得： S0 = (00
35、11) S0 + (01
36、10) (00
37、11)*((01
38、10) S0 + (01
39、10)) + (00
40、11) => S0 = ((00
41、11) + (01
42、10) (0
43、0
44、11)*(01
45、10))S0 + (01
46、10) (00
47、11)*(01
48、10) + (00
49、11) => S0 = ((00
50、11)
51、(01
52、10) (00
53、11)*(01
54、10))*((00
55、11) + (01
56、10) (00
57、11)* (01
58、10)) => S0 = ((00
59、11)
60、(01
61、10) (00
62、11)* (01
63、10))+ 因为S0→ε所以由偶数个0和偶数个1构成的所有0和1的串的正规定义为： S0 → ((00
64、11)
65、(01
66、10) (00
67、11)
68、* (01
69、10))* (g) 由偶数个0和奇数个1构成的所有0和1的串。 ［解答］ 此题目我们可以借鉴上题的结论来进行处理。 17 对于由偶数个0和奇数个1构成的所有0和1的串，我们分情况讨论： (1) 若符号串首字符为0，则剩余字符串必然是奇数个0和奇数个1，因此我们必须在上题偶数个0和偶数个1的符号串基础上再读入10（红色轨迹）或01（蓝色轨迹），又因为在0→1和1→3的过程中可以进行多次循环（红色虚线轨迹），同理0→2和2→3（蓝色虚线轨迹），所以还必须增加符号串(00
70、11)*，我
