有限自动机(Finite.ppt

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 )=U f ( S, b )=V f ( V, b )=Q f ( U, a )=Q f ( Q, a )=Q f ( 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.读一个字符 CurrentChar 3.如果CurrentCharEof并且 T(State,CurrentChar)erro

4、r 则当前状态转为新的状态T(State,Current)， 读下一字符。重复第3步工作。 4.如果当前字符为Eof并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错 特点： 程序短小，但占用存储空间多,b,DFA的实现2,状态转换图的形式： 每个状态对应一个带标号的case语句 转向边对应goto语句 特点： 程序长，但占用存储空间少,i,j,k,a,Li: case CurrentChar of a ：goto Lj b : goto Lk other : Error( ),非确定有限自动机NFA,定义1：一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS

5、).其中 是字母表 SS是状态集 S0是初始状态集 f是转换函数，但不要求是单值的 f: SS () 2SS TS是终止状态集,非确定有限自动机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

6、的转换,符号合并：A：NFA, A:DFA 1.令A的初始状态为S0=S1,S2,Sk, 其中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状态寻找边，如果有令SsS 2.对任意状态SiSs,如果有：f(Si,)= Sj则 消除边：Ss= SsSj 重复上述操作直至没有边 3.对a f(Ss,a)= f(Sk,a) Ss=S1,Sm,k=1,m. 4.如果

7、Ss中包含初始状态则Ss也为初始状 态，如果有终止状态，则Ss为终止状态。,NFA到DFA的转换,NFA到DFA的转换过程: 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 如果

8、S2为初始状态，则S1和S2对调 S2的出现修改为S1 删除状态S2。 状态分离法 初始化为两个不等价状态集组：非终止状态 组和终止状态组。 对每组中的某个状态分离出与之不等价的状 态组，直至所有状态组内部状态都等价为止,正则表达式与有限自动机等价,定理：对任一确定有限自动机A，存在一正 则表达式e,使得L(A)=L(e),反之亦然。 关系图：,DFA,正则表达式,NFA,正则表达式到FA的转换规则：,首先扩展转换图：,X,W,DFA到正则表达式的转换规则：,词法分析器的工作过程,词法分析器的设计,人工构造词法分析器过程： 1.确定词法分析器的接口，即确定词法分析 器是作为语法分析的一个子程序

9、还是作为 独立一遍。 2.确定单词分类和Token结构。 3.根据2步，构造每一类单词的描述 正则表达式NFADFA。 4.根据3步设计算法实现DFA。 利用工具自动生成：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, THEN, 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() ,单元总结,