编译原理第3章第1节词法分析﹒DFA﹒NFA及其转换.ppt

Step4 寻找可合并状态 ε ε 0 1 2 0 5 0 1 6 1 3 4 7 ε ε 0 8 9 1 1 0 10 11 0 0 1 1 1 0 12 13 0 1 I I0 I1 {0,1,2} 1 ε ε 0 1 2 2 5 0 0 8 {5,8} {5,8} 2 1 6 9 1 {6,9} {6,9} ε 1 2 0 5 8 {1,2} {1,2} 5 3 4 7 ε ε 8 {3,4,7} {3,4,7} 0 6 3 4 7 ε ε 9 {3,4,7} ε 1 2 6 1 9 {1,2} {5,8} {6,9} 0 4 7 10 0 12 {10,12} {10,12} 1 4 7 11 13 1 {11,13} {11,13} 0 4 7 ε 12 {4,7} {4,7} ε 1 2 10 1 {1,2} ε 1 2 11 0 {1,2} ε 1 4 7 13 {4,7} {10,12} {11,13} Step5 合并状态 I I0 I1 {0,1,2} {5,8} {5,8} {6,9} {6,9} {1,2} {1,2} {3,4,7} {3,4,7} {3,4,7} {1,2} {5,8} {6,9} {10,12} {10,12} {11,13} {11,13} {4,7} {4,7} {1,2} {1,2} {4,7} {10,12} {11,13} {0,1,2} 0 {3,4,7} I I0 I1 0 0 {5,8} 1 {5,8} {5,8} 1 1 1 1 1 1 {6,9} 2 {6,9} {6,9} 2 2 2 2 2 2 {1,2} 3 {1,2} {1,2} {1,2} {1,2} 3 3 3 3 3 3 3 3 3 3 {3,4,7} 4 {3,4,7} 4 4 4 4 4 4 {10,12} 5 {10,12} {10,12} 5 5 5 5 5 5 {11,13} 6 {11,13} {11,13} 6 6 6 6 6 6 {4,7} 7 {4,7} {4,7} 7 7 7 7 7 7 例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。 I I0 I1 0 1 1 1 2 2 2 3 3 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 Step6 构造DFA 1 2 3 2 3 4 1 3 4 4 5 6 5 6 7 3 5 7 3 6 7 0 1 2 0 1 2 0 1 3 4 0 1 0 1 0 1 5 6 0 1 7 0 1 0 1 0 1 例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。 Step7 确定初态和终态：原终态为1 0 1 5 6 0 1 0 1 2 0 1 3 4 0 1 0 1 7 0 1 0 1 0 1 {0,1,2} {5,8} {6,9} {1,2} {3,4,7} {10,12} {11,13} {4,7} {0,1,2} 0 {5,8} 1 {6,9} 2 {1,2} 3 {3,4,7} 4 {10,12} 5 {11,13} 6 {4,7} 7 0 3 例：构造DFA，使其能接受所有由偶数个0和偶数个1所组成串。 0 人,狼,羊,白菜 1 人,狼,羊 2 人,狼,白菜 3 人,羊,白菜 4 人,羊 5 狼,白菜 6 狼 7 羊 8 白菜 9 Φ 用G(x)表示人带x从左岸到右岸，R(x)表示从人带x右岸回到左岸； G和R分别代表人自己去到右岸或回到左岸。 0 1 2 3 4 6 7 8 5 9 G(羊) G(狼) G(羊) G G(狼) G(白菜) G(羊) G(白菜) G G(羊) R R(羊) R(羊) R(白菜) R R(狼) R(白菜) R(狼) R(羊) R(羊) 0 人,狼,羊,白菜 1 人,狼,羊 2 人,狼,白菜 3 人,羊,白菜 4 人,羊 5 狼,白菜 6 狼 7 羊 8 白菜 9 Φ 0 1 2 3 4 6 7 8 5 9 G(羊) G(狼) G(羊) G G(狼) G(白菜) G(羊) G(白菜) G G(羊) R R(羊) R(羊) R(白菜) R R(狼) R(白菜) R(狼) R(羊) R(羊) 0?5?2?8?3?7?4?9步骤： G(羊)?5(狼,白菜) R?2(人,狼,白菜) G(狼)?8(白菜) R(羊)?3(人,羊,白菜) (5)G(狼)?7(羊) (6)R?4(人,羊) (7)G(羊)?9() 问题： 任给一个正规式，如(a|b)*(aa|bb)(a|b)*，如何构造其DFA？ 0 a b 1 2 3 4 a a b b 5 a b ε ε (a|b)*(aa|bb)(a|b)* 0 a|b 3 a|b 1 2 aa bb ε ε 0 (a|b)*(aa|bb)(