第5讲-词法分析-iv

《第5讲-词法分析-iv》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理和技术本讲纲要温故子集构造法DFA化简(a

2、b)*ab=>NFA19开始0abab6782345NFA=>DFA理论依据根据有限自动机理论，设L为一个有不确定的有限自动机接受的集合，则存在一个接受L的确定的有限自动机怎样进行NFA到DFA的转化子集构造法NFA=>DFA子集构造法DFA的一个状态是NFA的一个状态集合读了输入a1a2…an后，NFA能到达的所有状态：s1,s2,…,sk，则DFA到达状态{s1,s2,…,sk}2.3有限自动机19开始0abab6782345输入符号ab状态2.

3、3有限自动机19开始0abab6782345输入符号abA状态A={0,1,2,4,7}2.3有限自动机19开始0abab6782345输入符号abAB状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自动机19开始0abab6782345输入符号abABB状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自动机19开始0abab6782345输入符号abABCB状态A={0,1,2,4,7}B={1,2,3,4,6,7,

4、8}C={1,2,4,5,6,7}2.3有限自动机19开始0abab6782345输入符号abABCBC状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自动机19开始0abab6782345输入符号abABCBBC状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自动机19开始0abab6782345输入符号abABCBBDC状态A={0,1,2,4,7}B={1,2,3,4,

5、6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}2.3有限自动机19开始0abab6782345输入符号abABCBBDCD状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}2.3有限自动机19开始0abab6782345输入符号abABCBBDCBCD状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}2.3有限自动机1

6、9开始0abab6782345输入符号abABCBBDCBCDBC状态A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}2.3有限自动机BD开始aAabbabCba19开始0abab6782345输入符号abABCBBDCBCDBC状态本讲纲要温故子集构造法DFA化简2.3有限自动机2.3.4DFA的化简通过算法构造的NFA，而后经过子集构造法得来的DFA通常不是最简的如何判定一个DFA是不是最简，that’saquestion

7、DFA的化简判断依据：状态的可区分性状态的可区分性存在串w，使得从状态s开始，对w进行状态转换，最终停在某个接受状态；而对于从t开始对w进行状态转换后，却停在某个非接受状态2.3有限自动机可区别的状态A和B是可区别的状态A和C是不可区别的状态BD开始aAabbabCbaDFA的化简DFA化简的途径根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系2.3有限自动机BD开始aAabbaa,bCbaEb化简时，D

8、FA的状态转换函数必须是一个全函数死状态左图无须加死状态，右图加入死状态E。BD开始aAabbabCba2.3有限自动机方法1.{A,B,C},{D}move({A,B,C},a)={B}move({A,B,C},b)={C,D}2.{A,C},{B},{D}move({A,C},a)={B}move({A,C},b)={C}BD开始aAabbabCba2.3有限自动机方法1.{A,B,C},{D}move({A,B,C},a}={B}move({A,B,C},b}={C,D}2.{A,C},{B},{D}move({A,C},a}

9、={B}move({A,C},b}={C}BD开始aAabbabCba12开始a0abbab本讲纲要温故子集构造法DFA化简补充词法模式识别过程一个串被DFA匹配的过程(a

10、b)*ab转换过程m(0,abab)12开始a0abbab状