《有限自动机(finite》由会员分享，可在线阅读，更多相关《有限自动机(finite（30页珍藏版）》请在金锄头文库上搜索。
1、有限自动机(Finite Automata),描述程序设计语言中的单词的识别过程。 主要内容： 确定有限自动机DFA(Deterninistic FA) 确定有限自动机DFA的实现 非确定有限自动机NFA(Nondeterninistic FA) NFA到DFA的转换 DFA的化简,确定有限自动机DFA,确定有限自动机DFA为一个五元组(,SS,S0,f,TS)，其中： 是一个有穷字母表，它的每个元素称为一个输入字符； SS是一个有穷集，它的每个元素称为一个状态； S0 SS是唯一的一个初始状态； f是在 SS SS上的转换函数 TSSS，是一个终止状态集，又称为接受状态集,DFA的两种表示方
2、式,状态转换图：结点表示状态，转换边表示转换函数，边的箭头方向指向转换函数中定义的转换方向。标识出初始状态和终止状态。状态转换表：可用二维数组描述。标识出初始状态和终止状态。Trans（ SI ，a） SJ,一个DFA的例子,DFA M=( a,b, S,U,V,Q, S, f, 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,状态转换表,DFA接受的字符串,对于*中的任何字符串t,若存在一条从初始结点到某一终止结
3、点的路径，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受（识别）。DFA M 所能接受的字符串的全体记为L(M).,DFA的确定性,初始状态唯一。 转换函数f:SSSS是一个单值函数，也就是说，对任何状态SSS,和输入符号a , f(S,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。 没有空边。即没有输入为（）,DFA的实现1,状态转换表的形式：（数组T存放转换函数）1.当前状态State置为初始状态2.读一个字符 CurrentChar3.如果CurrentCharEof并且T(State,CurrentChar)error则当前状态转为新的状态T(Sta
4、te,Current)，读下一字符。重复第3步工作。4.如果当前字符为Eof并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错特点：程序短小，但占用存储空间多,b,DFA的实现2,状态转换图的形式：每个状态对应一个带标号的case语句转向边对应goto语句特点：程序长，但占用存储空间少,i,j,k,a,Li: case CurrentChar ofa ：goto Ljb : goto Lkother : Error( ),非确定有限自动机NFA,定义1：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS).其中是字母表SS是状态集S0是初始状态集f是转换函数，
5、但不要求是单值的f: SS () 2SSTS是终止状态集,非确定有限自动机NFA,定义2：设A是一个NFA，A= (,SS,S0,f,TS) 则定义L(A)为从任意初始状态到任意终止状态所接受的字符串。L(A)=|s0s, s0 S0 sTS定义3：设A1和A2是同一个字母表上的自动机，如果有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
6、,其中S1Sk是A的全部初始状态。2.若S=S1,Sm是A的一个状态，a则定义f(S,a)=f(S1,a)f(S2,a)f(Sm,a)3.若S=S1,Sn是A的一个状态,且存在一个Si是A的终止状态，则令S为A的终止状态。,NFA到DFA的转换,合并 （Close(S)）1.对S状态寻找边，如果有令SsS2.对任意状态SiSs,如果有：f(Si,)= Sj则消除边：Ss= SsSj重复上述操作直至没有边3.对a f(Ss,a)= f(Sk,a)Ss=S1,Sm,k=1,m.4.如果Ss中包含初始状态则Ss也为初始状态，如果有终止状态，则Ss为终止状态。,NFA到DFA的转换,NFA到DFA的转
7、换过程:1. NFA初始状态集的合并集作为DFA的初始状态。 2. 对DFA中一状态S，对a,进行符号合并和合并得到的状态设为S,定义DFA的转换函数为f(S,a)=S. 3. 直至没有新状态产生为止。,例：将如下的NFA转化为DFA,DFA的化简（极小化）,状态等价对DFA中的两个状态S1和S2，如果将它们看作是初始状态，所接受的符号串相同，则定义S1和S2是等价的。方法状态合并法状态分离法,DFA的化简,状态合并法（状态吸收方法）寻找等价状态S1和S2 如果S2为初始状态，则S1和S2对调S2的出现修改为S1删除状态S2。 状态分离法 初始化为两个不等价状态集组：非终止状态组和终止状态组。
8、对每组中的某个状态分离出与之不等价的状态组，直至所有状态组内部状态都等价为止,正则表达式与有限自动机等价,定理：对任一确定有限自动机A，存在一正则表达式e,使得L(A)=L(e),反之亦然。 关系图：,DFA,正则表达式,NFA,正则表达式到FA的转换规则：,首先扩展转换图：,X,W,DFA到正则表达式的转换规则：,词法分析器的工作过程,词法分析器的设计,人工构造词法分析器过程：1.确定词法分析器的接口，即确定词法分析器是作为语法分析的一个子程序还是作为独立一遍。2.确定单词分类和Token结构。3.根据2步，构造每一类单词的描述正则表达式NFADFA。4.根据3步设计算法实现DFA。利用工具
9、自动生成：ScanGen Lex,词法分析器的生成器Lex,功能：依据语言的正则表达式，自动生成该语言的词法分析程序。 执行过程：,Lex中的元字符,abc ：字符a、b或c中的任一个。a? ： 一个可选的a。ab ：除了a、b外的任何一个字符。. ：除了新行之外的任一字符。. ：字符 “.”。xxx：名字为xxx的正则表达式。a-z ：a到z中的任一字符。为了与减号区别，减号表示为“-”。,Lex输入文件的格式,输入文件格式：declarations%rules% auxiliary procedures,%声明变量,常量% 正则定义,p action,例子,% LT, LE, IF, TH
10、EN, ELSE#include int count =0; % letter A-Za-z digit 0-9 id letter (letter| digit)* % if return (IF); id yylval = installid();return (ID); “” yylval = LT; return (RELOP); % installid() ,单元总结,两个工具：有限自动机、正则表达式 三个算法：正则表达式到FA的转换NFA到DFA的转换DFA的化简 一个实现：DFA的实现,作业：构造正则表达式 (a|b)*abb(a|b)*的最简DFA。要求先构造NFA，其次转换为DFA，最后加以极小化。书上 Pp58 第8题 附加题：分别构造和的自动机,
