资源描述：
《有限自动机(Finite》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、有限自动机(FiniteAutomata)描述程序设计语言中的单词的识别过程。主要内容：确定有限自动机DFA(DeterninisticFA)确定有限自动机DFA的实现非确定有限自动机NFA(NondeterninisticFA)NFA到DFA的转换DFA的化简确定有限自动机DFA确定有限自动机DFA为一个五元组(,SS,S0,f,TS)，其中：是一个有穷字母表，它的每个元素称为一个输入字符；SS是一个有穷集，它的每个元素称为一个状态；S0SS是唯一的一个初始状态；f是在SSSS上的转换函数TSSS
2、，是一个终止状态集，又称为接受状态集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,b)=QSUVQabbabaa,b状态转换图字符状态
3、abSUVUQVVUQQQQ状态转换表DFA接受的字符串对于*中的任何字符串t,若存在一条从初始结点到某一终止结点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFAM所接受（识别）。DFAM所能接受的字符串的全体记为L(M).DFA的确定性初始状态唯一。转换函数f:SSSS是一个单值函数，也就是说，对任何状态SSS,和输入符号a,f(S,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。没有空边。即没有输入为（）DFA的实现1状态转换表的形式：（数组T存放转换函数）1.
4、当前状态State置为初始状态2.读一个字符CurrentChar3.如果CurrentCharEof并且T(State,CurrentChar)error则当前状态转为新的状态T(State,Current)，读下一字符。重复第3步工作。4.如果当前字符为Eof并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错特点：程序短小，但占用存储空间多bDFA的实现2状态转换图的形式：每个状态对应一个带标号的case语句转向边对应goto语句特点：程序长，但占用存储空间少ijkaLi:caseCurre
5、ntCharofa：gotoLjb:gotoLkother:Error()非确定有限自动机NFA定义1：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS).其中是字母表SS是状态集S0是初始状态集f是转换函数，但不要求是单值的f:SS(∪{})2SSTS是终止状态集非确定有限自动机NFA定义2：设A是一个NFA，A=(,SS,S0,f,TS)则定义L(A)为从任意初始状态到任意终止状态所接受的字符串。L(A)={
6、s0s’,s0S0s’TS}定义3：设A1和A2是同
7、一个字母表上的自动机，如果有L(A1)=L(A2),则称A1和A2等价。NFA到DFA的转换定理对于每一个非确定自动机A,存在一个确定自动机A’,使得L(A)=L(A’).转换：符号合并同一状态的不同输出边标有相同的字符。合并含有边NFA到DFA的转换符号合并：A：NFA,A’:DFA1.令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.若S’=[
8、S1,…,Sn]是A’的一个状态,且存在一个Si是A的终止状态，则令S’为A’的终止状态。NFA到DFA的转换合并（Close(S)）1.对S状态寻找边，如果有令Ss＝{S}2.对任意状态SiSs,如果有：f(Si,)=Sj则消除边：Ss=SsSj重复上述操作直至没有边3.对af(Ss,a)=f(Sk,a)Ss={S1,…,Sm},k=1,…,m.4.如果Ss中包含初始状态则Ss也为初始状态，如果有终止状态，则Ss为终止状态。NFA到DFA的转换NFA到DFA的转换过程:1.NFA初始状态集的
9、合并集作为DFA的初始状态。2.对DFA中一状态S，对a,进行符号合并和合并得到的状态设为S’,定义DFA的转换函数为f(S,a)=S’.3.直至没有新状态产生为止。例：将如下的NFA转化为DFAbbbaa012435678910DFA的化简（极小化）状态等价对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和
