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