资源描述：
《编译原理习题和课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、程序设计语言编译原理2021/9/19中国科大1.1叙述正规式(00
2、11)((01
3、10)(00
4、11)(01
5、10)(00
6、11))描述的语言。1.2给出下面的正规表达式：（1）能被五整除的十进制整数（2）包含奇数个1或奇数个0的二进制数串（3）包含偶数个0和奇数个1的二进制数串1.3构造一个DFA，它接受={0,1}上0和1的个数都是偶数的字符串。1.4构造一个DFA，它接受={0,1}上能被5整除的二进制数。1.5为正规式(a
7、b)a(a
8、b)(a
9、b)构造NFA。2021/9/19中国科大1.6用状态转
10、换图表示接收(a
11、b)aa的确定的DFA.1.7用状态转换图表示接收(a
12、b)a(a
13、b)(a
14、b)的DFA.1.8将1.5题得到的NFA变换成DFA。1.9将下图的DFA极小化。1.10将习题1.7结果的DFA极小化。aastart0123abbbbb42021/9/19中国科大1.1．叙述正规式(00
15、11)((01
16、10)(00
17、11)(01
18、10)(00
19、11))描述的语言。答案：该正规式所描述的语言是，所有由偶数个0和偶数个1构成的串。另外，和该正规式等价的正规式有(00
20、11
21、((01
22、10)(00
23、1
24、1)(01
25、10)))。2021/9/19中国科大1.2给出下面的正规表达式（1）能被五整除的十进制整数(0
26、5)
27、(1
28、2
29、3
30、4
31、5
32、6
33、7
34、8
35、9)(0
36、1
37、2
38、3
39、4
40、5
41、6
42、7
43、8
44、9)*(0
45、5)（2）包含奇数个1或奇数个0的二进制数串0*1(0
46、10*1)*
47、1*0(1
48、01*0)*（3）包含偶数个0和奇数个1的二进制数串even_0_even_1(00
49、11)((01
50、10)(00
51、11)(01
52、10)(00
53、11))1even_0_even_1
54、0(00
55、11)(01
56、10)even_0_ev
57、en_12021/9/19中国科大1.3构造一个DFA，它接受={0,1}上0和1的个数都是偶数的字符串。011111030020start情况0：0偶和1偶（作为状态0）情况1：0偶和1奇（作为状态1）情况2：0奇和1偶（作为状态2）情况3：0奇和1奇（作为状态3）2021/9/19中国科大1.4构造一个DFA，它接受={0,1}上能被5整除的二进制数。开始0123410010101012021/9/19中国科大1.5为正规式(a
58、b)a(a
59、b)(a
60、b)构造NFA。1a2ab3ab0startab23451607ab
61、εεεεεεεa98abεεεεabεεεε2021/9/19中国科大1.6用状态转换图表示接收(a
62、b)aa的确定的有限自动机102startaababb2021/9/19中国科大1.7用状态转换图表示接收(a
63、b)a(a
64、b)(a
65、b)的确定的有限自动机。baba2013467aabaabbstart5abab2021/9/19中国科大1.8将1.5题得到的NFA变换成DFA答案：所得的DFA和1.7题的结果是同构的2021/9/19中国科大1.9将下图的DFA极小化aastart0123abbbbb4012bbbb4
66、aastart最简DFA2021/9/19中国科大1.10将习题1.7结果的DFA极小化答案：习题1.7结果的DFA，即该DFA已是最简DFA2021/9/19中国科大1.11一个C语言编译器编译下面的函数时，报告parseerrorbefore‘else’。这是因为else的前面少了一个分号。但是如果第一个注释/*thenpart*/误写成/*thenpart那么该编译器发现不了遗漏分号的错误。这是为什么？longgcd(p,q)longp,q;{if(p%q==0)/*thenpart*/returnqelse/*else
67、part*/returngcd(q,p%q);}2021/9/19中国科大
