有限自动机幻灯片.ppt

《有限自动机幻灯片.ppt》由会员分享，可在线阅读，更多相关《有限自动机幻灯片.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、有限自动机第1页，共30页，编辑于2022年，星期六确定有限自动机确定有限自动机DFADFAl确定有限自动机确定有限自动机DFADFA为一个五元组为一个五元组(,SS,SSS,S0 0,f f,TS),TS)，其中：其中：l 是一个有穷字母表，它的每个元素称为一个是一个有穷字母表，它的每个元素称为一个输入字符；输入字符；lSSSS是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；lS S0 0 SSSS是唯一的一个初始状态；是唯一的一个初始状态；lf f是在是在 SS SS SSSS上的转换函数上的转换函数lTSTS SSSS，是一个终止状态集，又称为接受状态是一

2、个终止状态集，又称为接受状态集集第2页，共30页，编辑于2022年，星期六DFADFA的两种表示方式的两种表示方式l 状态转换图：状态转换图：结点表示状态，转换边表示转换函数，边结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转换方的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。向。标识出初始状态和终止状态。l 状态转换表：状态转换表：可用二维数组描述。标识出初始状态和终可用二维数组描述。标识出初始状态和终 止状态。止状态。Trans（S SI I，a）S SJ J第3页，共30页，编辑于2022年，星期六一个DFA的例子lDFA M=(a,b,S,U,

3、V,Q,S,f,Q),l其中其中 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第4页，共30页，编辑于2022年，星期六SUVQ Qabbabaa,b状态转换图状态转换图第5页，共30页，编辑于2022年，星期六 字符状态abSUVUQVVUQQQQ状态转换表状态转换表第6页，共30页，编辑于2022年，星期六DFADFA接受的字符串接受的字符串l对于对于*中的任何字符串中的任何字符串t,t,若存在一条从初始若存在一条从初始结点到某一终止结点的路径结点到某一终止结点的路径，且这

4、条路上所且这条路上所有弧的标记符连接成的字符串等于有弧的标记符连接成的字符串等于t,t,则称则称t t可可为为DFA MDFA M所所接受（识别）接受（识别）。lDFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M).L(M).第7页，共30页，编辑于2022年，星期六DFADFA的确定性的确定性l初始状态唯一。初始状态唯一。l转换函数转换函数f:SSf:SSSSSS是一个单值函数，也是一个单值函数，也就是说，对任何状态就是说，对任何状态S S SS,SS,和输入符号和输入符号a a ,f(S,a),f(S,a)唯一地确定了下一个状态。即转唯一地确定了下一个状态。

5、即转换函数至多确定一个状态。换函数至多确定一个状态。l没有空边。即没有输入为没有空边。即没有输入为（）第8页，共30页，编辑于2022年，星期六DFADFA的实现的实现1 1l状态转换表的形式：状态转换表的形式：（数组（数组T T存放转换函数）存放转换函数）1.1.当前状态当前状态StateState置为初始状态置为初始状态 2.2.读一个字符读一个字符 CurrentCharCurrentChar 3.3.如果如果CurrentCharCurrentChar EofEof并且并且 T(State,CurrentChar)T(State,CurrentChar)errorerror 则当前状态

6、转为新的状态则当前状态转为新的状态T(State,Current)T(State,Current)，读下一字符。重复第读下一字符。重复第3 3步工作。步工作。4.4.如果当前字符为如果当前字符为EofEof并且当前状态属于终止状态，则并且当前状态属于终止状态，则接受当前字符串，程序结束。否则报错接受当前字符串，程序结束。否则报错l 特点：特点：程序短小，但占用存储空间多程序短小，但占用存储空间多第9页，共30页，编辑于2022年，星期六bDFADFA的实现的实现2 2l状态转换图的形式：状态转换图的形式：l 每个状态对应一个带标号的每个状态对应一个带标号的casecase语句语句l 转向边对应

7、转向边对应gotogoto语句语句l特点：特点：程序长，但占用存储空间少程序长，但占用存储空间少 ijkaLi:case CurrentChar of a ：goto Lj b :goto Lk other :Error()第10页，共30页，编辑于2022年，星期六非确定有限自动机非确定有限自动机NFANFAl定义定义1 1：一个非确定有限自动机一个非确定有限自动机(NFA)ANFA)A是是一个五元组一个五元组A=(A=(,SS,S,SS,S0 0,f,TS).,f,TS).其中其中l 是字母表是字母表l SS SS是状态集是状态集l S S0 0是初始状态集是初始状态集l f f是转换函数

8、，但不要求是单值的是转换函数，但不要求是单值的l f:SS f:SS ()2 2SSSSl TS TS是终止状态集是终止状态集第11页，共30页，编辑于2022年，星期六非确定有限自动机非确定有限自动机NFANFAl定义定义2 2：设设A A是一个是一个NFANFA，A=(A=(,SS,S,SS,S0 0,f,TS),f,TS)l则定义则定义L(A)L(A)为从任意初始状态到任意终止状为从任意初始状态到任意终止状态所接受的字符串。态所接受的字符串。L(A)=L(A)=|s s0 0 s s,s,s0 0 S S0 0 s s TS l定义定义3 3：设设A A1 1和和A A2 2是同一个字母

9、表上的自动机，是同一个字母表上的自动机，如果有如果有L(AL(A1 1)=L(A)=L(A2 2),),则称则称A A1 1和和A A2 2等价。等价。第12页，共30页，编辑于2022年，星期六NFANFA到到DFADFA的转换的转换l定理定理 对于每一个非确定自动机对于每一个非确定自动机A,A,存在一个存在一个确定自动机确定自动机A A,使得使得L(A)=L(AL(A)=L(A).).l转换转换：符号合并符号合并 同一状态的不同输出边标有相同的字符。同一状态的不同输出边标有相同的字符。合并合并 含有含有 边边 第13页，共30页，编辑于2022年，星期六NFANFA到到DFADFA的转换的

10、转换l符号合并符号合并：A A：NFA,ANFA,A:DFA:DFA 1.1.令令A A的初始状态为的初始状态为S S0 0=S=S1 1,S,S2 2,S Sk k,其中其中S S1 1S Sk k是是A A的全部初始状态。的全部初始状态。2.2.若若S S=S=S1 1,S,Sm m 是是A A的一个状态，的一个状态，a a则定义则定义 f f(S(S,a)=f(S,a)=f(S1 1,a),a)f(Sf(S2 2,a),a)f(Sf(Sm m,a),a)3 3.若若S S=S=S1 1,S,Sn n 是是A A的一个状态的一个状态,且存且存 在一个在一个S Si i是是A A的终止状态，

11、则令的终止状态，则令S S为为A A 的终止状态。的终止状态。第14页，共30页，编辑于2022年，星期六NFANFA到到DFADFA的转换的转换l 合并合并 （Close(S)Close(S)）1.1.对对S S状态寻找状态寻找 边，如果有令边，如果有令SsSsSS 2.2.对任意状态对任意状态SiSi Ss,Ss,如果有：如果有：f(Si,f(Si,)=)=SjSj则则 消除消除 边：边：Ss=SSs=Ss s SjSj 重复上述操作直至没有重复上述操作直至没有 边边 3.3.对对a a f(f(SsSs,a)=,a)=f(f(SkSk,a a)Ss=S1,Ss=S1,Sm,k=1,Sm,

12、k=1,m.,m.4.4.如果如果SsSs中包含中包含初始状态则初始状态则SsSs也为初始状也为初始状 态，如果有终止状态，则态，如果有终止状态，则SsSs为终止状态。为终止状态。第15页，共30页，编辑于2022年，星期六NFANFA到到DFADFA的转换的转换NFANFA到到DFADFA的转换过程的转换过程:1.NFA1.NFA初始状态集的初始状态集的 合并集作为合并集作为DFADFA的初始状的初始状 态。态。2.2.对对DFADFA中一状态中一状态S S，对对a a,进行符号合并和进行符号合并和 合并得到的状态设为合并得到的状态设为S S,定义定义DFADFA的转换的转换函数为函数为f(

13、S,a)=Sf(S,a)=S.3.3.直至没有新状态产生为止。直至没有新状态产生为止。第16页，共30页，编辑于2022年，星期六例：将如下的例：将如下的NFA转化为转化为DFAbbbaa 012435678910第17页，共30页，编辑于2022年，星期六DFADFA的化简（极小化）的化简（极小化）l 状态等价状态等价 对对DFADFA中的两个状态中的两个状态S S1 1和和S S2 2，如果将它们看作是初始状态，所接受如果将它们看作是初始状态，所接受 的符号串相同，则定义的符号串相同，则定义S S1 1和和S S2 2是等价的。是等价的。l 方法方法 状态合并法状态合并法 状态分离法状态分

14、离法 第18页，共30页，编辑于2022年，星期六DFADFA的化简的化简l 状态合并法（状态吸收方法）状态合并法（状态吸收方法）寻找等价状态寻找等价状态S S1 1和和S S2 2 如果如果S S2 2为初始状态，则为初始状态，则S S1 1和和S S2 2对调对调 S S2 2的出现修改为的出现修改为S S1 1 删除状态删除状态S S2 2。l 状态分离法状态分离法 初始化为两个不等价状态集组：非终止状态初始化为两个不等价状态集组：非终止状态 组和终止状态组。组和终止状态组。对每组中的某个状态分离出与之不等价的状对每组中的某个状态分离出与之不等价的状 态组，直至所有状态组内部状态都等价为

15、止态组，直至所有状态组内部状态都等价为止第19页，共30页，编辑于2022年，星期六正则表达式与有限自动机等价正则表达式与有限自动机等价定理：定理：对任一确定有限自动机对任一确定有限自动机A A，存在一正存在一正 则表达式则表达式e,e,使得使得L(A)=L(e),L(A)=L(e),反之亦然。反之亦然。关系图：关系图：DFA正则表达式正则表达式NFA第20页，共30页，编辑于2022年，星期六正则表达式到正则表达式到FAFA的转换规则的转换规则：13a b12a|b13 b*123ab12ab123 b l首先扩展转换图：首先扩展转换图：X XW W 第21页，共30页，编辑于2022年，星

16、期六123ab12ab12313a b12a|b13a b*cabcDFADFA到正则表达式的转换规则到正则表达式的转换规则：第22页，共30页，编辑于2022年，星期六词法分析器的工作过程词法分析器的工作过程词法分析器（词法分析器（Scanner）输入流输入流词法描述（正则表达式）词法描述（正则表达式）NFADFATokenListerror第23页，共30页，编辑于2022年，星期六词法分析器的设计词法分析器的设计l人工构造词法分析器过程：人工构造词法分析器过程：1.1.确定词法分析器的接口，即确定词法分析确定词法分析器的接口，即确定词法分析 器是作为语法分析的一个子程序还是作为器是作为语

17、法分析的一个子程序还是作为 独立一遍。独立一遍。2.2.确定单词分类和确定单词分类和TokenToken结构。结构。3.3.根据根据2 2步，构造每一类单词的描述步，构造每一类单词的描述 正则表达式正则表达式NFANFADFADFA。4.4.根据根据3 3步设计算法实现步设计算法实现DFADFA。l 利用工具自动生成：利用工具自动生成：ScanGen LexScanGen Lex第24页，共30页，编辑于2022年，星期六词法分析器的生成器词法分析器的生成器LexLexl功能：功能：依据语言的正则表达式，自动生成该语言的依据语言的正则表达式，自动生成该语言的词法分析程序。词法分析程序。l执行过

18、程：执行过程：正则正则表表达达式式文件文件Lex.lLex.lLexLex词法词法分分 析析 器器lexyy.clexyy.cC编译器编译器a.out输入流输入流Token序列序列第25页，共30页，编辑于2022年，星期六LexLex中的元字符中的元字符l abc：字符字符a、b或或c中的任一个。中的任一个。l a?：一个可选的一个可选的a。l ab：除了除了a、b外的任何一个字符。外的任何一个字符。l.：除了新行之外的任一字符。除了新行之外的任一字符。l.：字符字符“.”。l xxx：名字为名字为xxx的正则表达式。的正则表达式。l a-z ：a到到z中的任一字符。中的任一字符。为了与减号

19、区别，减号表示为为了与减号区别，减号表示为“-”。第26页，共30页，编辑于2022年，星期六LexLex输入文件的格式输入文件的格式l输入文件格式：输入文件格式：declarations declarations%rules rules%auxiliary procedures auxiliary procedures%声明变量声明变量,常量常量%正则定义正则定义p action第27页，共30页，编辑于2022年，星期六例子例子例子例子%LT,LE,IF,THEN,ELSE LT,LE,IF,THEN,ELSE#include#include int count=0;int count=0

20、;%letter A-Za-zletter A-Za-zdigit 0-9digit 0-9id letter(letter|digit)*id letter(letter|digit)*%if return(IF);if return(IF);id yylval=installid();return(ID);id yylval=installid();return(ID);“”yylval=LT;return(RELOP);yylval=LT;return(RELOP);%installid()installid()第28页，共30页，编辑于2022年，星期六单元总结单元总结l两个工具：两个

21、工具：有限自动机、正则表达式有限自动机、正则表达式l三个算法：三个算法：正则表达式到正则表达式到FAFA的转换的转换 NFA NFA到到DFADFA的转换的转换 DFADFA的化简的化简l一个实现：一个实现：DFADFA的实现的实现 第29页，共30页，编辑于2022年，星期六作业：作业：l 构造正则表达式构造正则表达式 (a|b)*abb(a|b)*(a|b)*abb(a|b)*的最简的最简 DFA DFA。要求先构造。要求先构造NFANFA，其次转换为，其次转换为DFADFA，最，最 后加以极小化。后加以极小化。l 书上书上 Pp58 Pp58 第第8 8题题附加题：附加题：l 分别构造分别构造 和和 的自动机的自动机第30页，共30页，编辑于2022年，星期六