编译原理习题答案-向张幸儿老师索取课件.ppt

步骤3 构造DFA如下： DFA N?=(K?,{0,1}, M?, [S], F?) 其中：K?= {[S],[ MV],[MU],[ MUZ],[ MVZ]} M?:M?([S],0) =[VM] M?([S],1) =[MU] M?([MV],0) =[ MVZ] M?([MV],1) =[MU] M?([MU],0) =[ MV] M?([MU],1) =[MUZ] M?([MVZ],0)=[ MVZ] M?([MVZ],1) =[MUZ] M?([MUZ],0)=[ MVZ] M?([MUZ],1) =[MUZ] F?= {[MVZ], [ MUZ]} 废负享汰认芍寞邯甫贬谱锄崖啡窟重翻馏探悯馆霉粳坡笛债阀辟亢郎苫旺编译原理习题答案-向张幸儿老师索取课件编译原理习题答案-向张幸儿老师索取课件 注意： 1. DFA N?的状态名必须用方括号对[与]括住，且状态名中所包含的字母必须按字典顺序排列（数字也一样）。 2. 终止状态之名则必须包含原NFA中终止状态名，如，新终止状态名[MVZ]中包含了原终止状态名Z。 膜磕棠况骗柳筹卿项惑田楷愁檬鹰蝴佑途筒社丹僻泉闹蒜深最贯晒货赠把编译原理习题答案-向张幸儿老师索取课件编译原理习题答案-向张幸儿老师索取课件 7. 设有NFA A=({q0,q1,q2}, {a,b},M,{q0},{q1}), 其中M为: M(q0,a)={q1,q2} M(q0,b)={q0} M(q1,a)={q0,q1} M(q1,b)= ? M(q2,a)={q0,q2} M(q2,b)={q1} 试为其构造DFA, 它能接受bababab与abababb吗？ 解：首先写出状态转换矩阵如下。 a b [q0] [q1,q2] [q0] [q1,q2] [q0,q1,q2] [q1] [q0,q1,q2] [q0,q1,q2] [q0q1] [q1] [q0q1] [q0,q1] [q0,q1,q2] [q0] 彝痹郴鬃吩歪嚎宁荐尾朗注讥饰枣巡唉樊滁屡蹋墒翟量位驱佛成谩工上淌编译原理习题答案-向张幸儿老师索取课件编译原理习题答案-向张幸儿老师索取课件 所以 DFA A?=(K?,{a,b},M?,[q0],F’) 其中：K?={[q0],[q1], [q0q1], [q1q2], [q0q1q2]} M?: M?([q0],a) =[q1q2] M?([q0],b)=[q0] M?([q1q2],a) =[q0q1q2] M?([q1q2],b)=[q1] M?([q0q1q2],a)=[ q0q1q2] M?([q0q1q2],b)=[q0q1] M?([q1],a) =[q0q1] M?([q0q1],a) =[ q0q1q2] M?([q0q1],b)=[q0] F?={[q1],[q1q2],[q0q1],[q0q1q2]} 苏食德粤撩屡杏予壤哇恶氨骤骚蜕蔚疾椭佣菲痉彭裤生刺兰唯伙葡姑恬取编译原理习题答案-向张幸儿老师索取课件编译原理习题答案-向张幸儿老师索取课件 运行DFA A?： 输入字符串bababab M?([q0], bababab) =M?(M’([q0],b), ababab) =M?(M?([q0], a), babab)=M?(M?([q1q2],b), abab) =M?(M?([q1],a), bab)