《编译原理》期末复习资料 【题 1】 1.（a|b）*（aa|bb）（a|b）*画出状态转换图。 ① 1,2,3 ② 2,3,4 ③ 2,3,5 ④ 2,3,4,6,7,8 ⑤ 2,3,5,6,7,8 ⑥ 2,3,5,7,8 ⑦ 2,3,4,7,8 1 2 3 4 5 6 7 Ia 2 4 2 4 7 7 4 Ib 3 3 5 6 5 5 6 Ia 2,3,4 2,3,4,6,7,8 2,3,4 2,3,4,6,7,8 2,3,4,7,8 2,3,4,7,8 2,3,4,6,7,8 Ib 2,3,5 2,3,5 2,,3,5,6,7,8 2,3,5,7,8 2,3,5,6,7,8 2,3,5,6,7,8 2,3,5,7,8 新的状态转换图如下： （1）A={1,2,3}，B={4,5,6,7} Aa={2,4} × （2）A={1,3}，B={2}，C={4,5,6,7} Aa={2}?B，Ab={3,5} × （3）A={1}，B={2}，C={3},D={4,5,6,7}（单元素可以不用看，必有，古先看D） Da={4,7}?D，Db={5,6}?D，Aa={2}?B，Ab={3}?C，Ba={4}?D，Bb={3}?C，Ca={2}?B，Cb={5}?C，则有 A B C D a B D B D b C C D D 2.（a*|b*）b（ba）*的状态转换图。 ① 1,2,3,4 ② 2,4 ③ 3,4,5,6,8 ④ 5,6,8 ⑤ 3,4,5,6,7,8 ⑥ 7 ⑦ 6,8 1 2 3 4 5 6 7 新的状态转换图如下： Ia 2 2 --- --- 7 7 --- Ib 3 4 5 6 5 --- 6 Ia 2,4 2,4 --- --- 6,8 6,8 --- Ib 3,4,5,6,8 5,6,8 3,4,5,6,7,8 7 3,4,5,6,7,8 --- 7 化简：（用终结状态与非终结状态，然后输出状态一致分一类）。 （1）A={1,2,6}，B={3,4,5,7} Aa={2} × （2）A={1,2}，B={6}，C={3,4,7}，D={5} Cb={5,6} ×（只要有一个不属于任何一个集合，就不行） （3）A={1,2}，B={6}，C={3}，D={4,7}，E={5} Ab={3,4} × （4） A={1}，B={2}，C={6}，D={3}，E={4,7}，F={5} Aa={2}?B，Ab={3}?D，Ba={2}?B，Bb={4}?E，Ca={7}?E，Db={5}?F，Eb={6}?C，Fa={7}?E，Fb={5}?F A B C D E F [注意事项]： a B B E --- --- E b D E --- F C F [知识要点]： ? 正则表达式：a,a|b,ab,(ab),(a|b),a(a|b),a|ab,a|ab ******a*???,a,aa,aaa,a?a?；a|b(a或b)??a,b?；ab(a和b)??ab?； ?ab?*???,ab,abab,ababab,???；