杭电 编译原理期末试卷.pdf

练习练习 2 词法分析词法分析 1 利用子集构造法把以下 NFA 转换成 DFA Answer 1 x z x T0 x y x y z x y z T5 x x y z x y T4 x y y T3 x y x z x z T2 y x z z T1 10 x z x T0 x y x y z x y z T5 x x y z x y T4 x y y T3 x y x z x z T2 y x z z T1 10 2 03 1 1 0 0 2 1 5 4 0 1 0 1 0 0 1 DFA 2 利用子集构造法把以下 NFA 转换成 DFA Answer 1 q u z v z q u z T5 q u v q s T0 z z z T6 z v T4 z z v z T3 q u z v q u T2 q u v z v q T1 10 q u z v z q u z T5 q u v q s T0 z z z T6 z v T4 z z v z T3 q u z v q u T2 q u v z v q T1 10 2 0 2 0 1 0 3 6 5 4 0 1 0 1 1 0 1 1 0 1 0 DFA 3 生成以下正规式的 NFA 并转换成 DFA 最后最小化该 DFA 1 a b 2 a ba 3 1 0 1 1 0 1 Answer 1 a b 01 2 4 3 5 6 a b 7 a b NFA a a B C A a b b b DFA A a b 最小化DFA 2 a ba 1 a 最小化DFA 2 b a 3 1 0 1 1 0 1 11 0 1 0 1 NFA 2 3 4 6 7 8 9 2 3 4 5 7 8 10 2 3 4 6 7 8 9 11 F 1 2 3 4 8 0 A 2 3 4 6 7 8 9 11 2 3 4 5 7 8 2 3 4 5 7 8 10 E 2 3 4 6 7 8 9 2 3 4 5 7 8 10 2 3 4 6 7 8 9 D 2 3 4 6 7 8 9 2 3 4 5 7 8 2 3 4 5 7 8 C 2 3 4 6 7 8 9 2 3 4 5 7 8 1 2 3 4 8 B 10 2 3 4 6 7 8 9 2 3 4 5 7 8 10 2 3 4 6 7 8 9 11 F 1 2 3 4 8 0 A 2 3 4 6 7 8 9 11 2 3 4 5 7 8 2 3 4 5 7 8 10 E 2 3 4 6 7 8 9 2 3 4 5 7 8 10 2 3 4 6 7 8 9 D 2 3 4 6 7 8 9 2 3 4 5 7 8 2 3 4 5 7 8 C 2 3 4 6 7 8 9 2 3 4 5 7 8 1 2 3 4 8 B 10 A C F D 1 0 DFA E 1 1 1 0 B 0 1 0 1 0 最小化后DFA A F D 1 0 E 1 1 B 0 1 0 1 0 4 设计一个 DFA 它能接受以 0 开始 以 1 结尾的所有序列 Answer 1 正规式 正规式 0 0 1 1 2 NFA Z 1