编译原理词法分析--有穷自动机-算法-DFA化简.pptVIP

YTU COMPILER 确定有穷自动机的化简 DFA的最小化 - 寻求等价的最少状态的DFA 没有多余状态 不可到达 不可终止 没有两个状态互相等价 定义: 两个状态s和t等价 假定s和t是M的两个不同状态,我们称s和t等价 如果从s出发能读出某个字w而停于终态， 则从t出发也能读出同样的字w而停于终态; 如果从t出发能读出某个字w而停于终态， 则从s出发也能读出同样的字w而停于终态。 0 2 3 a 1 a b a 4 a a 两个状态s和t等价的条件 ①一致性条件 终态和非终态不等价 ②蔓延性条件 对于所有输入符号，状态s和状态t必须转换到等价的状态里 0 2 3 a 1 a b a 4 a a 定义: 两个状态可区别－ 两个状态s和t不等价 终态和非终态可区别 例: 0和4是__________的 2和3是__________的 可区别 可区别 填空 : 等价 可区别 确定有穷自动机的化简方法 分割法: 把DFA的状态分成不相交的子集: 同一子集中的状态相互等价 不同子集中的状态相互区别 a b 1 6 3 2 7 3 3 1 5 4 4 6 5 7 3 6 4 1 7 4 2 {1,2},{3},{4}， {5}，{6,7} {1,2,3,4}, {5,6,7} 初始划分∏0 划分∏final 补充例 ? 对∏实施划分, 产生∏new 假定在某时刻, ∏含有m个子集, 记为∏={I1, I2,..., Im } , Ii中的两个状态s1和s2分在同一子组的充要条件是： s1和s2对所有的输入符号ai，都转换到∏的同一子集中 a b 1 6 3 2 7 3 3 1 5 4 4 6 5 7 3 6 4 1 7 4 2 {1, 2} {3} {4} {5} {6, 7} a b 1 6 3 3 1 5 4 4 6 5 6 3 6 4 1 为∏中的每一子集选取一个代表 a b 1 6 3 3 1 5 4 4 6 5 6 3 6 4 1 b 最小化结果 ? 分割法 (1) 构造初始划分∏, 终态集和非终态集 (2) 对∏实施划分, 产生∏new (3) 如果∏new=∏, 得到最后划分∏final=∏, 执行(4) , 否则 重复步骤(2). (4) 为∏中的每一子集选取一个代表 (5) 确定初态和终态 (6) 去掉死状态(多余状态) 例: DFA最小化 0 3 1 2 4 6 5 a b b a a b b a b a b a a b 最小化结果 0 2 3 a 1 a b b b a a,b * YTU COMPILER *