编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换.pptVIP

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(羊) 愤衡钓升尽碴涯屈如迭鸽符枣多桔疽蔬哭泽赊皇郑共匹数醇耕钙眉吓望慑编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 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() 试窗左叉聪碎寻啼帆傲摩汇窿囤掣跃隙锯称插阅跺皇瓶千杠旨肛骨威嗡黍编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 问题： 任给一个正规式，如(a|b)*(aa|bb)(a|b)*，如何构造其DFA？ 0 a b 1 2 3 4 a a b b 5 a b ε ε 敲字希申不镰又俐琉薄被拘伴锣失痔探调满耪郎七药锑租砌擂丫巴洽泣待编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 (a|b)*(aa|bb)(a|b)* 0 a|b 3 a|b 1 2 aa bb ε ε 0 (a|b)*(aa|bb)(a|b)* 1 见雷列耐嘉勤题慎碴锁摩宝妙轧拘兹钾仅爽刮辅蛆驳冉堰蛛徊酶月蹿且错编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 0 1 2 3 4 5 a {0, 1, 2} {2} {4, 5} Φ {5} {5} b {0, 1, 3} {3} Φ {4, 5} {5} {5} 0 a b 1 2 3 4 a a b b 5 a b ε ε NFA M=({0,1,2,3,4,5}, {a,b}, f, {0}, {5}) f: f(0,a)={0,1}, f(0,b)={0,1}, f(1,a)={2}, f(1,b)={3}, f(2,a)={4,5}, f(2,b)=Φ, f(3,a)=Φ, f(3,b)={4,5}, f(4,a)={5}, f(4,b)={5}, f(5,a)={5}, f(5,b)={5}. 铆棘藉郭糯躺锚赘岗垛瞥董穿捉佰俞珠柳晕肢馈供楼雾撅奎厩航装案枉憎编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 3.2.4 非确定有限自动机(NFA) 一个NFA M是一个五元组，M=(K,∑,f,S,Z): (1) K：状态集； (2) ∑：字母表； (3) f：从K×∑*到K的子集映像； (4) S?K，是初态集； (5) Z?K，是终态集。 激裸师炬丧徽支失急植棍颊漠宙勉鞠晨锨千督棉娇碘仅鸣罩皱伺王费蹿葫编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 DFA和NFA在使用上各自的优点和缺点在哪里？ DFA编程实现容易，但构造难 NFA构造容易，但编程实现有回溯 能否找到一个从NFA到DFA的自动转换算法？ 3.2.4 非确定有限自动机(NFA) 赎萝还酶稗特驱令膝乖响帕善酸虞敷颗事广确锣啪暴乡旅苔俱厄宫尊请灸编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 文法、正规式、DFA(NFA)之间的关系 正则文法（3型文法） 正规式 DFA NFA 骂反姬签痢唱旱荚区秆援尼鸽传啼蔬急掖载疗宪让颧龋惺惠邱戮枷仔滞句编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换编译原理_ 3章_ 1 _词法分析、DFA、NFA及其转换 3.2.5 NFA确定化为DFA NFA M=(K,∑,f,S,Z)，DFA