编译原理习题和.ppt

2023/10/8,中国科大,程序设计语言编译原理,2023/10/8,中国科大,1.1 叙述正规式(00|11)(01|10)(00|11)(01|10)(00|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|b)a(a|b)(a|b)构造NFA。,2023/10/8,中国科大,1.6 用状态转换图表示接收(a|b)aa的确定的DFA.1.7 用状态转换图表示接收(a|b)a(a|b)(a|b)的DFA.1.8 将1.5 题得到的NFA变换成DFA。1.9 将下图的DFA极小化。1.10 将习题1.7结果的DFA极小化。,2023/10/8,中国科大,1.1叙述正规式(00|11)(01|10)(00|11)(01|10)(00|11)描述的语言。答案：该正规式所描述的语言是，所有由偶数个0和偶数个1构成的串。另外，和该正规式等价的正规式有(00|11|(01|10)(00|11)(01|10)。,2023/10/8,中国科大,1.2 给出下面的正规表达式（1）能被五整除的十进制整数(0|5)|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)（2）包含奇数个1或奇数个0的二进制数串0*1(0|10*1)*|1*0(1|01*0)*（3）包含偶数个0和奇数个1的二进制数串even_0_even_1(00|11)(01|10)(00|11)(01|10)(00|11)1 even_0_even_1|0(00|11)(01|10)even_0_even_1,2023/10/8,中国科大,1.3 构造一个DFA，它接受=0,1上0和1的个数都是偶数的字符串。,0,start,情况0：0偶和1偶（作为状态0）情况1：0偶和1奇（作为状态1）情况2：0奇和1偶（作为状态2）情况3：0奇和1奇（作为状态3）,2023/10/8,中国科大,1.4 构造一个DFA，它接受=0,1上能被5整除的二进制数。,2023/10/8,中国科大,1.5 为正规式(a|b)a(a|b)(a|b)构造NFA。,2023/10/8,中国科大,1.6 用状态转换图表示接收(a|b)aa的确定的有限自动机,2023/10/8,中国科大,1.7 用状态转换图表示接收(a|b)a(a|b)(a|b)的确定的有限自动机。,2023/10/8,中国科大,1.8 将1.5 题得到的NFA变换成DFA答案：所得的DFA和1.7题的结果是同构的,2023/10/8,中国科大,1.9 将下图的DFA极小化,最简DFA,2023/10/8,中国科大,1.10 将习题1.7结果的DFA极小化答案：习题1.7结果的DFA，即该DFA已是最简DFA,2023/10/8,中国科大,1.11 一个C语言编译器编译下面的函数时，报告parse error before else。这是因为else的前面少了一个分号。但是如果第一个注释/*then part*/误写成/*then part 那么该编译器发现不了遗漏分号的错误。这是为什么？long gcd(p,q)long p,q;if(p%q=0)/*then part*/return q else/*else part*/return gcd(q,p%q);,