第3章词法分析与有限自动机

1、本章目标v 解释词法分析器的工作原理及设计实现v 介绍单词的描述工具：正规文法和正规式v 定义DFA和NFA的概念v 介绍“正规式NFADFA最小化DFA”的转换方法v 介绍有限自动机、正规文法和正规式的等价性v 介绍词法分析器的自动构造工具-LEX的原理与实现教学内容3.1 3.1 词法分析器的设计思想词法分析器的设计思想3.2 3.2 词法分析器的设计词法分析器的设计3.3 3.3 单词的描述工具单词的描述工具3.4 3.4 有限自动机有限自动机3.5 3.5 正规式、正规文法和有限自动机的等价性正规式、正规文法和有限自动机的等价性3.6 3.6 词法分析器的自动构造工具词法分析器的自动构

2、造工具LEXLEX3.7 3.7 本章小结本章小结3.1 词法分析器的设计思想词法分析器的任务和输出形式词法分析器的任务和输出形式 1将词法分析工作分离的考虑将词法分析工作分离的考虑 21、词法分析器的任务和输出形式（1）词法分析器的任务 自左至右逐个字符地对源程序进行扫描，按语言的构词规则识别出一个个单词，把作为字符串的源程序改造为单词符号串的中间程序。字符串流字符串流单词流单词流源语言程序源语言程序单词符号单词符号1、词法分析器的任务和输出形式（2）单词符号单词符号是程序设计语言的基本语法单位和最小语义单位。（3）单词符号的种类 ：标记常量、变量、函数等的名字，如fun、i ：具有固定意义

3、的标识符，如if、while、for ：各种类型的常数，如实型0.618，布尔型TRUE ：如+、-、*、/、=、 、 = 、= ：如，、；、（、），单词符号1、词法分析器的任务和输出形式（4）单词符号的输出形式 二元式： （ 单词种别， 单词符号的属性值） ，它是语，它是语法分析所需要的信息。一法分析所需要的信息。一个语言的单词符号如何划个语言的单词符号如何划分种类、分为几类、如何分种类、分为几类、如何编码都属于技术性问题，编码都属于技术性问题，主要取决于处理上的方便。主要取决于处理上的方便。，这样可最大限度，这样可最大限度地把各个单词区别开来。地把各个单词区别开来。用来区分该类单词中的哪一

4、用来区分该类单词中的哪一个单词，它是单词本身的机个单词，它是单词本身的机内编码。内编码。例如，对于某个标识符，例如，对于某个标识符，常将存放它的有关信息的符常将存放它的有关信息的符号表项的指针作为其属性值；号表项的指针作为其属性值；而对于某个常数，则是将存而对于某个常数，则是将存放它的常数表项的指针作为放它的常数表项的指针作为其属性值。其属性值。1、词法分析器的任务和输出形式（4）单词符号的输出形式常用单词种别编码方案 标识符：一种 关键字：全体视为一种或一字一种 常 数：按类型分种，如整数、实数、布尔型 运算符：一符一种 界 符：一符一种单词种别编码1、词法分析器的任务和输出形式（5）举例假

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）将词法分析器设计为语法分析器的子程序 在实现编译程序时，常将词法分析程序从语法分析中独立出来，将其设计

6、为语法分析器的子程序，每当语法分析器需要一个单词符号时就调用词法分析器，每一次调用，词法分析器就从输入串中识别出一个单词符号，并将该单词类别和单词值返回给语法分析器。 字符串形式的源程序字符词法分析器语法分析器符号表单词取下一单词2、将词法分析工作分离的考虑（2）好处简化设计： 由词法分析器处理注解和空白字符，可简化语法分析器的设计。此外，在设计新语言时，分离词法和语法规则可以进行更全面的语言设计。改进编译效率： 编译的大部分时间消耗在读源程序和分离一个个单词符号上，专用的经过精心设计的读源程序字符流和处理单词符号的词法分析器可以加快编译速度。增强编译系统的可移植性：不同语言的字母表的特殊性，

7、构词规则的差异和其它与设备有关的不规则性可以限制在词法分析器中进行处理。 返回3.2 词法分析器的设计输入缓冲区和预处理程序输入缓冲区和预处理程序 1扫描器的工作原理扫描器的工作原理 2状态转换图与单词的识别状态转换图与单词的识别 3状态转换图的代码实现状态转换图的代码实现 41、输入缓冲区和预处理程序 （1）预处理程序 建立输入缓冲区，将源程序分批读入输入缓冲区中 过滤掉源程序中的注释；剔除一些无用的空白符、跳格符、回车符、换行符等编辑性字符；进行宏替换；实现文件包含的嵌入和条件编译的嵌入等。 将预处理结果送扫描器的扫描缓冲区（2）预处理程序作为独立子程序 预处理可作为一个子程序完成上述三个

8、任务，并被词法分析器调用，每调用一次，它就处理出一串确定长度（如120个字符）的输入字符，并送进扫描缓冲区。 返回2、扫描器的工作原理 （1）扫描器执行词法分析的程序称为，或称，或称。（2）扫描缓冲区一个可以互补使用的一分为二的扫描缓冲区。扫描缓冲区总长度为2N（如N=120）个字符，扫描器单词长度的要求是单词长度1/2扫描缓冲区长度。 2、扫描器的工作原理 （3）设置两个指示器 起点指示器：指向当前正在识别的单词的开始位置（指向新单词的首字符） 搜索指示器：用于向前搜索以寻找单词的终点（4）扫描器的工作 调用预处理子程序，把N(如120)个输入字符装进扫描缓冲区的某半区，搜索指针从起点指针开

9、始向前寻找单词的终点，若在该半区内查找到单词的终点，便输出二元式，再把起点指针移到此处的后一个字符，继续搜索下一个单词，如果在搜索到该半区的边缘，尚未到达单词终点，那么就调用预处理子程序，把后续的N个字符装进另半区，继续搜索。 返回3、状态转换图与单词的识别 （1）状态转换图 状态转换图是一种有限方向图，状态转换图可用于识别3型语言，它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。它由以下几个要素构成：结点：代表状态，用圆圈表示。箭弧：状态之间的连接，箭弧上的标记（字符）代表在射出结点状态下可能出现的输入字符或字符类。初态：识别出某一类字符串的开始，初态只有一个。终态：识别出某一单

10、词，至少有一个。用双圈表示。aaa3、状态转换图与单词的识别 （2）状态转换图识别的符号串 把从开始状态出发到某一终止状态所经过的路径上的标记依次连接起来的符号串，称为能被该状态转换图识别的符号串。 例如，右图能够识别符号串adb,addb,adddb,.,c（3）状态转换图识别的语言 状态转换图所能识别的全部符号串组成的集合构成了该状态转换图所识别的语言。 例如，右图所能识别的语言为：L(G)=c,adnb|n03、状态转换图与单词的识别 （4）标识符及无符号数的状态转换图012 2(a)字母字母或数字其它*012 2(b)数字数字其它*012 72356数字数字数字数字E或数字数字其它*数

11、字其它其它(c)E4 (a) 标识符；(b) 无符号整数；(c) 无符号数*为进行超前搜索，多读进了为进行超前搜索，多读进了一个符号，应回退搜索指示器。一个符号，应回退搜索指示器。3、状态转换图与单词的识别 （5）利用状态转换图识别单词的基本步骤从开始状态出发；读入一个字符；根据当前字符转入下一状态；重复和，直到到达某一终态。3、状态转换图与单词的识别 （6）举例下图为识别某个简单语言的所有单词符号的状态转换图。返回4、状态转换图的代码实现 （1）一组全局变量和函数要能有效实现词法分析器，需要定义如下的一组全局变量和函数：字符变量，存放最新读入的源程序字符：字符数组，存放构成单词符号的字符串：

12、函数，把下一个字符读入到ch中。：函数，跳过空白符，直至ch中读入一非空白符。：函数，把ch中的字符连接到 strToken ；：函数，判断ch中字符是否为字母；： 函数，判断ch中字符是否为数字；：函数，对于strToken中的字符串查找保留字表，若它是保留字则给出它的编码，否则返回0；：函数，把搜索指针回调一个字符位置，将ch置为空白字符；4、状态转换图的代码实现 （1）一组全局变量和函数：函数，将strToken中的标识符插入符号表，返回符号表指针；: 函数，将strToken中的常数插入常数表，返回常数表指针。 ：函数，把strToken中数字串译成标准二进制码，并作为函数值返回（十进

13、制转换为二进制）4、状态转换图的代码实现 （2）根据状态转换图编写代码的一般方法 一般将状态转换图看成一个流程图，从状态转换图的初态开始，对其每一个状态结点编写一段相应的程序，具体的做法是：每个状态结点对应于一个程序段；对不含回路的分叉结点来说，可让它对应一个switch 语句或一组if.else语句；如下图中的结点 i 对应的程序段为：state i：GetChar();if(IsLetter().转状态j对应的程序段.else if(IsDigit().转状态k对应的程序段.else if(ch=+).转状态L对应的程序段.else .错误处理.4、状态转换图的代码实现 （2）根据状态转换

14、图编写代码的一般方法对含有回路的状态结点来说，可让它对应一个由while语句和if语句构成的程序段；如下图中的结点 i 对应的程序段为：state i：GetChar();while(IsLetter()|IsDigit()GetChar();.转状态j对应的程序段.4、状态转换图的代码实现 （2）根据状态转换图编写代码的一般方法终态结点表示识别出某种单词符号，因此一般对应一个形如return(code,value)的语句，其中code为单词的种别编码，value为单词符号的属性值，或无定义； 如下图中的结点 i 对应的程序段为：凡带有星号（*）的终态结点意味着多读进一个不属于现行单词符号的字

15、符，该字符应予退回，即必须把搜索指示器回调一个字符位置。如下图中的结点 i 对应的程序段为：state i：return (code,value);state i：Retract();return (code,value);4、状态转换图的代码实现 （3）词法规则的相关约定为方便起见，对词法进行如下约定：除标识符、常数外，均为一符一种；关键字均作为保留字，不可用作用户标识符；设保留字表，识别出标识符时，查该表确定是否为关键字；相邻单词之间至少存在一个界符、运算符或空格。4、状态转换图的代码实现 （4）举例 编写由以下状态转换图所描述的某简单语言的词法分析程序。单词符号单词符号种别编码种别编码助

16、忆符助忆符内码值内码值DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END标识符6$ID内部字符串常数（数）7$INT标准二进制形式=8$ASSIGN-9$PLUS*10$STAR*11$POWER，12$COMMA(13$LPAR)14$RPAR单词符号及内码值4、状态转换图的代码实现 int code,value; strToken= ; GetChar( ); GetBC( ); if (IsLetter( ) while (IsLetter( ) or IsDigit( ) Concat ( ) ; GetChar( ); Retract( )； 4、状态转换图

17、的代码实现 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, );el

18、se 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）实验目的和要求理解词法分析器的任务和输出形式；理解扫描器的工作原理；掌握状态转换图的绘制以及单词的识别技术；掌握词法分析器的设计过程，能够使用某种高

19、级语言实现一个词法分析器。（2）实验内容给出一个简单语言的词法规则描述如表3.2所示，其中：种别码是1开头的为关键词，2开头的为算符，3开头的为界符，4开头的为标识符，5开头的为常数；标识符为字母开头，以字母和数字组成的任意符号串；常数为整数，即以数字组成的符号串。实验一 词法分析器的设计 请完成以下任务：画出识别该语言词法规则的状态转换图；依据该状态转换图编制出词法分析程序，能够从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、界符五大类。并依次输出各个单词的内部编码（种别码）及单词符号自身值。实验一 词法分析器的设计 单词符号单词符号种别码种别码内码内码单

20、词符号单词符号种别码种别码内码内码单词符号单词符号种别码种别码内码内码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或

21、Aa，其中A，BVN ，aVT*，则称G为一个；若文法G的任一产生式的形式都为ABa或Aa，其中A，BVN ，aVT*，则称G为一个。右线性文法和左线性文法统称为。【例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*)也都是正规式，它们所表示的正规集分

22、别为(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

23、|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 均为正规式，则下列关系普遍成立：交换律 正规式正规式正规集正规集U|VV|UL(U|V)L(V|U)L(U|V)L(U)L(V)L(V|U)L(V)L(U)2、正规式与正规集 （4）

24、正规式和正规集的运算律 结合律 正规式正规式正规集正规集U | (V | W)(U | V) | WL(U|(V| W)L(U|V)| W)L(U|(V| W)L(U)L(V| W)L(U)L(V)L(W)L(U|V)| W)L(U|V)L(W)L(U)L(V)L(W)U(VW)(UV)WL(U(VW)L(UV)W)L(U(VW)L(U)L(VW)L(U)L(V)L(W)L(UV)W)L(UV)L(W)L(U)L(V)L(W)2、正规式与正规集 （4）正规式和正规集的运算律 分配律 正规式正规式正规集正规集U(V | W)(UV) | UWL(U(V| W)L(UV| UW)L(U(V| W)

25、L(U)L(V| W)L(U)L(V)L(U)L(W)L(UV| UW)L(UV)L(UW)L(U)L(V)L(U)L(W)(V | W)UVU | WUL(V| W)U)L(VU| WU)L(V| W)U)L(V| W)L(U)L(V)L(U)L(W)L(U)L(VU| WU)L(VU)L(WU)L(V)L(U)L(W)L(U)2、正规式与正规集 （4）正规式和正规集的运算律 对任何正规式和正规集有：【例3.7】 证明证明：利用正规式的分配律和结合律直接推导： UUU L( U)L(U )L(U) *(ab) aa(ba)*2102121210*)(.|)(|)(|)(.|)(|)(|.|)

26、( |)( |.)|)( |)( |)()(baabaabaabaabaabaaaaabaabaaabababaab作业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是一个非空有限集，它的每个元素称为一个状态。是一个有穷字母表，它的每个元素称为一个输入

27、符号，所以也称为输入符号字母表。是状态转换函数，是在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)=

28、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）可识别 对于*中的任何字，若存在

29、一条从初态结点到某一个终态结点的路径，这条路径即为。若这条通路上所有弧的标记符连接成的字等于，则称可为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是一个非空有限集，它的每个元素称为一个状态

30、。是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表。是状态转换函数，：S*2S，即是一个从S *到S的子集的映射（多值映射），其中，2S表示S的所有子集的全体。S0 S，是一个非空的初态集合。F S，可空，是一个终态集合，终态也称可接受状态或结束状态。 2、非确定有限自动机（NFA） （2）表示形式一个NFA也可以用状态转换矩阵和状态转换图来表示。状态转换矩阵的行表示状态，列表示输入字，矩阵元素表示(s，a)的值。下面，主要介绍状态转换图的表示方法。NFA的状态转换图表示 若一个NFA M含有m个状态和n个输入字符，那么它所对应的状态转换图就含有m个状态结点，每个结点可

31、以射出若干条箭弧与别的结点相连接，每条箭弧用*中的一个字（不一定要不同的字而且可以是空字）作为标记（称为输入字），整个状态转换图至少含有一个初态终点和若干个终态结点，某些结点既可以是初态结点也可以是终态结点。 2、非确定有限自动机（NFA） （3）可识别 对于*中的任何一个字，若存在一条从某一个初态结点到某一个终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于，则称可为NFA M所（或）。若M的某些结点既是初态结点又是终态结点，或者存在一条从某个初态结点到某个终态结点的的通路，则空字可为M所识别。 例如，下图所示的NFA M所能识别的是所有含有相继两个a或相继两个b的字。 返回3、将

32、 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的闭包_C

33、LOSURE(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)

34、=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、将 NF

35、A 转换为 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 （

36、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。解：构造NFA*(a | b) (aa | bb)(a | b)*(a | b)*(a | b)aa | bba

37、 | baabba | babbaabab3、将 NFA 转换为 DFA 构造状态转换表aabbbaabIIaIbX,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,

38、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)

39、，且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最小化的任务 确定有限自动机化简的任务是去掉多余状态，合并等价状态。多余状态是指从该自动机的开

40、始状态出发，任何输入串也不能达到的状态，即从初态结点开始永远到达不了的那些状态。（5）DFA最小化算法（）基本思想a)将DFA M中的状态集分割成一些互不相交的子集，使得任何不同的两个子集中的状态都是可区别的，而同一个子集中的任何两个状态都是等价的。b)从每个子集中任选一个状态作为代表，同时消去其它等价状态及其射出的弧。c)把那些原来到达其它等价状态的弧改为到达相应的代表状态。（5）DFA最小化算法（） 具体步骤a)初始分割：把状态集S划分为终态集和非终态集，记为 其中， 属于终态集， 属于非终态集。b)k次分割：假定经过k次划分后， 得到m个子集， 记为 ，并且属于不同子集中的状态都是可区别

41、的。检查 中的每个子 集 ，看其能否进一步分割。令 ，若存在一个输入字符a（a），使得 不全包含在现行分割 的某一子集 中，就将 一分为二。12000S ,S 10S20S12mkkkkS ,S ,S kjkS (j1,2,m)jk1tS(q ,q )jk( S)aIkjkS4、确定有限自动机的化简 ikS 假设当前子集 ，若状态q1和q2经a弧分别到达状态t1和t2，而t1和t2又分属于当前已划分出的两个不同子集 和 中，则此时应将 分为两半，使得一半含有q1，另一半含有q2。4、确定有限自动机的化简 jk12tS(q ,q ,q )hkSikSjkSj1jikkkSs|sS and (s,

42、a)S j2jj1kkkSSS（5）DFA最小化算法（） 具体步骤c)循环分割：重复上一步，直到子集个数不再增加为止（即每个子集已是不可再分的了）。所谓不能划分，是指该子集或者仅有一个状态，或者虽有多个状态但这些状态均不可区别（即等价）。d)选代表，删除等价状态：对于最后分划 中的每一个子集，选取该子集中的一个状态代表其它等价状态。例如，状态子集I=q1,q2,，qk，挑选q1作为子集I的代表，则凡导入到q2，qk的弧都改成导入到q1中，然后将q2，qk及其所射出的弧从原来的DFA中删除。e)决定初态和终态：设删除等价状态之后的DFA为M ，凡那些包含M的初态的状态子集所对应的代表状态均作为M

43、的初态；凡那些包含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。ab3,4,5,63,63,4,5,63,4,5,64,53,4,5,6a0,1,21,33,4,5,60,1,2

44、aa0,21,134、确定有限自动机的化简 考察0，2 所以，将0，2分割为0和2。 最后，得到的全部分割子集为0，1，2，3，4，5，6。每个子集均不需再分割，即每个子集内的状态互相等价，任意不同两个子集中的状态都是可区别的。b0,22,43,4,5,60,214、确定有限自动机的化简 选代表，删除多余状态 令状态3代表3，4，5，6，把原来导入4，5，6的弧全都导入3，并删除4，5，6，最后可得下图所示的最小化DFA。作业3.2习题三（P64）：56(1)(2)返回3.5 正规文法、正规式和有限自动机的等价特性正规文法与正规式的等价性正规文法与正规式的等价性 1正规文法与有限自动机的等价性

45、正规文法与有限自动机的等价性 2正规式与有限自动机的等价性正规式与有限自动机的等价性 3总结总结 41、正规文法与正规式的等价性 一个正规语言（正规集）既可以用正规文法定义，也可以用正规式定义。关于正规文法和正规式有以下等价性定理：（1）定理1、正规文法与正规式的等价性 （2）正规式到正规文法的转换可按如下方法将上的一个正规式 r 转换成正规文法G=（VT，VN，S，P）：首先令VT =，选择一个非终结符号S（SVN）作为G的开始符号，并生成初始产生式Sr。然后，对该产生式反复运用下述规则进行变换，直到所生成的每个产生式最多含有一个终结符为止。假设x和y都是正规式：规则1：形如Axy，变换为

46、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。*SaAA(a | d)SaAA(a | d)AA SaAAaAAdAA SaAAaA | dA |1、正规文法与正规式的等价性 （3）正规文法到正规式的转换可按如下方法将正规文法G=（VT，VN，S，P

47、）转换成上的一个正规式 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等价的正规式为：AaA | b*Aa bBbB

48、 | c*Bb c*Sda b | eb c*da b | eb c返回2、正规文法与有限自动机的等价性 （1）正规文法和有限自动机的等价定理对于正规文法G和有限自动机M，如果L(G)L(M)，则称G和M是的。关于正规文法和有限自动机的等价性，有以下结论：2、正规文法与有限自动机的等价性 （2）由正规文法构造有限自动机由右线性正规文法构造有限自动机设G=( VT, VN, S, P)为一个右线性正规文法，则存在一个有限自动机M =（S， ，S0 ，F )，使得L(M)=L(G)。M的构造方法如下：a)M的字母表与G的终结符集合相同，即=VT；b)让G中的每个非终结符对应M中的一个状态结点；c)

49、以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

50、,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,