资源描述：
《编译原理课后问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、文档第二章2.3叙述由下列正规式描述的语言(a)0(0
2、1)*0(c)(0
3、1)*0(0
4、1)(0
5、1)在字母表{0,1}上,以0开头和结尾的长度至少是2的01串在字母表{0,1}上,倒数第三位是0的01串(b)((ε
6、0)1*)*(d)0*10*10*10*在字母表{0,1}上,所有的01串,包括空串在字母表{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*(***other1other*)****/(f)由偶数个0和偶数个1构成的所有0和1的串。［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：x偶数个0和偶数个1（用状态0表示）；x偶数个0和奇数个1（用状态1表示）；x奇数个0和偶数个1（用状态2表示）；x奇数个0和奇数个1（用状态3表示）；所以，x状态0（偶数个0和偶
17、数个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（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和
18、偶数个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、1S2→1S3
23、0S0
24、0S3→1S2
25、0S1在不考虑S0→ε产生式的情况下，可以将文法变形为：S0=1S1+0S2S1=1S0+0S3+1S2=1S3+0S0+0S3=1S2+0S1所以：S0=(00
26、11)S0+(01
27、10)S3+11+00(1)S3=(00
28、11)S3+(01
29、
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)+(01
41、10)(00
42、11)*(01
43、10))S0+(01
44、10)(00
45、11)*(01
46、10)+(00
47、11)=>S0=((00
48、11)
49、(01
50、10)(00
51、11)*(01
52、10))*((00
53、11)+(01
54、10)(00
55、11)*(01
56、10))=>S0=((00
57、11)
58、(01
59、10)(00
60、1
61、1)*(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的串。［解答］此题目我们可以借鉴上题的结论来进行处理。文档对于由偶数个0和奇数个1构成的所有0和1的串，我们分情况讨论：(1)若符号串首字符为0，则剩余字符串必然是奇数个0和奇数个1，因此我们必须在上题偶数个0和偶数个1的符号串基础上再读入10（红色轨迹）或01（蓝色轨迹），又因为在0→1和1→3的过程中可以进行多次循环（红色虚线轨迹），同理0→2和2
68、→3（蓝色虚线轨迹），所以还必须增加符号串(00
69、11)*，我们用S0表示偶数个0和偶数个1，用S表示偶数个0和奇数个1则其正规定义为：S→0(00
70、11)*(01
71、10)S0S0→((00
72、11)
73、(01
74、10)(00
75、11)*(01
76、10))*(2)若符号串首字符为1，则剩余字符串必然是偶数个0和偶数个1，其正规定义为：S→1S0S0→((00
77、11)
78、(01
79、10)(00
80、11)*(01
81、10))*综合(1)和(2)可得，偶数个0和奇数个1构成的所有0和1串其正规定义为：S→0(00
82、11)*(01
83、10)S0
84、1S0S0→((00
85、11)
86、(01
87、
88、10)(00
89、11)*(01
90、10))*2.7(c)((ε
91、a)b
