《有限自动机(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题 附加题:分别构造和的自动机,