第三章 3-有限自动机

有限自动机FA描述程序设计语言中的单词字，进一步为词法分析程序的自动构造寻找特殊的方法和工具。主要内容：确定有限自动机DFA确定有限自动机DFA的实现非确定有限自动机NFANFA到DFA的转换DFA的化简确定有限自动机DFA确定有限自动机（DFA：DeterministricFiniteAutomata)为一个五元组(,SS,S0,f,TS)，其中：是一个有穷字母表，它的每个元素称为一个输入字符；SS是一个有穷集，它的每个元素称为一个状态；S0SS是唯一的一个初始状态；f是在SSSS上的转换函数TSSS，是一个终止状态集，又称为接受状态集DFA的两种表示方式状态转换图：结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。状态转换表：可用二维数组描述。标识出初始状态和终止状态。Trans（SI，a）＝SJ一个DFA的例子DFAM=({a,b},{S,U,V,Q},S,f,{Q}),其中f定义为：f(S,a)=Uf(V,a)=Uf(S,b)=Vf(V,b)=Qf(U,a)=Qf(Q,a)=Qf(U,b)=Vf(Q,1)=QSUVQabbabaa,b状态转换图字符状态abSUVUQVVUQQQQ状态转换表DFA接受的字符串对于*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFAM所接受（识别）。DFAM所能接受的字符串的全体记为L(M).DFA的确定性初始状态唯一。转换函数f:SSSS是一个单值函数，也就是说，对任何状态SSS,和输入符号a,f(S,a)唯一地确定了下一个状态。即至多确定一个状态。没有空边。即没有输入为（）DFA的实现1状态转换表的形式：1.当前状态State置为初始状态2.读一个字符CurrentChar3.如果CurrentCharEof并且T(State,CurrentChar)error则当前状态转为新的状态T(State,Current)，读下一字符。重复第3步工作。4.如果当前字符为Eof并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错特点：程序短小，但占用存储空间多bDFA的实现2状态转换图的形式：每个状态对应一个带标号的case语句转向边对应goto语句特点：程序长，但占用存储空间少ijkaLi:caseCurrentCharofa：gotoLjb:gotoLkother:Error()非确定有限自动机NFA定义1：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS).其中是字母表SS是状态集S0是初始状态集f是转换函数，但不要求是单值的f:SS(∪{})2SSTS是终止状态集非确定有限自动机NFA定义2：设A是一个NFA，A=(,SS,S0,f,TS)则定义L(A)为从任意初始状态到任意终止状态所接受的字符串。L(A)={|s0s’,s0S0s’TS}定义3：设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2),则称A1和A2等价。NFA到DFA的转换定理1对于每一个非确定自动机A,存在一个确定自动机A’,使得L(A)=L(A’).转换：符号合并同一状态的不同输出边标有相同的字符。合并含有边NFA到DFA的转换符号合并：A：NFA,A’:FA1.令A’的初始状态为S0’=[S1,S2,…Sk],其中S1…Sk是A的全部初始状态。2.若S’=[S1,…,Sm]是A’的一个状态，a则定义f’(S’,a)=f(S1,a)f(S2,a)…f(Sm,a)3.重复步骤直至不出现新的状态为止。4.若S’=[S1,…,Sn]是A’的一个状态,且存在一个Si是A的终止状态，则令S为A’的终止状态。NFA到DFA的转换合并（Close(S)）1.对S状态寻找边，如果有令Ss＝{S}2.对任意状态SiSs,如果有：f(Si,)=Sj则消除边：Ss=SsSj重复上述操作直至没有边3.对af(Ss,a)=f(Sk,a)Ss={S1,…,Sm},k=1,…,m.4.如果Ss中包含初始状态则Ss也为初始状态，如果有终止状态，则Ss为终止状态。NFA到DFA的转换NFA到DFA的转换过程:1.NFA初始状态集的合并集作为DFA的初始状态。2.对DFA中一状态S，对a,进行符号合并和合并得到的状态设为S’,定义DFA的转换函数为f(S,a)=S’.3.直至没有新状态产生为止。将如下的NFA转化为DFAbbbaa012435678910DFA的化简（极小化）状态等价对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。方法状态合并法状态分离法DFA的化简状态合并法（状态吸收方法）寻找等价状态S1和S2如果S2为初始状态，则S1和S2对调S2的出现修改为S1删除状态S2。状态分离法初始化为两个不等价状态集组：非终止状态组和终止状态组。对每组中的某个状态分离出与之不等价的状态组，直至所有状态组内部状态都等价为止。正则表达式与有限自动机等价定理：对任一确定有限自动机A，存在一正则表达式e,使得L(A)=L(e),反之亦然。关系图：DFA正则表达式NFA正则表达式到NFA的转换规则：13ab12a|b13b*123ab12ab123b首先扩展转换图：XW123ab12ab12313ab12a|b13ab*cabcDFA到正则表达式的转换规则：词法分析器的工作过程词法分析器（Scanner）输入流词法描述（正则表达式）NFADFATokenListerror词法分析器的设计人工构造词法分析器过程：1.确定词法分析器的接口，即确定词法分析器是作为语法分析的一个子程序还是作为独立一遍。2.确定单词分类和Token结构。3.根据2步，构造每一类单词的描述正则表达式NFADFA。4.根据3步设计算法实现DFA。利用工具自动生成：ScanGenLex单元总结两个工具：有限自动机、正则表达式三个算法：正则表达式到FA的转换NFA到DFA的转换DFA的化简一个实现：DFA的实现