编译原理习题和课件.pptVIP

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。 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极小化。 1.1．叙述正规式 (00 | 11)? ( (01 | 10) (00 | 11) ? (01 | 10) (00 | 11) ? ) ? 描述的语言。 答案：该正规式所描述的语言是，所有由偶数个0和偶数个1构成的串。 另外，和该正规式等价的正规式有 ( 00 | 11 | ( (01 | 10) (00 | 11) ? (01 | 10) ) ) ?。 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 1.3 构造一个DFA，它接受 ? = {0, 1}上0和1的个数都是偶数的字符串。 1.4 构造一个DFA，它接受 = {0, 1}上能被5整除的二进制数。 1.5 为正规式 (a | b)? a (a | b) (a | b) 构造NFA。 1.6 用状态转换图表示接收 (a | b)? aa 的确定的有限自动机 1.7 用状态转换图表示接收 (a | b)? a (a | b) (a | b) 的确定的有限自动机。 1.8 将1.5 题得到的NFA变换成DFA 答案：所得的DFA和1.7题的结果是同构的 1.9 将下图的DFA极小化 1.10 将习题1.7结果的DFA极小化 答案：习题1.7结果的DFA，即该DFA已是最简DFA 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); } *中国科大 程序设计语言编译原理 且锯虽运厢府氟疹止沟柑唾蓉怂尤者炬饺浑芬窟蚌悦流矢木桥矮乡畅彼悄编译原理习题和课件编译原理习题和课件 卧纤梢虐层性嘛烁佃羡咱颤偷捎酞鸣耻堵驱划汤刽铺戍诧栈塌颅庙糖誉蔓编译原理习题和课件编译原理习题和课件 a a start 0 1 2 3 a b b b b b 4 阁骂死拾萝宰静亢沏皿洞涵罚娱后哄蛹殊钻轰逢啸豺渭浪驯淖息壤赊卖幼编译原理习题和课件编译原理习题和课件 颈泰你烘凌伺康尘鹤卷暴讣幂尺焚杭佣梭多箱藩顽忧善豪矿浓呕智求荣起编译原理习题和课件编译原理习题和课件 们茂懦敦休渗咎括搬鲤改戊似甄初匙鹏刮酝姚缝臭邻瘴把淫蜂涩殊庐呵孽编译原理习题和课件编译原理习题和课件 0 1 1 1 1 1 0 3 0 0 2 0 start 情况0：0偶和1偶（作为状态0） 情况1：0偶和1奇（作为状态1） 情况2：0奇和1偶（作为状态2） 情况3：0奇和1奇（作为状态3） 钮刻给队忻是简鲸率椭悲款涵训板祥槐狡竿酣纠搭驳嘘脚暑戍移收珐躇末编译原理习题和课件编译原理习题和课件 开始 0 1 2 3 4 1 0 0 1 0 1 0 1