编译原理习题和课件.ppt

2020 2 1 中国科大 程序设计语言编译原理 2020 2 1 中国科大 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 2020 2 1 中国科大 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极小化 2020 2 1 中国科大 1 1 叙述正规式 00 11 01 10 00 11 01 10 00 11 描述的语言 答案 该正规式所描述的语言是 所有由偶数个0和偶数个1构成的串 另外 和该正规式等价的正规式有 00 11 01 10 00 11 01 10 2020 2 1 中国科大 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 1even 0 even 1 0 00 11 01 10 even 0 even 1 2020 2 1 中国科大 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 2020 2 1 中国科大 1 4构造一个DFA 它接受 0 1 上能被5整除的二进制数 2020 2 1 中国科大 1 5为正规式 a b a a b a b 构造NFA 2020 2 1 中国科大 1 6用状态转换图表示接收 a b aa的确定的有限自动机 2020 2 1 中国科大 1 7用状态转换图表示接收 a b a a b a b 的确定的有限自动机 a b a b 2020 2 1 中国科大 1 8将1 5题得到的NFA变换成DFA答案 所得的DFA和1 7题的结果是同构的 2020 2 1 中国科大 1 9将下图的DFA极小化 最简DFA 2020 2 1 中国科大 1 10将习题1 7结果的DFA极小化答案 习题1 7结果的DFA 即该DFA已是最简DFA 2020 2 1 中国科大 1 11一个C语言编译器编译下面的函数时 报告parseerrorbefore else 这是因为else的前面少了一个分号 但是如果第一个注释 thenpart 误写成 thenpart那么该编译器发现不了遗漏分号的错误 这是为什么 long