词法分析与有限自动机.pptx

词法分析与有限自动机教学内容3.1 3.1 词法分析器的设计思想词法分析器的设计思想3.2 3.2 词法分析器的设计词法分析器的设计3.3 3.3 单词的描述工具单词的描述工具3.4 3.4 有限自动机有限自动机3.5 3.5 正规式、正规文法和有限自动机的等价性正规式、正规文法和有限自动机的等价性3.6 3.6 词法分析器的自动构造工具词法分析器的自动构造工具LEXLEX3.7 3.7 本章小结本章小结3、1 词法分析器得设计思想词法分析器的任务和输出形式词法分析器的任务和输出形式 1将词法分析工作分离的考虑将词法分析工作分离的考虑 21、词法分析器得任务与输出形式(1)词法分析器得任务 自左至右逐个字符地对源程序进行扫描,按语言得构词规则识别出一个个单词,把作为字符串得源程序改造为单词符号串得中间程序。字符串流字符串流单词流单词流源语言程序源语言程序单词符号单词符号1、词法分析器得任务与输出形式(2)单词符号单词符号就是程序设计语言得基本语法单位与最小语义单位。(3)单词符号得种类 标识符标识符:标记常量、变量、函数等得名字,如fun、i 关键字关键字:具有固定意义得标识符,如if、while、for 常常 数数:各种类型得常数,如实型0、618,布尔型TRUE 运算符运算符:如+、-、*、/、=、=、=界界 符符:如,、;、(、),单词符号1、词法分析器得任务与输出形式(4)单词符号得输出形式 二元式:(单词种别,单词符号得属性值)表示单词得种类表示单词得种类,它就是语它就是语法分析所需要得信息。一法分析所需要得信息。一个语言得单词符号如何划个语言得单词符号如何划分种类、分为几类、如何分种类、分为几类、如何编码都属于技术性问题编码都属于技术性问题,主主要取决于处理上得方便。要取决于处理上得方便。通常让每种单词对应一个通常让每种单词对应一个整数码整数码,这样可最大限度地这样可最大限度地把各个单词区别开来。把各个单词区别开来。用来区分该类单词中得哪一用来区分该类单词中得哪一个单词个单词,它就是单词本身得它就是单词本身得机内编码。机内编码。单词符号得属性单词符号得属性就是指单词符号得特性或特就是指单词符号得特性或特征。属性值就是反应特性或征。属性值就是反应特性或特征得值。特征得值。例如例如,对于某个对于某个标识符标识符,常将存放它得有关常将存放它得有关信息得符号表项得指针作为信息得符号表项得指针作为其属性值其属性值;而对于某个常数而对于某个常数,则就是将存放它得常数表项则就是将存放它得常数表项得指针作为其属性值。得指针作为其属性值。1、词法分析器得任务与输出形式(4)单词符号得输出形式常用单词种别编码方案 标识符:一种 关键字:全体视为一种或一字一种 常 数:按类型分种,如整数、实数、布尔型 运算符:一符一种 界 符:一符一种单词种别编码1、词法分析器得任务与输出形式(5)举例假定单词类别用整数编码,标识符、常数、关键字、运算符与界符得编码依次为1、2、3、4、5。C+语句 if(a=90)b=c;在经过词法分析器处理后输出得二元式及其单词表示如下:二元式 单词(3,if)关键字if(5,()界符(1,指向a得符号表项得指针)标识符a(4,=)运算符=(2,90)常数90(5,)界符)(1,指向b得符号表项得指针)标识符b(4,=)运算符=(1,指向c得符号表项得指针)标识符c(5,;)界符;返回2、将词法分析工作分离得考虑(1)将词法分析器设计为语法分析器得子程序 在实现编译程序时,常将词法分析程序从语法分析中独立出来,将其设计为语法分析器得子程序,每当语法分析器需要一个单词符号时就调用词法分析器,每一次调用,词法分析器就从输入串中识别出一个单词符号,并将该单词类别与单词值返回给语法分析器。字符串形式的源程序字符词法分析器语法分析器符号表单词取下一单词2、将词法分析工作分离得考虑(2)好处简化设计:由词法分析器处理注解与空白字符,可简化语法分析器得设计。此外,在设计新语言时,分离词法与语法规则可以进行更全面得语言设计。改进编译效率:编译得大部分时间消耗在读源程序与分离一个个单词符号上,专用得经过精心设计得读源程序字符流与处理单词符号得词法分析器可以加快编译速度。增强编译系统得可移植性:不同语言得字母表得特殊性,构词规则得差异与其它与设备有关得不规则性可以限制在词法分析器中进行处理。返回3、2 词法分析器得设计输入缓冲区和预处理程序输入缓冲区和预处理程序 1扫描器的工作原理扫描器的工作原理 2状态转换图与单词的识别状态转换图与单词的识别 3状态转换图的代码实现状态转换图的代码实现 4大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点1、输入缓冲区与预处理程序(1)预处理程序建立输入缓冲区,将源程序分批读入输入缓冲区中过滤掉源程序中得注释;剔除一些无用得空白符、跳格符、回车符、换行符等编辑性字符;进行宏替换;实现文件包含得嵌入与条件编译得嵌入等。将预处理结果送扫描器得扫描缓冲区(2)预处理程序作为独立子程序 预处理可作为一个子程序完成上述三个任务,并被词法分析器调用,每调用一次,它就处理出一串确定长度(如120个字符)得输入字符,并送进扫描缓冲区。返回2、扫描器得工作原理(1)扫描器执行词法分析得程序称为词法词法分析程序分析程序,或称词法分析器词法分析器,或称扫描器扫描器。(2)扫描缓冲区一个可以互补使用得一分为二得扫描缓冲区。扫描缓冲区总长度为2N(如N=120)个字符,扫描器单词长度得要求就是单词长度1/2扫描缓冲区长度。2、扫描器得工作原理(3)设置两个指示器起点指示器:指向当前正在识别得单词得开始位置(指向新单词得首字符)搜索指示器:用于向前搜索以寻找单词得终点(4)扫描器得工作 调用预处理子程序,把N(如120)个输入字符装进扫描缓冲区得某半区,搜索指针从起点指针开始向前寻找单词得终点,若在该半区内查找到单词得终点,便输出二元式,再把起点指针移到此处得后一个字符,继续搜索下一个单词,如果在搜索到该半区得边缘,尚未到达单词终点,那么就调用预处理子程序,把后续得N个字符装进另半区,继续搜索。返回3、状态转换图与单词得识别(1)状态转换图 状态转换图就是一种有限方向图,状态转换图可用于识别3型语言,它就是设计与实现扫描器得一种有效工具,就是有限自动机得直观图示。它由以下几个要素构成:结点:代表状态,用圆圈表示。箭弧:状态之间得连接,箭弧上得标记(字符)代表在射出结点状态下可能出现得输入字符或字符类。初态:识别出某一类字符串得开始,初态只有一个。终态:识别出某一单词,至少有一个。用双圈表示。aaa3、状态转换图与单词得识别(2)状态转换图识别得符号串 把从开始状态出发到某一终止状态所经过得路径上得标记依次连接起来得符号串,称为能被该状态转换图识别得符号串。例如,右图能够识别符号串adb,addb,adddb,、,c(3)状态转换图识别得语言 状态转换图所能识别得全部符号串组成得集合构成了该状态转换图所识别得语言。例如,右图所能识别得语言为:L(G)=c,adnb|n03、状态转换图与单词得识别(4)标识符及无符号数得状态转换图 (a)标识符;(b)无符号整数;(c)无符号数*为进行超前搜索为进行超前搜索,多读进了一多读进了一个符号个符号,应回退搜索指示器。应回退搜索指示器。3、状态转换图与单词得识别(5)利用状态转换图识别单词得基本步骤从开始状态出发;读入一个字符;根据当前字符转入下一状态;重复与,直到到达某一终态。3、状态转换图与单词得识别(6)举例下图为识别某个简单语言得所有单词符号得状态转换图。返回4、状态转换图得代码实现(1)一组全局变量与函数要能有效实现词法分析器,需要定义如下得一组全局变量与函数:chch:字符变量,存放最新读入得源程序字符strTokenstrToken:字符数组,存放构成单词符号得字符串GetCharGetChar:函数,把下一个字符读入到ch中。GetBCGetBC:函数,跳过空白符,直至ch中读入一非空白符。ConcatConcat:函数,把ch中得字符连接到 strToken;IsLetterIsLetter:函数,判断ch中字符就是否为字母;IsDigitIsDigit:函数,判断ch中字符就是否为数字;ReserveReserve:函数,对于strToken中得字符串查找保留字表,若它就是保留字则给出它得编码,否则返回0;RetractRetract:函数,把搜索指针回调一个字符位置,将ch置为空白字符;4、状态转换图得代码实现(1)一组全局变量与函数InsertId InsertId:函数,将strToken中得标识符插入符号表,返回符号表指针;InsertConst InsertConst:函数,将strToken中得常数插入常数表,返回常数表指针。DTBDTB:函数,把strToken中数字串译成标准二进制码,并作为函数值返回(十进制转换为二进制)4、状态转换图得代码实现(2)根据状态转换图编写代码得一般方法 一般将状态转换图瞧成一个流程图,从状态转换图得初态开始,对其每一个状态结点编写一段相应得程序,具体得做法就是:每个状态结点对应于一个程序段;对不含回路得分叉结点来说,可让它对应一个switch 语句或一组if、else语句;如下图中得结点 i 对应得程序段为:state i:GetChar();if(IsLetter()、转状态j对应得程序段、else if(IsDigit()、转状态k对应得程序段、else if(ch=+)、转状态L对应得程序段、else、错误处理、4、状态转换图得代码实现(2)根据状态转换图编写代码得一般方法对含有回路得状态结点来说,可让它对应一个由while语句与if语句构成得程序段;如下图中得结点 i 对应得程序段为:state i:GetChar();while(IsLetter()|IsDigit()GetChar();、转状态j对应得程序段、4、状态转换图得代码实现(2)根据状态转换图编写代码得一般方法终态结点表示识别出某种单词符号,因此一般对应一个形如return(code,value)得语句,其中code为单词得种别编码,value为单词符号得属性值,或无定义;如下图中得结点 i 对应得程序段为:凡带有星号(*)得终态结点意味着多读进一个不属于现行单词符号得字符,该字符应予退回,即必须把搜索指示器回调一个字符位置。如下图中得结点 i 对应得程序段为:state i:return(code,value);state i:Retract();return(code,value);4、状态转换图得代码实现(3)词法规则得相关约定为方便起见,对词法进行如下约定:除标识符、常数外,均为一符一种;关键字均作为保留字,不可用作用户标识符;设保留字表,识别出标识符时,查该表确定就是否为关键字;相邻单词之间至少存在一个界符、运算符或空格。4、状态转换图得代码实现(4)举例 编写由以下状态转换图所描述得某简单语言得词法分析程序。单词符号单词符号种别编码种别编码助忆符助忆符内码值内码值DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END标识符6$ID内部字符串常数(数)7$INT标准二进制形式=8$ASSIGN-9$PLUS*10$STAR*11$POWER,12$MA(13$LPAR)14$RPAR单词符号及内码值4、状态转换图得代码实现 int code,value;strToken=;GetChar();GetBC();if(IsLetter()while(IsLetter()or IsDigit()Concat();GetChar();Retract();4、状态转换图得代码实现 code=Reserve();if(code=0)value=InsertId(strToken);return($ID,value);else return(code,);else if(IsDigit()while(IsDigit()Contact();Getchar();Retract();value=InsertConst(strToken);return($INT,value);4、状态转换图得代码实现 else if(ch=)return($ASSIGN,);else if(ch=+)return($PLUS,);else if(ch=*)GetChar();if(ch=*)return($POWER,);Retract();return($STAR,);else if(ch=;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else ProcError();/错误处理;实验一 词法分析器得设计(1)实验目得与要求理解词法分析器得任务与输出形式;理解扫描器得工作原理;掌握状态转换图得绘制以及单词得识别技术;掌握词法分析器得设计过程,能够使用某种高级语言实现一个词法分析器。(2)实验内容给出一个简单语言得词法规则描述如表3、2所示,其中:种别码就是1开头得为关键词,2开头得为算符,3开头得为界符,4开头得为标识符,5开头得为常数;标识符为字母开头,以字母与数字组成得任意符号串;常数为整数,即以数字组成得符号串。实验一 词法分析器得设计 请完成以下任务:画出识别该语言词法规则得状态转换图;依据该状态转换图编制出词法分析程序,能够从输入得源程序中,识别出各个具有独立意义得单词,即基本保留字、标识符、常数、运算符、界符五大类。并依次输出各个单词得内部编码(种别码)及单词符号自身值。实验一 词法分析器得设计 单词符号单词符号种别码种别码内码内码单词符号单词符号种别码种别码内码内码单词符号单词符号种别码种别码内码内码void101*203&216main102/204|217int103=205！218char104206(301if105=207)302else106208303for107=209304while108=210305return109211306cout110+212,307cin111-213;308+201214标识符400-202215常数500二进制形式返回3、3 单词得描述工具正规文法正规文法 1正规式与正规集正规式与正规集 21、正规文法 正规文法(线性文法)若文法G得任一产生式得形式都为AaB或Aa,其中A,BVN,aVT*,则称G为一个右线性文法右线性文法;若文法G得任一产生式得形式都为ABa或Aa,其中A,BVN,aVT*,则称G为一个左线性文法左线性文法。右线性文法与左线性文法统称为正规文正规文法或法或3 3型文法型文法。【例3、2】设有文法G1=(VT,VN,S,P),其中VT=0,1,VN=S,A,B,P为:S0A|1BA10A|1B01B|0则G1就是一个正规文法。返回2、正规式与正规集(1)正规式与正规集得递归定义与都就是上得正规式,它们所表示得正规集分别为与;任何,就是上得正规式,它所表示得正规集为;假定U与V都就是上得正规式,它们所表示得正规集分别为(U)与 (V),那么,(U|V)、(UV)与(U*)也都就是正规式,它们所表示得正规集分别为(U)(V)、(U)(V)与(U)*)。仅由有限次使用上述三步骤而得到得表达式才就是上得正规式,仅由这些正规式所表示得字集才就是上得正规集。(2)正规式得运算 正规式得运算符“|”、“”与“*”分别读作“或”、“连接”与“闭包”。运算符得优先级依次由低到高。连接符“”一般可以省略不写。2、正规式与正规集 【例3、6】令=a,b,则上得正规式与相应得正规集如下所示:正规式正规式正规集正规集aaa|ba,babab(a|b)(a|b)aa,ab,ba,bba*,a,aa,任意个任意个a得串得串(a|b)*,a,b,aa,ab,所有由所有由a与与b组成得串组成得串(a|b)*(aa|bb)(a|b)*上所有含有两个相继得上所有含有两个相继得a或两个相继得或两个相继得b组成得串组成得串2、正规式与正规集(3)正规式得等价若两个正规式所表示得正规集相同,则称这两个正规式等价等价。即 U、V为正规式,若L(U)=L(V),则称U、V等价,记为U=V。例如,1(01)*=(10)*1,b(ab)*=(ba)*b,(a|b)*=(a*|b*)*。(4)正规式与正规集得运算律若 U,V 与 W 均为正规式,则下列关系普遍成立:交换律 正规式正规式正规集正规集2、正规式与正规集(4)正规式与正规集得运算律结合律 正规式正规式正规集正规集2、正规式与正规集(4)正规式与正规集得运算律分配律 正规式正规式正规集正规集2、正规式与正规集(4)正规式与正规集得运算律对任何正规式与正规集有:【例3、7】证明证明:利用正规式得分配律与结合律直接推导:作业3、1习题三(P64):2(1)(2)3(1)(2)(3)返回3、4 有限自动机确定有限自动机（确定有限自动机（DFA）1非确定有限自动机（非确定有限自动机（NFA）2将将NFA转换为转换为DFA 3确定有限自动机的化简确定有限自动机的化简 41、确定有限自动机(DFA)(1)确定有限自动机(DFA)得定义一个确定得有限自动机(DFA)M就是一个五元组:M=(S,s0,F)S就是一个非空有限集,它得每个元素称为一个状态。就是一个有穷字母表,它得每个元素称为一个输入符号,所以也称为输入符号字母表。就是状态转换函数,就是在SS上得单值映射。定义形式:(s,a)=s,其中sS,sS,表示当现行状态为s,输入字符为a时,将转换到下一个状态s。称s为s得一个后续状态。s0S,就是唯一得一个初态。F S,可空,就是一个终态集,终态也称可接受状态或结束状态。1、确定有限自动机(DFA)(2)表示形式状态转换矩阵 一个DFA可用一个矩阵表示,行表示状态,列表示输入字符,矩阵元素表示(s,a)得值。这个矩阵称为状态转换矩阵状态转换矩阵。【例3、8】DFA M=(S,U,V,Q,a,b,S,Q),其中定义为:(S,a)=U,(S,b)=V,(U,a)=Q,(U,b)=V (V,a)=U,(V,b)=Q,(Q,a)=Q,(Q,b)=Q则该DFA对应得状态转换矩阵如下表所示。字符字符状态状态abSUVUQVVUQQQQ1、确定有限自动机(DFA)(2)表示形式状态转换图 一个DFA可以表示成一张(确定得)状态转换图状态转换图,假定DFA M含m个状态与n个输入字符,那么它所对应得状态转换图就含有m个状态结点,每个结点最多含有n条箭弧射出与别得结点相连接,每条箭弧用中得一个不同输入字符作标记。整张图含有唯一得一个初态结点与若干个(可以就是0个)终态结点。【例3、9】例3、8 中所定义得DFA M相应得状态转换图如下图所示:1、确定有限自动机(DFA)(3)可识别 对于*中得任何字,若存在一条从初态结点到某一个终态结点得路径,这条路径即为通路通路。若这条通路上所有弧得标记符连接成得字等于,则称可为DFA M所识别识别(或接受接受)。若M得初态结点同时也就是终态结点,则空字可为M所识别。DFA M=(S,s0,F)所能接受得字符串得全体为L(M)。(4)定理如果一个DFA M得输入字母表为,则称M就是上得一个DFA,可以证明:上得一个字集V *就是正规得,当且仅当存在上得DFA M,使得V=L(M)。返回2、非确定有限自动机(NFA)(1)非确定有限自动机(NFA)得定义一个非确定得有限自动机(NFA)M就是一个五元组:M=(S,S0,F)S就是一个非空有限集,它得每个元素称为一个状态。就是一个有穷字母表,它得每个元素称为一个输入符号,所以也称为输入符号字母表。就是状态转换函数,:S*2S,即就是一个从S *到S得子集得映射(多值映射),其中,2S表示S得所有子集得全体。S0 S,就是一个非空得初态集合。F S,可空,就是一个终态集合,终态也称可接受状态或结束状态。2、非确定有限自动机(NFA)(2)表示形式一个NFA也可以用状态转换矩阵与状态转换图来表示。状态转换矩阵得行表示状态,列表示输入字,矩阵元素表示(s,a)得值。下面,主要介绍状态转换图得表示方法。NFA得状态转换图表示 若一个NFA M含有m个状态与n个输入字符,那么它所对应得状态转换图就含有m个状态结点,每个结点可以射出若干条箭弧与别得结点相连接,每条箭弧用*中得一个字(不一定要不同得字而且可以就是空字)作为标记(称为输入字),整个状态转换图至少含有一个初态终点与若干个终态结点,某些结点既可以就是初态结点也可以就是终态结点。2、非确定有限自动机(NFA)(3)可识别 对于*中得任何一个字,若存在一条从某一个初态结点到某一个终态结点得通路,且这条通路上所有弧得标记字依序连接成得字等于,则称可为NFA M所识别识别(读出读出或接受接受)。若M得某些结点既就是初态结点又就是终态结点,或者存在一条从某个初态结点到某个终态结点得得通路,则空字可为M所识别。例如,下图所示得NFA M所能识别得就是所有含有相继两个a或相继两个b得字。返回3、将 NFA 转换为 DFA(1)NFA与DFA得等价性定理对每一个NFA N,一定存在一个DFA M,使得:L(M)=L(N),即对于每个NFA N存在着与之等价得DFA M,而且与某一NFA等价得DFA就是不唯一得。(2)子集算法 可以通过子集法得算法来将NFA转换成接受相同语言得DFA。子集法得基本思想就是:把DFA中得每一个状态对应NFA中得一组状态。即由于NFA中得就是多值得,所以在读入一个输入符号后可能达到得状态就是集合,而子集法就就是用DFA得状态记录该状态得集合。3、将 NFA 转换为 DFA(3)子集算法涉及得相关运算闭包_CLOSURE(I)假定I就是M得状态集得子集,定义I得闭包_CLOSURE(I)为:a)若qI,则q_CLOSURE(I);b)若qI,那么从q出发经任意条弧而能到达得任何状态q都属于_CLOSURE(I);Ia 假定I就是M状态集得子集,a,定义Ia=_CLOSURE(J),其中,J就是那些可从I中某一状态结点出发经过一条a弧而到达得状态结点得全体。可以先通过I求J,J=y|y=(x,a),xI,再求_CLOSURE(J),即得Ia。3、将 NFA 转换为 DFA 例如,如下图所示得NFA中:若I=1,则_CLOSURE(I)=1,2;若I=5,则_CLOSURE(I)=5,6,2;若I=1,2,则J=5,4,3,Ia=_CLOSURE(J)=5,6,2,3,8,4,7。3、将 NFA 转换为 DFA(4)NFA确定化为DFA得方法假设NFA M=(S,S0,F),可按如下方法对其确定化:对M得状态转换图作如下改造:a)引进新得初态结点X与终态结点Y。X,Y S,从X到S0中任意状态结点连一条箭弧,从F中任意状态结点连一条箭弧到Y。3、将 NFA 转换为 DFA(4)NFA确定化为DFA得方法b)对M得状态转换图按下图所示得规则作重复替换,其中K就是新引入得状态。重复这种分裂过程直至状态转换图中得每条箭弧上得标记或为,或为中得单个字母。将完成以上操作后最终得到得NFA 记为M,显然有:L(M)=L(M)。3、将 NFA 转换为 DFA(4)NFA确定化为DFA得方法 构造状态转换表假设a1,ak,针对M 构造如下得状态转换表:a)该表有k+1列,置该表得首行首列为_CLOSURE(X),其中X为初始状态;b)一般而言,如果某一行得第一列得状态子集已经确定,例如记为I,那么,置该行得i+1列为Iai(i=1k);c)检查该行上得所有状态子集,瞧它们就是否已经在表得第一列中出现,将未曾出现者依次重新填入到后面空行得第一列;d)重复上述过程,直到出现在i+1列(i=1k)上得所有状态子集均已在第一列上出现;e)由于M得状态子集得个数就是有限得,所以上述过程必定在有限步内终止。3、将 NFA 转换为 DFA(4)NFA确定化为DFA得方法 根据状态转换表构造状态转换矩阵(DFA M)假设a1,ak,针对M 构造如下得状态转换表:a)将状态转换表中得每个状态子集视为新得状态,将其作为M得状态;b)M得初态就是状态转换表中首行首列得状态子集对应得那个状态;c)M得终态就是状态转换表中含有M终态得状态子集对应得那些状态。显然,有 L(M)=L(M)=L(M)。3、将 NFA 转换为 DFA【例3、12】构造识别正规式(a|b)*(aa|bb)(a|b)*得NFA,并将其确定化为DFA。解:构造NFA3、将 NFA 转换为 DFA 构造状态转换表IIaIbX,5,15,3,15,4,15,3,15,4,15,3,1,2,6,Y5,4,1,2,6,Y5,3,15,4,15,3,1,2,6,Y5,4,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,2,6,Y5,4,1,6,Y3、将 NFA 转换为 DFA 重命名,构造状态转换矩阵IIaIbX,5,15,3,15,4,15,3,15,3,1,2,6,Y5,4,15,4,15,3,15,4,1,2,6,Y5,3,1,2,6,Y5,3,1,2,6,Y5,4,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,4,1,2,6,Y5,4,1,6,Y5,3,1,6,Y5,4,1,2,6,Y5,3,1,6,Y5,3,1,2,6,Y5,4,1,6,YSab012132214335464564635其中,0为初态,3,4,5,6为终态3、将 NFA 转换为 DFA 绘制状态转换图Sab012132214335464564635返回4、确定有限自动机得化简(1)DFA得化简(最小化DFA)对于任意给定得DFA M,构造另一个DFA M,使得L(M)=L(M),且DFA M 得状态个数为最少。(2)状态等价与可区别 假定s与t就是M得两个不同状态,如果从状态s出发能读出某个字w而停于终态,从状态t出发也能读出同样得字w而停于终态,反之亦然,就称状态s与t就是等价等价得;如果 DFA M得两个状态s与t不等价,则称状态s与t就是可区可区别别得。可 区 别 等 价4、确定有限自动机得化简 终态与非终态就是可区别得。(3)状态等价得条件一致性条件一致性条件:状态 s 与 t 必须同时为终态或非终态。蔓延性条件蔓延性条件:对于所有输入符号,状态 s 与 t 必须转化到等价得状态里。等 价4、确定有限自动机得化简(4)DFA最小化得任务 确定有限自动机化简得任务就是去掉多余状态,合并等价状态。多余状态就是指从该自动机得开始状态出发,任何输入串也不能达到得状态,即从初态结点开始永远到达不了得那些状态。(5)DFA最小化算法(子集分割算法子集分割算法)基本思想a)将DFA M中得状态集分割成一些互不相交得子集,使得任何不同得两个子集中得状态都就是可区别得,而同一个子集中得任何两个状态都就是等价得。b)从每个子集中任选一个状态作为代表,同时消去其它等价状态及其射出得弧。c)把那些原来到达其它等价状态得弧改为到达相应得代表状态。(5)DFA最小化算法(子集分割算法子集分割算法)具体步骤a)初始分割:把状态集S划分为终态集与非终态集,记为 其中,属于终态集,属于非终态集。b)k次分割:假定经过k次划分后,得到m个子集,记为 ,并且属于不同子集中得状态都就是可区别得。检查 中得每个子 集 ,瞧其能否进一步分割。令 ,若存在一个输入字符a(a),使得 不全包含在现行分割 得某一子集 中,就将 一分为二。4、确定有限自动机得化简 分割办法分割办法:假设当前子集 ,若状态q1与q2经a弧分别到达状态t1与t2,而t1与t2又分属于当前已划分出得两个不同子集 与 中,则此时应将 分为两半,使得一半含有q1,另一半含有q2。4、确定有限自动机得化简 q q1 1与与与与q q2 2不等价不等价不等价不等价t t1 1和和和和t t2 2不等价不等价不等价不等价(5)DFA最小化算法(子集分割算法子集分割算法)具体步骤c)循环分割:重复上一步,直到子集个数不再增加为止(即每个子集已就是不可再分得了)。所谓不能划分,就是指该子集或者仅有一个状态,或者虽有多个状态但这些状态均不可区别(即等价)。d)选代表,删除等价状态:对于最后分划 中得每一个子集,选取该子集中得一个状态代表其它等价状态。例如,状态子集I=q1,q2,qk,挑选q1作为子集I得代表,则凡导入到q2,qk得弧都改成导入到q1中,然后将q2,qk及其所射出得弧从原来得DFA中删除。e)决定初态与终态:设删除等价状态之后得DFA为M,凡那些包含M得初态得状态子集所对应得代表状态均作为M得初态;凡那些包含M得终态得状态子集所对应得代表状态均作为M 得终态。则有L(M)=L(M)。4、确定有限自动机得化简 4、确定有限自动机得化简【例3、13】对下图所示得DFA M进行化简。解:初始分割将状态集S=0,1,2,3,4,5,6划分为终态集3,4,5,6与非终态集0,1,2。4、确定有限自动机得化简 考察3,4,5,6 所以,3,4,5,6不再分割。考察0,1,2由于 ,所以,应将0,1,2分割为0,2与1。至此,得到得全部分割子集为3,4,5,6,0,2与1。4、确定有限自动机得化简 考察0,2 所以,将0,2分割为0与2。最后,得到得全部分割子集为0,1,2,3,4,5,6。每个子集均不需再分割,即每个子集内得状态互相等价,任意不同两个子集中得状态都就是可区别得。4、确定有限自动机得化简 选代表,删除多余状态 令状态3代表3,4,5,6,把原来导入4,5,6得弧全都导入3,并删除4,5,6,最后可得下图所示得最小化DFA。作业3、2习题三(P64):56(1)(2)返回3、5 正规文法、正规式与有限自动机得等价特性正规文法与正规式的等价性正规文法与正规式的等价性 1正规文法与有限自动机的等价性正规文法与有限自动机的等价性 2正规式与有限自动机的等价性正规式与有限自动机的等价性 3总结总结 41、正规文法与正规式得等价性 一个正规语言(正规集)既可以用正规文法定义,也可以用正规式定义。关于正规文法与正规式有以下等价性定理:(1)定理对任何正规式对任何正规式r,r,都存在一个正规文法都存在一个正规文法G,G,使得使得L(G)=L(r)L(G)=L(r)。对任何正规文法对任何正规文法G,G,都存在一个正规式都存在一个正规式r,r,使得使得L(r)=L(G)L(r)=L(G)。1、正规文法与正规式得等价性 (2)正规式到正规文法得转换可按如下方法将上得一个正规式 r 转换成正规文法G=(VT,VN,S,P):首先令VT=,选择一个非终结符号S(SVN)作为G得开始符号,并生成初始产生式Sr。然后,对该产生式反复运用下述规则进行变换,直到所生成得每个产生式最多含有一个终结符为止。假设x与y都就是正规式:规则1:形如Axy,变换为 AxB,By,BVN;规则2:形如Ax*y,变换为AxA,Ay;规则3:形如Ax|y,变换为A x,A y。1、正规文法与正规式得等价性 【例3、15】将正规式 R=a(a|d)*转换成相应得正规文法。解:令转换成得文法为G=(VT,VN,S,P),其中VT=a,d,文法开始符号为S,首先形成Sa(a|d)*,然后做变换:最后,得到得正规文法G得产生式为:VN=S,A。1、正规文法与正规式得等价性 (3)正规文法到正规式得转换可按如下方法将正规文法G=(VT,VN,S,P)转换成上得一个正规式 r:首先令=VT,然后,对P中得产生式反复运用下述规则进行变换,直到只剩下一个开始符号定义得产生式,并且该产生式得右部不含非终结符:规则1:形如AxB,By,变换为Axy;规则2:形如AxA,Ay,变换为Ax*y;规则3:形如A x,A y,变换为 Ax|y。1、正规文法与正规式得等价性 【例3、16】有正规文法GS,其中得产生式为:S d A|eB,AaA|b,BbB|c,将该文法G转换成正规式。解:令=a,b,c,d,e,然后对文法GS中得产生式做如下变换:将A,B代入S产生式得右部,得那么,与正规文法GS等价得正规式为:返回2、正规文法与有限自动机得等价性 (1)正规文法与有限自动机得等价定理对于正规文法G与有限自动机M,如果L(G)L(M),则称G与M就是等等价价得。关于正规文法与有限自动机得等价性,有以下结论:对每一个右线性正规文法对每一个右线性正规文法GG或左线性正规文法或左线性正规文法G,G,都存在一都存在一个有限自动机个有限自动机(FA)M,(FA)M,使得使得L(M)L(M)L(G)L(G)。对每一个对每一个FA M,FA M,都存在一个右线性正规文法都存在一个右线性正规文法GGR R与左线性正与左线性正规文法规文法GGL L,使得使得L(M)L(M)L(GL(GR R)L(GL(GL L)。2、正规文法与有限自动机得等价性 (2)由正规文法构造有限自动机由右线性正规文法构造有限自动机设G=(VT,VN,S,P)为一个右线性正规文法,则存在一个有限自动机M=(S,S0,F),使得L(M)=L(G)。M得构造方法如下:a)M得字母表与G得终结符集合相同,即=VT;b)让G中得每个非终结符对应M中得一个状态结点;c)以G得开始符作为M得初态结点,即S0=S;d)引进一个新得终态结点f,即S=VN f;e)对G中形如AaB得产生式,则令(A,a)=B;f)对G中形如Aa得产生式,则令(A,a)=f。2、正规文法与有限自动机得等价性 【例3、17】设有右线性正规文法G=(0,1,A,B,C,D,A,P),其中P为:A0|0B|1D B0D|1C C0|0B|1D D0D|1D 构造与G等价得有限自动机M。解:根据右线性正规文法构造有限自动机得方法,构造M=(A,B,C,D,f,0,1,A,f),其中为:(A,0)=f,(A,0)=B,(A,1)=D,(B,0)=D,(B,1)=C(C,0)=f,(C,0)=B,(C,1)=D,(D,0)=D,(D,1)=D其状态转换图如下图所示:2、正规文法与有限自动机得等价性 (2)由正规文法构造有限自动机由左线性正规文法构造有限自动机设G=(VT,VN,S,P)为一个左线性正规文法,则存在一个有限自动机M=(S,S0,F),使得L(M)=L(G)。M得构造方法如下:a)M得字母表与G得终结符集合相同,即=VT;b)让G中得每个非终结符对应M中得一个状态结点;c)以G得开始符号作为M得终态结点,即SF;d)引进一个新得初态结点q0;e)对G中形如ABa得产生式,则令(B,a)=A;f)对G中形如Aa得产生式,则令(q0,a)=A。2、正规文法与有限自动机得等价性 (3)由有限自动机构造正规文法由有限自动机构造右线性正规文法对于NFA,先将其确定化。设有确定有限自动机DFA M=(S,s0,f),构造一个右线性正规文法G=(VT,VN,S,P),使得L(G)=L(M)。G得构造方法如下:方法一方法一 a)令VN=S,VT=,S=s0;b)对任何a,A,BS,若有:(A,a)=B,则有规则AaB P。c)对M中得终态f,则加一条规则fP。方法二方法二 a)令VN=S,VT=,S=s0;b)对任何a,A,BS,若有:(A,a)=B,则当B不属于F,令AaB当BF,令Aa|aBc)若s0 f,即s0=f,则加一条规则s0P。2、正规文法与有限自动机得等价性 【例3、18】语言L就是所有由偶数个0与偶数个1组成得句子得集合,能接受语言L得状态转换图如右图所示,给出其对应得正规文法。解:设右线性正规文法G=(VT,VN,S,P),其中VT=0,1,VN=S,A,B,C,S=S,P为:或返回3、正规式与有限自动机得等价性(