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

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

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

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

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

5、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正规式正规集aaa|ba,babab(a|b)(a|b)aa，bb,ab,baa*，a,aa, ，aaaa(a|b)* ，a,b,aa,ab

6、,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或两个相继的或两个相继的b b组成的串组成的串 1. 1. 正规式与相应的正规集是等价的，正规集给出了正规式与相应的正规集是等价的，正规集给出了相应正规式

7、所描述的全部单词（句子）；相应正规式所描述的全部单词（句子）； 2. 2. 正规式的运算结果是正规集；正规式的运算结果是正规集； 3. 3. 正规式不是集合，其运算结果正规集是集合。正规式不是集合，其运算结果正规集是集合。莆田学院网络中心许振和11 讨论下面两个例子讨论下面两个例子例例1 1 令令 =l l，dd，则，则 上的正规式上的正规式 r=l(lr=l(l d d) ) 定义定义的正规集为的正规集为: l,ll,ld,ldd: l,ll,ld,ldd, ,其中其中l l代表字母代表字母,d,d代表数字代表数字, ,正规式正规式 即是即是 字母字母( (字母字母| |数字数字) ) ,

8、,它表示的正规集中的每个它表示的正规集中的每个元素的模式是元素的模式是“字母打头的字母数字串字母打头的字母数字串”, ,就是就是PascalPascal和多数程序设计语言允许的标和多数程序设计语言允许的标识符的词法规则识符的词法规则. .莆田学院网络中心许振和12例例2 2：令：令 d d， ，e e，则，则 上的正上的正规式为：规式为：d d* *(.dd(.dd* *| | )(e(+|-|)(e(+|-| )dd)dd* *| | ) )表示的是无符号数。表示的是无符号数。 其中其中d d为为0 09 9中的数字。中的数字。 比如：比如：2,12.59,3.6e2,471.88e-12,

9、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又如：又如： 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 ) )

10、正规式的等价正规式的等价莆田学院网络中心许振和14设设e e1 1、e e2 2、e e3 3为正规式，有如下运算规则：为正规式，有如下运算规则： 莆田学院网络中心许振和15对于任意一个正规文法，存在一个同一语言的正规式。对每一个正规式，存在一个正规文法。即正规式正规文法 正规式正规式正规文法正规文法文法G=（VN，VT，P，S）令VT=，对正规式r，选择一个非终结符S生成Sr，S为G的开始符号。 若x，y都是正规式，对形如Axy的产生式，写成AxB，By。其中B VN二、正规文法与正规式转换二、正规文法与正规式转换* *莆田学院网络中心许振和16 对形如Ax*y的产生式，重写为： AxB A

11、y BxB By B为新的非终结符，B VN对形如Ax|y的产生式，重写为： Ax Ay 不断利用上述规则进行变换即可。莆田学院网络中心许振和17例：将Ra(a|d)*变换成正规文法。令S是文法开始符号。解：S a(a|d)*SaAA(a|d)*A(a|d)BA B(a|d)BB 根据上述规则1xa，y(a|d)*根据上述规则2x(a|d)y莆田学院网络中心许振和18最后得到：SaAAaBAdBA BaBBdBB 莆田学院网络中心许振和19 正规文法正规文法正规式正规式转换规则：转换规则： AxB，By 正规式为： A=xy AxA|y 正规式为： A=x*y Ax，Ay 正规式为： A=x|

12、y 例：文法GS：S aAS aA aAA dAA aA d转换为正规式莆田学院网络中心许振和20S aAS aA aAA dAA aA dSaA|aAaA|dAAa|dA(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d)根据上述规则3Ax，Ay推出A=x|y将它化为正规文法变成A (a|d)A|(a|d) 再根据上述规则2转换xy (a|d)莆田学院网络中心许振和21Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a(a|d)+将A代入SaA|a得到如下：莆田学院网络中心许振和22 三、三、确定的有穷自动机确定的有穷自动机DF

13、A 有穷自动机( (也称有限自动机也称有限自动机) )作为一种识作为一种识别装置别装置，是词法分析程序的工具和方法，能自动识别（且是正确识别正确识别）正规集。即识别正规即识别正规文法所定义的语言和正规式所表示的集合，引文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。的自动构造寻找特殊的方法和工具。分为确定的有穷自动机（确定的有穷自动机（DFA）不确定的有穷自动机（不确定的有穷自动机（NFA） 莆田学院网络中心许振和23一个确定的有穷自动机M是一个五元组： M=（K，f，S，Z），其中： K是

14、一个有穷集，每个元素表示一个状态；是一个有穷字母表，每个元素是一个输入字符； f是转换函数，是在KK上的映象上的映象，如： f(Ki ，a)= Kj (Ki, KjK)； S是初态，S K； ZK，是终态集。 含义：当前状态为Ki，输入字符a，转换为Kj状态DFADFA映射的唯一性和初态的唯一性映射的唯一性和初态的唯一性莆田学院网络中心许振和24 方法如下： 初始态用 “”或“”表示； 终态点用 “” 或“” 表示； 若f(Ki ，a)= Kj ，则从状态点Ki 到Kj画弧，标记为a。1 1、单词的构成规则用状态转换图表示、单词的构成规则用状态转换图表示DFADFA等价表示法：等价表示法：DF

15、ADFA形式定义形式定义= =状态转换图状态转换图= =状态矩阵状态矩阵莆田学院网络中心许振和25状态转换图(也称状态变迁图状态变迁图)是一张有限方向图。有限个状态，用结点表示状态，其中有一个初态有一个初态(初态用箭头指出)，至少有一个终态至少有一个终态(终态用双圈表示)。状态之间用带箭头的弧线连结，弧线上标记的字符表示在射出状态下可能出现的输入字符或字符类。识别标识符的转换图012字母字母或数字其它*莆田学院网络中心许振和26一个状态图可用于识别一定的字符串，大多数程序设计语言的单词符号都可以用转换图来识别。识别过程是识别过程是：从初始状态0开始，若读入一个字母，转入1状态，若再读入字母或数

16、字，仍处于1状态，否则转向2状态，结束一个标识符的识别过程。状态上的*表示多读入一个符号。012字母字母或数字其它*莆田学院网络中心许振和27例：DFA的M(S,U,V,Q,a,b,f,S,Q)其中f为：f(S,a)=U, f(S,b)=V, f(U,a)=Qf(U,b)=V, f(V,a)=U, f(V,b)=Qf(Q,a)=Q, f(Q,b)=Q状态图如下：a,baaabbbSUVQa,b莆田学院网络中心许振和28Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA（DFA）例2.21: 一个单部电梯对3层楼进行控制的电梯控制系统的DFA描述。问题分析：用户请求（输入）上

17、1、上2、上3下1、下2、下3状态设置（所处楼层）1层2层3层S1S2S3莆田学院网络中心许振和29Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA（DFA）S2S3S1上2/下2上3/下3上1/下1下1下2上3上2下1上3莆田学院网络中心许振和302、用矩阵表示、用矩阵表示DFA :方法： 行表示状态 列表示输入字符 元素表示相应状态行和输入字符下的新状态。 “” 标明初态，默认第一行是初态。 终态行在表右端标1，非终态标0莆田学院网络中心许振和31上例矩阵表示如下：abSUVUQVVUQQQQ字符状态0001莆田学院网络中心许振和32例：baSZa,b表示：f(S,a

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

19、串等于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，则输入字符串是，则输入字符串是空串，并停留在原状态上。空串，并停留在原状态上。 莆田学院网络中心许振和36例：证明例：证明t t= =baabbaab被下图的

20、被下图的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 QQ Q属于终态。属于终态。得证。得证。bSUVQabba, baa莆田学院网络中心许振和37 DFA的确定性表现在：的确定性表现在： 对任何状态s S，在读入了输入符号a 之后，能够唯一地确定唯一地确定下一个状态 映射函数：SS是一个单值单值函数 从状态转换图来看，若

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

22、机不确定的有穷自动机NFA 一个不确定的有穷自动机NFA M是一个五元组：M=（K，f，S，Z），其中： K是一个有穷集，每个元素表示一个状态； 是一个有穷字母表，每个元素是一个输入字符； f是一个从K*到到K上的子集上的子集的映象； S K，是一个非空初态集； Z K，是一个终态集。【要点】至少一个初态，若干个终态。莆田学院网络中心许振和40映象映象映象 （1）DFA任何状态都没有没有转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态； （2）DFA对任何状态S和任何输入符号a，最多只有一条标记为a的边离开S，即转换函数：S S是一个单值单值部分函数。 （3）DFA的初态唯一初

23、态唯一，NFA的初态为一集合。莆田学院网络中心许振和41例子例子 NFA M=NFA M=（SS，P P，ZZ，00，11，f f，SS，PP，ZZ）其中其中 f f（S S，0 0）=P=Pf f（Z Z，0 0）=P=Pf f（P P，1 1）=Z=Zf f（Z Z，1 1）=P=Pf f（S S，1 1）=S=S，ZZ状态图表示状态图表示SPZ00,1111 * *上的符号串上的符号串t t被被NFA MNFA M接受接受若若t t * *，f(Sf(S0 0，t)=Pt)=P，其中，其中S S0 0 S S，P P Z Z，则称，则称t t为为NFA MNFA M所接受（识别）所接受（

24、识别）莆田学院网络中心许振和42Ch2 形式语言自动机理论基础2.2 自动机基础2.2.2 非确定的FA(NFA)例2.24: 给出一个接收字符串aa*|bb*的NFA M，如下图所示。对字符串aaa的接受路径为0，1，2，2，2，接受路径中边的标记是，a，a，a，它们的连接为字符串aaa，在连接中消失。abastart04132a莆田学院网络中心许振和43*上的符号串t被NFA M接受（识别）: 对于*中的任何一个串t，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。 若M的某些结

25、点既是初态结点又是终态结点；或者存在一条从某个初态结点到某个终态结点的道路,其上所有弧的标记均为，那么空字可为M所接受。莆田学院网络中心许振和44 使用NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择那个状态。如果选择不好，该输入符号串可能不能到达终止状态。但是，我们不能说该输入符号串不能被该NFA接受。 如果通过尝试的方法，不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA。 NFA M所能接受的符号串的全体记为L(M)结论：上一个符号串集V 是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。莆田学院网络

26、中心许振和45定理：设定理：设L为一个由不确定的有穷自动机接受的集合，则存为一个由不确定的有穷自动机接受的集合，则存在一个接受在一个接受L的确定的有穷自动机。的确定的有穷自动机。将将NFA转换成接受同样语言的转换成接受同样语言的DFA，这种算法称为，这种算法称为子集法。子集法。NFA与与DFA的等价性：的等价性：对于每个对于每个NFA M存在一个存在一个DFA M，使使L(M)=L(M)。NFA可以利用可以利用子集法进行确定化子集法进行确定化，对于一个，对于一个NFA M总可以构总可以构造一个等价的造一个等价的DFA M。NFA到到DFA构造基本思路构造基本思路：DFA的每一个状态对于的每一个

27、状态对于NFA的一的一组状态。组状态。DFA利用它的一个状态去记录在利用它的一个状态去记录在NFA读入一个输入读入一个输入符号后可能到达的所有状态。符号后可能到达的所有状态。五、五、NFANFA转换为等价的转换为等价的DFADFA（NFANFA确定化）确定化）莆田学院网络中心许振和46 例例2-10 2-10 试把试把 例例2-92-9中构造出来的中构造出来的NFANFA确定化的确定化的状态转换表。状态转换表。 表表2-32-3就是所求的就是所求的DFA MDFA M的状的状态变迁函数。态变迁函数。确定化确定化前前确定化确定化后后莆田学院网络中心许振和47将将NFA M进行确定化时应注意考虑进

28、行确定化时应注意考虑 弧弧，方法是求，方法是求 闭包闭包( -closure),将此闭包将此闭包(状态子集状态子集)作为作为DFA的一个状态使用，而的一个状态使用，而将将NFA的状态之间转换为闭包之间的转换。的状态之间转换为闭包之间的转换。状态集合状态集合I的几个有关运算：的几个有关运算：1、状态集合、状态集合I的的 -闭包，表示为闭包，表示为 -closure(I)，定义为一状，定义为一状态集，是状态集态集，是状态集I中的任何状态中的任何状态S经任意条经任意条 弧而能到达的状弧而能到达的状态的集合。态的集合。状态集合状态集合I的任何状态的任何状态S都属于都属于 -closure(I)2、状态

29、集合、状态集合I的的a弧转换，表示为弧转换，表示为move(I,a)定义为状态集定义为状态集合合J，其中，其中J是所有那些可从是所有那些可从I的某一状态经过一条的某一状态经过一条a弧而到弧而到达的状态的全体。达的状态的全体。带 弧的弧的NFA确定化方法：莆田学院网络中心许振和48Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化例2.25: 有NFA M如下图所示。12385467aaa莆田学院网络中心许振和49Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化设 I= 1,5则 -closure(1,5)=1,2,5,6设 I=5则 -closur

30、e(I) = -closure(5)= 5, 6, 2设 I=1则 -closure(1) = 1, 2-closure (5) -closure (1)莆田学院网络中心许振和50则Ia =-closure（I）=-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莆田学院网络中心许振和51Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化综述

31、求Ia步骤：(1) 求-closure(I)；(2) 求J；(3) 求-closure(J)；NFA确定化关键：(1) 消去弧；(2) 解决映射不唯一问题。-closure(I)求Ia莆田学院网络中心许振和52Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化子集法对NFA M =（S, 1, 2, , n , f, S0, Z）设一矩阵形式的表：II 1I 2I n-closure(S0)Step1:初始化莆田学院网络中心许振和53Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化II 1I 2I n-closure(S0)I11I12I1nI11

32、I12I1nStep2:求InI2nI3n莆田学院网络中心许振和54Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化Step3: 重新命名对求得的矩阵（DFA M）的第一列各状态子集重新命名，然后代入相应的状态矩阵元素；第一列第一行为DFA M 的惟一初态；含有原M终态的I为M终态。莆田学院网络中心许振和55Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化例2.27: 有NFA M如下图所示。12385467aaa莆田学院网络中心许振和56Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化IIa2, 3, 4, 5, 6,

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

34、sure(move(T2,a)= -closure(1,y)=1,2,ymove(T3,a)=1 同同T1 move(T3,b)=1,3 同同T2莆田学院网络中心许振和58I IIaIaIbIbX X1 12 23 31 11 13 31 12 22 22 22 2IIaIb状态状态X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123莆田学院网络中心许振和59使用图使用图4.4的的NFAN的状态集合来理解上述两个运算：的状态集合来理解上述两个运算： -closure(0)=0,1,2,4,7令令A=0,1,2,4,7, mov

35、e(A,a)=3,8 -closure(3,8)=1,2,3,4,6,7,8图图4.4NFAN莆田学院网络中心许振和60 ab0 00124701247T0=0124738385 53838123467812346785 5124567124567T1=1234678T1=123467838385959595912456791245679T2=124567T2=12456738385 5T3=1245679T3=124567938385105105105101245671012456710T4=12456710T4=1245671038385 5例例2 对图对图4.4的的NFA N构构造子集造

36、子集莆田学院网络中心许振和61IaIbT0=012471234678 T1124567 T2T1=1234678T1=12346781234678 T11245679 T3T2=124567T2=1245671234678 T1124567 T2T3=1245679T3=12456791234678 T112456710 T4T4=124567T4=12456710101234678 T1124567 T2莆田学院网络中心许振和62图图4.6DFAMabT0=012471234678 T1124567 T2T1=1234678T1=12346781234678 T11245679 T3T2=1

37、24567T2=1245671234678 T1124567 T2T3=1245679T3=12456791234678 T112456710 T4T4=12456710T4=124567101234678 T1124567 T2莆田学院网络中心许振和63六、确定有穷自动机六、确定有穷自动机DFA的化简的化简（DFA最小化）最小化） 说一个有穷自动机是化简了的，即是说，它说一个有穷自动机是化简了的，即是说，它没有多余状态没有多余状态并且它的状态中并且它的状态中没有两个是互相等没有两个是互相等价的价的。一个有穷自动机可以通过消除多余状态和。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成

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

39、个状态能到达S4。当S4是多余时，又可以推出S6是多余的。同样也可以推出S8也是多余的。 最小状态最小状态DFA的含义的含义: 1.没有多余状态没有多余状态(死状态死状态) 2.没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）莆田学院网络中心许振和6501S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价莆田学院网络中心许振和662、等价的条件（状态、等价的条件（状态S和和T） 两个状态两个

40、状态s s和和t t等价：满足等价：满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s s出发读入某个出发读入某个a a a a和从和从t t出发出发读入某个读入某个a a到达的状态等价。到达的状态等价。莆田学院网络中心许振和673、等价的方法（分割法）等价的方法（分割法）方法：将DFA的状态分割成一些互不相交的子集。把一个把一个DFADFA（不含多余状态）的状态分成一些不（不含多余状态）的状态分成一些不相交的子集，使得任何不同的两子集的状态都相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是可区别的，而同一子集中的任何两个状态都是等价的

41、。是等价的。分割法的核心 把DFA的全部状态划分成一些互不相交的子集，使得任何不同的两子集的状态都是可区别的（不等价），而同一子集中的任何两个状态都是等价的.莆田学院网络中心许振和68DFA化简（最小化方法最小化方法） 算法算法： 所有状态分成两个子集终态集和非终态集； 运用判定状态等价的原则分别对两个子集的状态进行分析和划分，若发现某个状态与其它状态不等价，则将其作为一个新的状态子集，如果无法区分，则放在同一子集中； 从每个子集中选出一个状态做代表，即可构成简化的DFA； 含有原来初态的子集仍为初态，各终态的子集仍为终态。莆田学院网络中心许振和69Ch2 形式语言自动机理论基础2.2 自动机

42、基础2.2.4 DFA的化简Step1: 形成基本划分。划分为终态集和非终态集。P0 = （ 0,1 , 2）考察 ： 0,1a =1 0,10,1b =2 2a例1： 设确定有限自动机DFA M ，如图所示。bbaa021Step2: 重新命名。令 0,1为0，令2为1。基本划分不可对 0,1 再分莆田学院网络中心许振和70Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简baa10化简后的DFA M莆田学院网络中心许振和71DBASaaabbbba,CDBAEFSbaaaaaabbbbbba例例2：化简下图的：化简下图的DFA莆田学院网络中心许振和721643257a

43、aaaaaabbbbbbb例例3：将下图中的：将下图中的DFA M最小化。最小化。莆田学院网络中心许振和73Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简第一步，对M的状态形成基本划分： 设p是基本划分。将 p分成q , q2，即p=(1, 2, 3, 4 , 5, 6, 7 )= ( q1,q2 )第二步，对q , q2考察知：对p的q，I=1时 Ia= 6I=2时 Ia= 7I=3时 Ia= 1I=4时 Ia= 4Ib= 3Ib= 3Ib= 5Ib= 6莆田学院网络中心许振和74Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简对q1形成新的

44、划分：q1=(q3, q4)=（1, 2，3, 4）对p的q2， I=5时 Ia=7 Ib=3I=6时 Ia=4 Ib=1I=7时 Ia=4 Ib=2在输入a或b的情况下， q2中的状态5与状态 6,7 是不等价的，构成q2新的划分：莆田学院网络中心许振和75Ch2 形式语言自动机理论基础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 )莆田学院网络中心许振和76Ch2 形式语言自动机理论基础2.2 自动机基础2.2

45、.4 DFA的化简第三步，对新形成的划分p1重复上述第二步，则对p1 中q4的状态 3,4 在输入字符a的情况下考察其是不等价的，再划分为q4=（q7, q8）=（3, 4）对划分p1 经考察且划分后，形成新的划分p2：p2 =（q3, q5, q6, q7, q8 ）= ( 1,2, 5, 6,7 , 3, 4 )莆田学院网络中心许振和771643257aaaaaaabbbbbbb16435aaaaabbbbb至此所有状态集中的状态皆为等价状态。莆田学院网络中心许振和78 合并状态注意：a、由于一个子集中，各状态等价，故只需将原进入该子集中各状态的弧都改为进入所选的状态，子集中各状态射出的弧

46、均改为从该状态射出。b、含有原来初态的子集仍为初态，含原终态原终态的子集仍为终终态态莆田学院网络中心许振和79例例4：将下图中的：将下图中的DFA M最小化。最小化。1402357600000000111111莆田学院网络中心许振和801、一个终态（可接受态）组成，一个非终态组成。 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,C,D,E表示,简化后图如下:

47、莆田学院网络中心许振和811402357600000000111111ADBCE00000111莆田学院网络中心许振和82 正规式和FA之间也可以互相转换，转换的方法是从已知的正规式先构造出等价的-NFA（本节），去掉-NFA中的空动作变换为不含迁移的NFA，然后再把NFA转化为DFA，最后再对DFA化简，求得最小DFA。 上述各种转换关系可用图2-8表示。七、七、正规式和有穷自动机的等价性正规式和有穷自动机的等价性 莆田学院网络中心许振和83正规式和有穷自动机的等价性：正规式和有穷自动机的等价性： 对于对于上的上的NFA MNFA M，可以构造一个，可以构造一个上的正规式上的正规式R R，使

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

49、替换规则一替换规则一逐步消去逐步消去 M中的结和弧，并中的结和弧，并用正规式代替原来用正规式代替原来M 中的弧标记，直至只剩下中的弧标记，直至只剩下结为止。结为止。XY莆田学院网络中心许振和86(1)123R1R213R1R2(2)12R1R221R1|R221R1+R2替换为或(3)321R1R2R331R1R2*R3替换为替换为替换规则一替换规则一莆田学院网络中心许振和87Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAY1234bbaa0a,b例1: 有NFA M 如下图所示。a,ba,b莆田学院网络中心许振和88Ch2 形式语言自动机理论基础2.3 正规式与

50、自动机2.3.2 正规式与FAY1234bbaa0a,ba,ba,bX莆田学院网络中心许振和89Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAY123baa,b4X(a|b)*b(a|b)*a用规则(3)消去0结和a,b弧a,b莆田学院网络中心许振和90Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA用规则(3)消去2,4结和2个a|b弧Y13X(a|b)*b(a|b)*ab(a|b)*a(a|b)*莆田学院网络中心许振和91Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA(a|b)*aa(a|b)*YX用规

51、则(1)消去1,3结(a|b)*b b(a|b)*莆田学院网络中心许振和92Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA用规则(2)消去2个弧(a|b)*bb(a|b)*|(a|b)*aa(a|b)*YYX用分配率实施化简(a|b)*(aa|bb)(a|b)*X正规式正规式莆田学院网络中心许振和93例2: L(M)如下图：求正规式R，使L(R)=L(M).解：aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)= (a+b)(a+b)*莆田学院网络中心许振和94 例4：L(M)如下图，求L(R)-+abbaaba,b莆田学院网络中心许

52、振和95解：-+abbaaba,b-abbaaba,bxy莆田学院网络中心许振和96-abbaa|ba,bxy-a|bababbaxy(ababba)*(a+b)xy所以所以 L(R) = (ababba)*(a+b) =(a+b)*(a+b)=(a+b)+莆田学院网络中心许振和97例例5：L(M) 如下图，求如下图，求L(R) .-+abbbbabbaa,ba解：-+abbbbabbaa,ba莆田学院网络中心许振和98abba+abb+bb+a,b-aa*(abba+abb+bb)(a+b)*+-所以 L(R) = a*(abba+abb+bb)(a+b)* 注：注：abba+abb+bb

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

54、自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAR1R1|R2ABR2AB替换为R1*ABACB替换为R1ACR2BR1R2AB替换为R1替换规则二(1)莆田学院网络中心许振和102例1：L(R) =(a+b)*abb，构造NFA使L(N)=L(R)解：xy(a+b)*abbxyabba,bxyabbabxyababb莆田学院网络中心许振和103yababb例2： L(R): b(a+b)* 求L(M)-+ba,baa,b莆田学院网络中心许振和104例3：L(R) =(a+b)b(a+b)* 求L(M)。 ababa,ba,b例4： L(R) =(a+b)*(aa+bb)(a+b)

55、*构造L(N)使与L(R) 等价。莆田学院网络中心许振和105xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b莆田学院网络中心许振和106xya baaabbb-+a baaabbb莆田学院网络中心许振和107八、正规文法和有穷自动机的等价性八、正规文法和有穷自动机的等价性采用下面的规则可以从正规文法采用下面的规则可以从正规文法G直接构造一个有穷直接构造一个有穷自动机自动机NFAM；使得；使得L（M）L（G）：）：M M的字母表与的字母表与G G的终结符集相同的终结符集相同为为G G中的每个非终结符生成中的每个非终结符生成M M的一个状态

56、，的一个状态，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 A t t的产生式，构造的产生式，构造M M的一个转换函数的一个转换函数f(A,tf(A,t)=Z)=Z莆田学院网络中心许振和108 例例2-6 2-6 已知正规文法已知正规文法G3G3(S(S，A A，BB，aa，b b，c c，P P，S) S)，其中，其中P P内包含以下产生式：内包含以下产生式：根据上述转换方法，与G3等价的FA M为：其中函数的定义式为：莆田学院网络中心许振