编译原理课后答案

函数 move 如上, S0 为开始状态,接收状态集合 F= {S5, S6, S7, S8} ,其状态转换图如下所示: (3) 根据算法 2.3 过将 DFA 最小化第一次划分: {S0, S1, S2, S3, S4} {S5, S6, S7, S8} {S0, S1, S2, S3, S4}a = {S1, S3, S1, S5, S7} 第二次划分: {S0, S1, S2} {S3, S4} {S5, S6, S7, S8} {S0, S1, S2}a = {S1, S3, S1} 第三次划分: {S0, S2} {S1} {S3, S4} {S5, S6, S7, S8} {S0, S2}a = {S1} {S0, S2}b = {S2} S0, S2 不可区分,即等价。{S5, S6, S7, S8}a = {S5, S7, S3, S1} 第四次划分: {S0, S2} {S1} {S3, S4} {S5, S6} {S7, S8} {S3, S4}a = {S5, S7} 第五次划分: {S0, S2} {S1} {S3} {S4} {S5, S6} {S7, S8} {S5, S6}a = {S5, S7} 第六次划分: {S0, S2} {S1} {S3} {S4} {S5} {S6} {S 7, S8} {S7, S8}a = {S3, S1} 第七次划分: {S0, S2} {S1} {S3} {S4} {S5} {S6} {S7} {S8} 集合不可再划分, 所以 S0, S2 等价,选取 S0 表示{S0, S2} ,其状态转换图,即题目所要求的最简 DFA 如下所示: 第三章 3.1 3.2 4 3.10 3.115 3.20 3.2367 第四章 4.1 题目有点不同方法一样 89 4.7 ( a) 4.10 ( a) 10 第六章 6.3