第三章词法分析有穷自动机 (2).pptVIP

定义对状态集合I的几个有关运算：

1.状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。状态集合I的任何状态S都属于ε-closure(I)。2.状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。第61页，共100页，星期日，2025年，2月5日状态集合I的有关运算的例子I={1},?-closure(I)={1,2}；I={5},?-closure(I)={5,6,2}；move({1,2},a)={5,3,4}?-closure({5,3,4})={2,3,4,5,6,7,8}；12534687aa?????a第62页，共100页，星期日，2025年，2月5日构造NFAN的状态K的子集的算法：假定所构造的子集族为C，即C=(T1,T2,,...TI),其中T1,T2,,...TI为状态K的子集。1开始，令?-closure(K0)为C中唯一成员，并且它是未被标记的。第63页，共100页，星期日，2025年，2月5日2while（C中存在尚未被标记的子集T）do { 标记T； for每个输入字母ado { U:=?-closure(move(T,a))； ifU不在C中then 将U作为未标记的子集加在C中 } }第64页，共100页，星期日，2025年，2月5日NFA的确定化例子4f35621i????aaaabbbb第65页，共100页，星期日，2025年，2月5日4f35621i????aaaabbbb第66页，共100页，星期日，2025年，2月5日等价的DFAaCDBAEFSbaaaaabbbbbabF第67页，共100页，星期日，2025年，2月5日确定有穷自动机的化简

说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。?第68页，共100页，星期日，2025年，2月5日DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t可区别：不满足兼容性——同是终态或同是非终态传播性——从s出发读入某个a?a???和从 t出发读入某个a到达的状态等价。第69页，共100页，星期日，2025年，2月5日C和D同是终态,读入a到达C和F,C和F同是终态,C和F读入a都到达C,读入b都到达E.C和D等价aCDBAEFSbaaaaabbbbbabF第70页，共100页，星期日，2025年，2月5日一个DFA的例子：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q第29页，共100页，星期日，2025年，2月5日一个DFA可以表示成一个状态图(或称状态转换图)。假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧；??第30页，共100页，星期日，2025年，2月5日DFA的状态图表示bSUVQaaaba，b第31页，共100页，星期日，2025年，2月5日一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表的