编译原理第2章自动机理论

1、莆田学院网络中心许振和 1 本章本章将介绍正规文法和有穷自动将介绍正规文法和有穷自动 机之间的关系，所涉及的内容是编译机之间的关系，所涉及的内容是编译 中词法分析技术和自动生成词法分析中词法分析技术和自动生成词法分析 程序的理论。程序的理论。 第第2 2章章 自动机理论基础自动机理论基础 莆田学院网络中心许振和 2 教学要求教学要求 掌握：掌握：正规式，正规式，DFADFA的概念，的概念，NFANFA的概念的概念 理解理解：将：将DFA DFA 转换为转换为NFANFA，正规文法与有穷，正规文法与有穷 自动机间的转换自动机间的转换 重点：重点：正规式构造正规式构造DFADFA，DFADFA最小

2、化最小化 难点难点：正规表达式构造：正规表达式构造DFADFA 莆田学院网络中心许振和 3 一、正规式一、正规式 二、正规文法到正规式二、正规文法到正规式* 三、确定有穷自动机三、确定有穷自动机 四、不确定有穷自动机四、不确定有穷自动机 五、五、 NFA转换为等价的转换为等价的DFA 六、六、 DFA的化简的化简 七、正规式和有穷自动机的等价七、正规式和有穷自动机的等价 八、正规文法和有穷自动机的等价性八、正规文法和有穷自动机的等价性* 典型例题及解答典型例题及解答 教学大纲 教学大纲 莆田学院网络中心许振和 4 知识结构知识结构 词法分析词法分析自动构造工具自动构造工具 正规集正规集 正规式

3、正规式 有穷自动机（有穷自动机（NFA DFA)正规文法正规文法 莆田学院网络中心许振和 5 1、正规文法 文法G=(VN,VT,P,S)，P中每一规则有AaB或 Aa ，A,BVN，aVT*，称G(S)是正规文法。 多数程序设计语言的单词的语法能用正规文法来描述多数程序设计语言的单词的语法能用正规文法来描述 下面定义的标识符和无符号整数都是正规文法： letter | letter字母数字 letter | digit | letter字母数字 | digit字母数字 digit | digit无符号整数 一、正规式与正规集一、正规式与正规集 莆田学院网络中心许振和 6 2、正规式（正规表达

4、式） 是表示正规集的工具，也是用以描述单词符 号的方便工具。正规式也称正则表达式正规式也称正则表达式, ,是说明单是说明单 词的模式的一种重要的表示法（记号），是定义词的模式的一种重要的表示法（记号），是定义 正规集的数学工具。正规集的数学工具。 正规式中包括3种操作符：连接()，或(|)和闭包 (*)，其中或运算也常用“+”表示。 优先级：优先级：“闭包闭包”运算的优先级最高，运算的优先级最高，“连接连接” 运算次之，运算次之，“或或”运算最低。运算最低。 莆田学院网络中心许振和 7 正规式与正规集的正规式与正规集的递归递归定义：定义： 设字母表为，辅助字母表=，|， *，（，） ； 和都是

5、上的正规式，表示的正规集分 别为和； 任何a,a是上的一个正规式，表示的 正规集为a; 莆田学院网络中心许振和 8 假定e1和e2都是上的正规式，它们所表示的正 规集分别为L(e1)和L(e2),则(e1),e1|e2,e1e2和 e 1 * 也 都 是 正 规 式 ， 所 表 示 的 正 规 集 分 别 为 L(e1),L(e1)L(e2), L(e1)L(e2)和(L(e1)*。 仅由有限次使用上述三步骤而定义的表达式才是 上的正规式，仅由这些正规式所表示的子集才是 上的正规集。 例：例： a,ba,b， 上的正规式和相应的正规集为：上的正规式和相应的正规集为： 莆田学院网络中心许振和 9

6、 正规式正规集 aa a|ba,b abab (a|b)(a|b)aa，bb,ab,ba a*，a,aa, ，aaaa (a|b)* ，a,b,aa,ab,aab,abab, (a|b)*(aa|bb) (a|b)* *上所有含有两个相继的a 或两个相继的b组成的串 莆田学院网络中心许振和 10 正规式正规式: : (a(a b)b) 正规集正规集: : ,a,b,aa,ab ,a,b,aa,ab 所有由所有由a a和和b b组成的组成的 串串 正规式正规式: :(a(a b)b) (aa(aa bb)(abb)(a b)b) 正规集正规集: : 上所有含有两个相继的上所有含有两个相继的a a

7、或两个相继的或两个相继的 b b组成的串组成的串 1. 1. 正规式与相应的正规集是等价的，正规集给出了正规式与相应的正规集是等价的，正规集给出了 相应正规式所描述的全部单词（句子）；相应正规式所描述的全部单词（句子）； 2. 2. 正规式的运算结果是正规集；正规式的运算结果是正规集； 3. 3. 正规式不是集合，其运算结果正规集是集合。正规式不是集合，其运算结果正规集是集合。 莆田学院网络中心许振和 11 讨论下面两个例子讨论下面两个例子 例例1 1 令令 =l=l，dd，则，则 上的正规式上的正规式 r=l(lr=l(l d)d) 定义定义 的正规集为的正规集为: l,ll,ld,ldd,

8、: l,ll,ld,ldd,其中其中l l 代表字母代表字母,d,d代表数字代表数字, ,正规式正规式 即是即是 字母字母 ( (字母字母| |数字数字) ) , ,它表示的正规集中的每个它表示的正规集中的每个 元素的模式是元素的模式是“字母打头的字母数字串字母打头的字母数字串”,”, 就是就是PascalPascal和多数程序设计语言允许的标和多数程序设计语言允许的标 识符的词法规则识符的词法规则. . 莆田学院网络中心许振和 12 例例2 2：令：令 d d， ，e e，则，则 上的正上的正 规式为：规式为： d d* *(.dd(.dd* *| | )(e(+|-|)(e(+|-| )d

9、d)dd* *| | ) )表示的是无符号数。表示的是无符号数。 其中其中d d为为0 09 9中的数字。中的数字。 比如：比如：2,12.59,3.6e2,471.88e-12,12.59,3.6e2,471.88e-1等都是正规等都是正规 式表示集合中的元素。式表示集合中的元素。 莆田学院网络中心许振和 13 若两个正规式若两个正规式e e1 1和和e e2 2所表示的所表示的正规集相同，正规集相同， 则说则说e e1 1和和e e2 2等价等价, ,写作写作e e1 1=e=e2 2。 例如：例如： e e1 1= (a= (a b)b)， e e2 2 = b = b a a 又如：又

10、如： e e1 1= b(ab)= b(ab) , e , e2 2 =(ba) =(ba) b b e e1 1= (a= (a b)b) , e, e2 2 =(a=(a b b ) ) 正规式的等价正规式的等价 莆田学院网络中心许振和 14 设设e e1 1、e e2 2、e e3 3为正规式，有如下运算规则：为正规式，有如下运算规则： 莆田学院网络中心许振和 15 对于任意一个正规文法，存在一个同一语言的正 规式。对每一个正规式，存在一个正规文法。 即正规式正规文法 正规式正规式正规文法正规文法 文法G=（VN，VT，P，S）令VT=，对正规式r， 选择一个非终结符S生成Sr，S为G的

11、开始符号。 若x，y都是正规式，对形如Axy的产生式， 写成AxB，By。其中B VN 二、正规文法与正规式转换二、正规文法与正规式转换* * 莆田学院网络中心许振和 16 对形如Ax*y的产生式，重写为： AxB Ay BxB By B为新的非终结符，B VN 对形如Ax|y的产生式，重写为： Ax Ay 不断利用上述规则进行变换即可。 莆田学院网络中心许振和 17 例：将Ra(a|d)*变换成正规文法。令S是文法开 始符号。 解： S a(a|d)* SaA A(a|d)* A(a|d)B A B(a|d)B B 根据上述规则1 xa， y(a|d)* 根据上述规则2 x(a|d) y 莆

12、田学院网络中心许振和 18 最后得到： SaA AaB AdB A BaB BdB B 莆田学院网络中心许振和 19 正规文法正规文法正规式正规式 转换规则：转换规则： AxB，By 正规式为： A=xy AxA|y 正规式为： A=x*y Ax，Ay 正规式为： A=x|y 例：文法GS： S aA S a A aA A dA A a A d 转换为正规式 莆田学院网络中心许振和 20 S aA S a A aA A dA A a A d SaA|a AaA|dA Aa|d A(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d) 根据上述规则3 Ax，Ay 推出A

13、=x|y 将它化为正规文法 变成A (a|d)A|(a|d) 再根据上述 规则2转换 xy (a|d) 莆田学院网络中心许振和 21 Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a(a|d)+ 将A代入SaA|a得到如下： 莆田学院网络中心许振和 22 三、三、确定的有穷自动机确定的有穷自动机DFA 有穷自动机( (也称有限自动机也称有限自动机) )作为一种识作为一种识 别装置别装置，是词法分析程序的工具和方法，能自 动识别（且是正确识别正确识别）正规集。即识别正规即识别正规 文法所定义的语言和正规式所表示的集合，引文法所定义的语言和正规式所表示的集合，

14、引 入有穷自动机这个理论，正是为词法分析程序入有穷自动机这个理论，正是为词法分析程序 的自动构造寻找特殊的方法和工具。的自动构造寻找特殊的方法和工具。 分为 确定的有穷自动机（确定的有穷自动机（DFA） 不确定的有穷自动机（不确定的有穷自动机（NFA） 莆田学院网络中心许振和 23 一个确定的有穷自动机M是一个五元组： M=（K，f，S，Z），其中： K是一个有穷集，每个元素表示一个状态； 是一个有穷字母表，每个元素是一个输入字符； f是转换函数，是在KK上的映象上的映象，如： f(Ki ，a)= Kj (Ki, KjK)； S是初态，S K； ZK，是终态集。 含义：当前状态为 Ki，输入字

15、符a， 转换为Kj状态 DFADFA映射的唯一性和初态的唯一性映射的唯一性和初态的唯一性 莆田学院网络中心许振和 24 方法如下： 初始态用 “”或“”表示； 终态点用 “” 或“” 表示； 若f(Ki ，a)= Kj ，则从状态点Ki 到Kj画弧，标 记为a。 1 1、单词的构成规则用状态转换图表示、单词的构成规则用状态转换图表示 DFADFA等价表示法：等价表示法： DFADFA形式定义形式定义= =状态转换图状态转换图= =状态矩阵状态矩阵 莆田学院网络中心许振和 25 状态转换图(也称状态变迁图状态变迁图)是一张有限方向图。有 限个状态，用结点表示状态，其中有一个初态有一个初态(初态

16、用箭头指出)，至少有一个终态至少有一个终态(终态用双圈表示)。 状态之间用带箭头的弧线连结，弧线上标记的字符 表示在射出状态下可能出现的输入字符或字符类。 识别标识符的转换图 012 字母 字母或数字 其它 * 莆田学院网络中心许振和 26 一个状态图可用于识别一定的字符串，大多数程 序设计语言的单词符号都可以用转换图来识别。 识别过程是识别过程是：从初始状态0开始，若读入一个字 母，转入1状态，若再读入字母或数字，仍处 于1状态，否则转向2状态，结束一个标识符的 识别过程。状态上的*表示多读入一个符号。 012 字母 字母或数字 其它 * 莆田学院网络中心许振和 27 例：DFA的M(S,U

17、,V,Q,a,b,f,S,Q) 其中f为： f(S,a)=U, f(S,b)=V, f(U,a)=Q f(U,b)=V, f(V,a)=U, f(V,b)=Q f(Q,a)=Q, f(Q,b)=Q 状态图如下： a,b a a a b b b S U V Q a,b 莆田学院网络中心许振和 28 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA（DFA） 例2.21: 一个单部电梯对3层楼进行控制的电梯控制 系统的DFA描述。 问题分析： 用户请求 （输入） 上1、上2、上3 下1、下2、下3 状态设置 （所处楼层） 1层 2层 3层 S1 S2 S3 莆田学院网络中心许

18、振和 29 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA（DFA） S2 S3 S1 上2/下2 上3/下3 上1/下1 下1 下 2 上 3 上2 下1 上3 莆田学院网络中心许振和 30 2、用矩阵表示、用矩阵表示DFA : 方法： 行表示状态 列表示输入字符 元素表示相应状态行和输入字符下的新 状态。 “” 标明初态，默认第一行是初态。 终态行在表右端标1，非终态标0 莆田学院网络中心许振和 31 上例矩阵表示如下： ab SUV UQV VUQ QQQ 字符 状态 0 0 0 1 莆田学院网络中心许振和 32 例： b a S Z a,b 表示：f(S,a)=

19、Z f(S,b)=Z f(Z,a)=Z f(Z,b)=Z ab SZZ ZZZ 0 1 写成正规式是： (a+b)(a+b)* 莆田学院网络中心许振和 33 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA（DFA） 电梯控制的状态矩阵表示 上1下1上2 下2上3下3 S1* S1 S2* S3* S1 S1 S1 S2 S2 S2 S2 S3 S3 S3 S3 莆田学院网络中心许振和 34 3、DFA接接受（识别）的概念受（识别）的概念： 对于对于*中的任何字符串中的任何字符串t，若存在一条初态到若存在一条初态到 某一终态的路，且这条路上所有弧的标记符连接成某一终态的路

20、，且这条路上所有弧的标记符连接成 的字符串等于的字符串等于t，则称，则称t可为可为DFA M所接受。所接受。 若若M的初态同时又是终态，则空字可为的初态同时又是终态，则空字可为M所接所接 受。受。 莆田学院网络中心许振和 35 输入字符串输入字符串t（t表示成表示成Tt1形式，形式，T ，t1 *），在），在DFA M上运行的定义为：上运行的定义为：f（Q，Tt1） =f(f(Q,T),t1)，其中，其中Q K。 4、接受（识别）的理解：接受（识别）的理解： 设设Q K，函数，函数f(Q, )=Q，则输入字符串是，则输入字符串是 空串，并停留在原状态上。空串，并停留在原状态上。 莆田学院网络中

21、心许振和 36 例：证明例：证明t t= =baabbaab被下图的被下图的DFADFA所接受所接受。 f f（S S，baabbaab）=f=f（f f（S S，b b），），aabaab） = f= f（V V，aabaab）= f= f（f f（V V，a a），），abab） =f=f（U U，abab）=f=f（f f（U U，a a），），b b） =f=f（Q Q，b b）= =Q Q Q Q属于终态。属于终态。 得证。得证。 b S U V Q a b b a , b a a 莆田学院网络中心许振和 37 DFA的确定性表现在：的确定性表现在： 对任何状态s S，在读入了输入符

22、号a 之后，能够唯一地确定唯一地确定下一个状态 映射函数：SS是一个单值单值函数 从状态转换图来看，若字母表含有n个输入 字符，那末任何一个状态结点最多有最多有n条弧条弧 射出射出，而且每条弧以一个不同的输入不同的输入字符字符标 记。 莆田学院网络中心许振和 38 DFA M所能接受的字符串的全体记为L（M） 称为语言 （也即句子的集合） 结论：结论： 上一个符上一个符号号串集串集V V 是正规的，当且仅当是正规的，当且仅当 存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M M，使得，使得V=L(M)V=L(M) 文法是语言的生成系统，是从产生的观点来描 述语言的。 自动机是语言的识别

23、系统，是从识别的观点来 描述语言的 文法和自动机的对比文法和自动机的对比 莆田学院网络中心许振和 39 四、四、 不确定的有穷自动机不确定的有穷自动机NFA 一个不确定的有穷自动机NFA M是一个五元组： M=（K，f，S，Z），其中： K是一个有穷集，每个元素表示一个状态； 是一个有穷字母表，每个元素是一个输入字符； f是一个从K*到到K上的子集上的子集的映象； S K，是一个非空初态集； Z K，是一个终态集。 【要点】至少一个初态，若干个终态。 莆田学院网络中心许振和 40 映象映象 映象 （1）DFA任何状态都没有没有转换，即没有任何状态可以不 进行输入符号的匹配就直接进入下一个状态；

24、 （2）DFA对任何状态S和任何输入符号a，最多只有一条标 记为a的边离开S，即转换函数：S S是一个单值单值 部分函数。 （3）DFA的初态唯一初态唯一，NFA的初态为一集合。 莆田学院网络中心许振和 41 例子例子 NFA M=NFA M=（SS，P P，ZZ，00，11，f f，SS，PP，ZZ） 其中其中 f f（S S，0 0）=P=P f f（Z Z，0 0）=P=P f f（P P，1 1）=Z=Z f f（Z Z，1 1）=P=P f f（S S，1 1）=S=S，ZZ 状态图表示状态图表示 S P Z 0 0,1 1 1 1 * *上的符号串上的符号串t t被被NFA MNF

25、A M接受接受 若若t t * *，f(Sf(S0 0，t)=Pt)=P，其中，其中S S0 0 S S， P P Z Z，则称，则称t t为为NFA MNFA M所接受（识别）所接受（识别） 莆田学院网络中心许振和 42 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.2 非确定的FA(NFA) 例2.24: 给出一个接收字符串aa*|bb*的NFA M， 如下图所示。 对字符串aaa的接受路径为0，1，2，2，2，接受 路径中边的标记是，a，a，a，它们的连接为字符串 aaa，在连接中消失。 ab a start 0 4 1 3 2 a 莆田学院网络中心许振和 43 *上的符号串t

26、被NFA M接受（识别）: 对于*中的任何一个串t，若存在一条从某一初态 结点到某一终态结点的通路，且这条通路上所有 弧的标记字依序连接成的串(不理采那些标记为 的弧)等于t，则称t可为NFA M所识别(读出或接受)。 若M的某些结点既是初态结点又是终态结点；或 者存在一条从某个初态结点到某个终态结点的道 路,其上所有弧的标记均为，那么空字可为M所 接受。 莆田学院网络中心许振和 44 使用NFA判定某个输入符号串的时候，可能出现不 确定的情况：不知道下面选择那个状态。如果选择 不好，该输入符号串可能不能到达终止状态。但是， 我们不能说该输入符号串不能被该NFA接受。 如果通过尝试的方法，不断

27、试探来确定输入符号串 是否可被接受，那么判定的效率将降低。解决的方 法是将NFA转换为等价的DFA。 NFA M所能接受的符号串的全体记为L(M) 结论：上一个符号串集V 是正规的，当 且仅当存在一个上的不确定的有穷自动机 M，使得V=L(M)。 莆田学院网络中心许振和 45 定理：设定理：设L为一个由不确定的有穷自动机接受的集合，则存为一个由不确定的有穷自动机接受的集合，则存 在一个接受在一个接受L的确定的有穷自动机。的确定的有穷自动机。 将将NFA转换成接受同样语言的转换成接受同样语言的DFA，这种算法称为，这种算法称为子集法。子集法。 NFA与与DFA的等价性：的等价性：对于每个对于每个

28、NFA M存在一个存在一个DFA M， 使使L(M)=L(M)。 NFA可以利用可以利用子集法进行确定化子集法进行确定化，对于一个，对于一个NFA M总可以构总可以构 造一个等价的造一个等价的DFA M。 NFA到到DFA构造基本思路构造基本思路：DFA的每一个状态对于的每一个状态对于NFA的一的一 组状态。组状态。DFA利用它的一个状态去记录在利用它的一个状态去记录在NFA读入一个输入读入一个输入 符号后可能到达的所有状态。符号后可能到达的所有状态。 五、五、NFANFA转换为等价的转换为等价的DFADFA（NFANFA确定化）确定化） 莆田学院网络中心许振和 46 例例2-10 2-10

29、试把试把 例例2-92-9中构造出来的中构造出来的NFANFA确定化的确定化的 状态转换表。状态转换表。 表表2-32-3就是所求的就是所求的DFA MDFA M的状的状 态变迁函数。态变迁函数。 确定化确定化 前前 确定化确定化 后后 莆田学院网络中心许振和 47 将将NFA M进行确定化时应注意考虑进行确定化时应注意考虑 弧弧，方法是求，方法是求 闭包闭包( - closure),将此闭包将此闭包(状态子集状态子集)作为作为DFA的一个状态使用，而的一个状态使用，而 将将NFA的状态之间转换为闭包之间的转换。的状态之间转换为闭包之间的转换。 状态集合状态集合I的几个有关运算：的几个有关运算

30、： 1、状态集合、状态集合I的的 -闭包，表示为闭包，表示为 -closure(I)，定义为一状，定义为一状 态集，是状态集态集，是状态集I中的任何状态中的任何状态S经任意条经任意条 弧而能到达的状弧而能到达的状 态的集合。态的集合。状态集合状态集合I的任何状态的任何状态S都属于都属于 -closure(I) 2、状态集合、状态集合I的的a弧转换，表示为弧转换，表示为move(I,a)定义为状态集定义为状态集 合合J，其中，其中J是所有那些可从是所有那些可从I的某一状态经过一条的某一状态经过一条a弧而到弧而到 达的状态的全体。达的状态的全体。 带 弧的弧的NFA确定化方法： 莆田学院网络中心许

31、振和 48 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 例2.25: 有NFA M如下图所示。 1 238 5 4 6 7 a a a 莆田学院网络中心许振和 49 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 设 I= 1,5 则 -closure(1,5)=1,2,5,6 设 I=5 则 -closure(I) = -closure(5) = 5, 6, 2 设 I=1 则 -closure(1) = 1, 2 -closure (5) -closure (1) 莆田学院网络中心许振和 50 则 Ia =-closure（I） =-

32、closure（3） = 3,8 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 例2.26: 有NFA M如例2.25所示。 设I=1 则 Ia =-closure（I） =-closure（3 , 4 , 5） = 2, 3, 4, 5, 6,7,8 设I=2,5 莆田学院网络中心许振和 51 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 综述 求Ia步骤： (1) 求-closure(I)； (2) 求J； (3) 求-closure(J)； NFA确定化关键： (1) 消去弧； (2) 解决映射不唯一问题。 -closure(I)

33、求Ia 莆田学院网络中心许振和 52 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 子集法 对NFA M =（S, 1, 2, , n , f, S0, Z） 设一矩阵形式的表： I I 1I 2 I n -closure(S0) Step1:初始化 莆田学院网络中心许振和 53 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 I I 1I 2 I n -closure(S0)I11I12 I1n I11 I12 I1n Step2:求In I2n I3n 莆田学院网络中心许振和 54 Ch2 形式语言自动机理论基础2.2 自动机基础2.2

34、.3 NFA确定化 Step3: 重新命名 对求得的矩阵（DFA M）的第一列各状态子集 重新命名，然后代入相应的状态矩阵元素； 第一列第一行为DFA M 的惟一初态； 含有原M终态的I为M终态。 莆田学院网络中心许振和 55 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 例2.27: 有NFA M如下图所示。 1 238 5 4 6 7 a a a 莆田学院网络中心许振和 56 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化 IIa 2, 3, 4, 5, 6, 7, 8 3, 8 1 2 0 -closure(S0)=1,2 1* 2*

35、 2, 3, 4, 5, 6, 7, 8 3, 8 莆田学院网络中心许振和 57 例1、将下图的NFA确定化为DFA。 T0= -closure(X)=x,1,2 move(T0,a)=1 move(T0,b)=1,3 T1= -closure(move(T0,a)= -closure(1)=1,2 T2= -closure(move(T0,b)= -closure(1,3)=1,2,3 move(T1,a)=1 同同T1 move(T1,b)=1,3 同同T2 move(T2,a)=1,y move(T2,b)=1,3 同同T2 T3= -closure(move(T2,a)= -closu

36、re(1,y)=1,2,y move(T3,a)=1 同同T1 move(T3,b)=1,3 同同T2 莆田学院网络中心许振和 58 I IIaIaIbIb X X 1 1 2 2 3 3 1 1 1 1 3 3 1 1 2 2 2 2 2 2 2 2 IIaIb状态状态 X,1,2 1,2. 1,2,3 1,2,Y 1,2. 1,2. 1,2,Y 1,2. 1,2,3 1,2,3 1,2,3 1,2,3 X 1 2 3 莆田学院网络中心许振和 59 使用图使用图4.4的的NFAN的状态集合来理解上述两个运算：的状态集合来理解上述两个运算： -closure(0)=0,1,2,4,7 令令A=

37、0,1,2,4,7, move(A,a)=3,8 -closure(3,8)=1,2,3,4,6,7,8 图图4.4NFAN 莆田学院网络中心许振和 60 ab 0 00124701247 T0=0124738385 5 383812346781234678 5 5124567124567 T1=1234678T1=123467838385959 595912456791245679 T2=124567T2=12456738385 5 T3=1245679T3=12456793838510510 5105101245671012456710 T4=12456710T4=124567103838

38、5 5 例例2 对图对图4.4的的NFA N构构 造子集造子集 莆田学院网络中心许振和 61 IaIb T0=012471234678 T1 124567 T2 T1=1234678T1=12346781234678 T1 1245679 T3 T2=124567T2=1245671234678 T1124567 T2 T3=1245679T3=12456791234678 T112456710 T4 T4=124567T4=1245671 1 0 0 1234678 T1124567 T2 莆田学院网络中心许振和 62 图图4.6DFAM ab T0=012471234678 T112456

39、7 T2 T1=1234678T1=12346781234678 T11245679 T3 T2=124567T2=1245671234678 T1124567 T2 T3=1245679T3=12456791234678 T112456710 T4 T4=12456710T4=124567101234678 T1124567 T2 莆田学院网络中心许振和 63 六、确定有穷自动机六、确定有穷自动机DFA的化简的化简 （DFA最小化）最小化） 说一个有穷自动机是化简了的，即是说，它说一个有穷自动机是化简了的，即是说，它 没有多余状态没有多余状态并且它的状态中并且它的状态中没有两个是互相等没有两

40、个是互相等 价的价的。一个有穷自动机可以通过消除多余状态和。一个有穷自动机可以通过消除多余状态和 合并等价状态而转换成一个最小的与之等价的有合并等价状态而转换成一个最小的与之等价的有 穷自动机。穷自动机。 将多余状态消除而形成一个最小的等价的DFA。 化简不仅是去除死状态，不可能到达状态，还包 括状态的合并。 DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA 莆田学院网络中心许振和 64 1、多余状态的概念： 所谓有穷自动机的多余状态，是指这样的状态：从自动所谓有穷自动机的多余状态，是指这样的状态：从自动 机的开始状态出发，任何输入串也不能到达的那个状态；或机的开始状态出发，任何输

41、入串也不能到达的那个状态；或 者从这个状态没有通路到达终态。者从这个状态没有通路到达终态。 如下图中的S4状态是多余的。在图中，没有一 个状态能到达S4。当S4是多余时，又可以推出S6是 多余的。同样也可以推出S8也是多余的。 最小状态最小状态DFA的含义的含义: 1.没有多余状态没有多余状态(死状态死状态) 2.没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别） 莆田学院网络中心许振和 65 01 S0S1S50 S1S2S71 S2S2S51 S3S5S70 S4S5S60 S5S3S10 S6S8S01 S7S0S11 S8S3S60 01 S0S1S50 S1S2S7

42、1 S2S2S51 S3S5S70 S5S3S10 S7S0S11 化简后的结果： 左右等价 莆田学院网络中心许振和 66 2、等价的条件（状态、等价的条件（状态S和和T） 两个状态两个状态s s和和t t等价：满足等价：满足 兼容性兼容性同是终态或同是非终态同是终态或同是非终态 传播性传播性从从s s出发读入某个出发读入某个a a a a和从和从t t出发出发 读入某个读入某个a a到达的状态等价。到达的状态等价。 莆田学院网络中心许振和 67 3、等价的方法（分割法）等价的方法（分割法） 方法：将DFA的状态分割成一些互不相交的子集。 把一个把一个DFADFA（不含多余状态）的状态分成一些

43、不（不含多余状态）的状态分成一些不 相交的子集，使得任何不同的两子集的状态都相交的子集，使得任何不同的两子集的状态都 是可区别的，而同一子集中的任何两个状态都是可区别的，而同一子集中的任何两个状态都 是等价的。是等价的。 分割法的核心 把DFA的全部状态划分成一些互不相交的子 集，使得任何不同的两子集的状态都是可区别 的（不等价），而同一子集中的任何两个状态 都是等价的. 莆田学院网络中心许振和 68 DFA化简（最小化方法最小化方法） 算法算法： 所有状态分成两个子集终态集和非终态集； 运用判定状态等价的原则分别对两个子集的状 态进行分析和划分，若发现某个状态与其它状 态不等价，则将其作为一

44、个新的状态子集，如 果无法区分，则放在同一子集中； 从每个子集中选出一个状态做代表，即可构成 简化的DFA； 含有原来初态的子集仍为初态，各终态的子集 仍为终态。 莆田学院网络中心许振和 69 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简 Step1: 形成基本划分。划分为终态集和非终态集。 P0 = （ 0,1 , 2） 考察 ： 0,1a =1 0,1 0,1b =2 2 a 例1： 设确定有限自动机DFA M ，如图所示。 b b a a 02 1 Step2: 重新命名。令 0,1为0，令2为1。 基本划分 不可对 0,1 再分 莆田学院网络中心许振和 70

45、 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简 b a a 1 0 化简后的DFA M 莆田学院网络中心许振和 71 DB A S a a a b b b ba, C DB AE F Sb a a a a a a b b b b b b a 例例2：化简下图的：化简下图的DFA 莆田学院网络中心许振和 72 1 6 4 3 2 5 7 a a a a a a a b b bb b b b 例例3：将下图中的：将下图中的DFA M最小化。最小化。 莆田学院网络中心许振和 73 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简 第一步，对M的状态

46、形成基本划分： 设p 是基本划分。将 p分成q , q2，即 p=(1, 2, 3, 4 , 5, 6, 7 )= ( q1,q2 ) 第二步，对q , q2考察知： 对p的q，I=1时 Ia= 6 I=2时 Ia= 7 I=3时 Ia= 1 I=4时 Ia= 4 Ib= 3 Ib= 3 Ib= 5 Ib= 6 莆田学院网络中心许振和 74 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简 对q1形成新的划分： q1=(q3, q4)=（1, 2，3, 4） 对p的q2， I=5时 Ia=7 Ib=3 I=6时 Ia=4 Ib=1 I=7时 Ia=4 Ib=2 在输入a

47、或b的情况下， q2中的状态5 与状态 6,7 是不等价的，构成q2新的划分： 莆田学院网络中心许振和 75 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简 q2新的划分： q2 =( q5, q6 )=（5，6, 7） 由此，对基本划分p0 经考察且划分后， 形成新的划分p1： p1 =（q3，q4，q5，q6） = ( 1,2，3,4，5，6,7 ) 莆田学院网络中心许振和 76 Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简 第三步，对新形成的划分p1重复上述第二 步，则对p1 中q4的状态 3,4 在输入字符a 的情况下考察其是不等价

48、的，再划分为 q4=（q7, q8）=（3, 4） 对划分p1 经考察且划分后，形成新的划分p2： p2 =（q3, q5, q6, q7, q8 ） = ( 1,2, 5, 6,7 , 3, 4 ) 莆田学院网络中心许振和 77 1 6 4 3 2 5 7 a a a a a a a b b bb b b b 1 6 4 3 5 a a a a a b b bb b 至此所有状态集中的状态皆为等价状态。 莆田学院网络中心许振和 78 合并状态注意： a、由于一个子集中，各状态等价，故只需将原进入该子集 中各状态的弧都改为进入所选的状态，子集中各状态射出 的弧均改为从该状态射出。 b、含有原来

49、初态的子集仍为初态，含原终态原终态的子集仍为终终 态态 莆田学院网络中心许振和 79 例例4：将下图中的：将下图中的DFA M最小化。最小化。 1 402 35 7 6 00 0 0 0 0 0 0 1 1 1 1 1 1 莆田学院网络中心许振和 80 1、一个终态（可接受态）组成，一个非终态组成。 P0(0,1,2,3,5,4,6,7) 2、0,1状态输入1到2状态,2,5输入1到4状态,3 状态输入1为,2状态和4状态属于不同的子 集,P1=(0,1,2,5,3) 3、4,7输入1到状态4,6输入1到, P3=(4,7,6) 0,1、2,5、 3、4,7、 6都不可再分了,分别 用A,B,

50、C,D,E表示,简化后图如下: 莆田学院网络中心许振和 81 1 402 35 7 6 00 0 0 0 0 0 0 1 1 1 1 1 1 ADB CE 0 00 00 1 1 1 莆田学院网络中心许振和 82 正规式和FA之间也可以互相转换，转换的方 法是从已知的正规式先构造出等价的-NFA（本 节），去掉-NFA中的空动作变换为不含迁移 的NFA，然后再把NFA转化为DFA，最后再对DFA化 简，求得最小DFA。 上述各种转换关系可用图2-8表示。 七、七、正规式和有穷自动机的等价性正规式和有穷自动机的等价性 莆田学院网络中心许振和 83 正规式和有穷自动机的等价性：正规式和有穷自动机的

51、等价性： 对于对于上的上的NFA MNFA M，可以构造一个，可以构造一个 上的正规式上的正规式R R，使得，使得L(R)=L(M)L(R)=L(M)。 对于对于上的每个正规式上的每个正规式R R，可以构，可以构 造一个造一个上的上的NFA MNFA M，使得，使得L(M)=L(R)L(M)=L(R)。 莆田学院网络中心许振和 84 Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA (1) 增加结点X，并从 X引弧到达S0中的所有状态； (2) 增加结点 Y，并从Z中所有状态引弧 到达 Y； step1: 将NFA M进行拓广； 1、在NFA M上构照正规式R。即从

52、L(M) L(R） 方法：在每一条弧上用一个正规式作标记。 规则如下： 莆田学院网络中心许振和 85 Y 3 a X step2: 利用利用替换规则一替换规则一逐步消去逐步消去 M中的结和弧，并中的结和弧，并 用正规式代替原来用正规式代替原来M 中的弧标记，直至只剩下中的弧标记，直至只剩下 结为止。结为止。 X Y 莆田学院网络中心许振和 86 (1)123 R1R2 1 3 R1R2 (2) 12 R1 R2 21 R1|R2 21 R1+R2 替换为 或 (3) 321 R1 R2 R3 31 R1R2*R3 替换为 替换为 替换规则一替换规则一 莆田学院网络中心许振和 87 Ch2 形式

53、语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA Y 12 3 4 b b a a 0 a,b 例1: 有NFA M 如下图所示。 a,b a,b 莆田学院网络中心许振和 88 Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA Y 12 3 4 b b a a 0 a,b a,b a,bX 莆田学院网络中心许振和 89 Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA Y 12 3 b a a,b 4 X (a|b)*b (a|b)*a 用规则(3)消去0结和a,b弧 a,b 莆田学院网络中心许振和 90 Ch2 形式语言

54、自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA 用规则(3)消去2,4结和2个a|b弧 Y 1 3 X (a|b)*b (a|b)*a b(a|b)* a(a|b)* 莆田学院网络中心许振和 91 Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA (a|b)*aa(a|b)* Y X 用规则(1)消去1,3结 (a|b)*b b(a|b)* 莆田学院网络中心许振和 92 Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA 用规则(2)消去2个弧 (a|b)*bb(a|b)*|(a|b)*aa(a|b)* Y Y X 用分配率实

55、施化简 (a|b)*(aa|bb)(a|b)* X 正规式正规式 莆田学院网络中心许振和 93 例2: L(M)如下图： 求正规式R，使L(R)=L(M). 解： a b a,b a b a,b xy y a|b x a|b yx (a|b)(a|b)*因此： L(R)= (a+b)(a+b)* 莆田学院网络中心许振和 94 例4：L(M)如下图，求L(R) - + + ab ba a b a,b 莆田学院网络中心许振和 95 解： - + + ab ba a b a,b - ab ba a b a,b x y 莆田学院网络中心许振和 96 - ab ba a|b a,b x y - a|b

56、ababba x y (ababba)*(a+b) xy 所以所以 L(R) = (ababba)*(a+b) =(a+b)*(a+b)=(a+b)+ 莆田学院网络中心许振和 97 例例5：L(M) 如下图，求如下图，求L(R) . - + abb bb ab ba a,b a 解： - + abb bb abba a,b a 莆田学院网络中心许振和 98 abba+abb+bb + a,b - a a*(abba+abb+bb)(a+b)* +- 所以 L(R) = a*(abba+abb+bb)(a+b)* 注：注：abba+abb+bb 不能把不能把bb提取出来提取出来 莆田学院网络中心

57、许振和 99 2、L(R) NFA，从正规式，从正规式R构造构造NFA 由正规式V直接形成拓广的FA状态图。构造上 的NFA M，使得L(M)=L(V); 方法如下：方法如下： 莆田学院网络中心许振和 100 Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA ai 1) 若V是或上的字符ai , 则 2) 若1）不成立，则V具有V1|V2，V1V2，(V1)*形式 ，按照替换规则二分解V； 3） 对新产生的弧标记重复1）、2），直到没有新的 弧和结产生为止。得到V相应的M，且L(M)=L(v). XY XY 莆田学院网络中心许振和 101 Ch2 形式语言自动机理论

58、基础2.3 正规式与自动机2.3.2 正规式与FA R1 R1|R2 A B R2 A B 替换为 R1* A B AC B 替换为 R1 AC R2 B R1R2 A B 替换为 R1 替换规则二 (1) 莆田学院网络中心许振和 102 例1：L(R) =(a+b)*abb，构造NFA使L(N)=L(R) 解： xy (a+b)*abb xy abb a,b xy abb a b x y a b abb 莆田学院网络中心许振和 103 y a b abb 例2： L(R): b(a+b)* 求L(M) - + b a,b a a,b 莆田学院网络中心许振和 104 例3：L(R) =(a+b

59、)b(a+b)* 求L(M)。 a b a b a,b a,b 例4： L(R) =(a+b)*(aa+bb)(a+b)* 构造L(N)使与L(R) 等价。 莆田学院网络中心许振和 105 xy (a+b)*(aa+bb)(a+b)* xy (a+b)*aa+bb(a+b)* xy aa bb a,b a,b 莆田学院网络中心许振和 106 x y a b a a a b b b - + a b a a a b b b 莆田学院网络中心许振和 107 八、正规文法和有穷自动机的等价性八、正规文法和有穷自动机的等价性 采用下面的规则可以从正规文法采用下面的规则可以从正规文法G直接构造一个有穷直接

60、构造一个有穷 自动机自动机NFAM；使得；使得L（M）L（G）：）： M M的字母表与的字母表与G G的终结符集相同的终结符集相同 为为G G中的每个非终结符生成中的每个非终结符生成M M的一个状态，的一个状态，G G的开始符的开始符S S是开是开 始状态始状态S S 增加一个新状态增加一个新状态Z Z，作为，作为NFANFA的终态的终态 对对G G中的形如中的形如A A tBtB的规则（其中的规则（其中t t为终结符或为终结符或 ，A A和和B B为为 非终结符的产生式），构造非终结符的产生式），构造M M的一个转换函数的一个转换函数f(A,t)=Bf(A,t)=B 对对G G中形如中形如A