编译原理22自动机理论

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

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

3、称（简称正规式正规式）表示。表示。 正规表达式正规表达式是表示是表示正规集正规集一种方法。一一种方法。一个字集合是个字集合是正规集正规集当且仅当它能用当且仅当它能用正规正规式式表示。表示。6 正规式和正规集的递归定义：正规式和正规集的递归定义：对给定的字母表对给定的字母表 1) 和和都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集为集为 和和;2) 任何任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的正规集为正规集为a ;73) 假定假定e e1 1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集为正规集为L(e1)和和L(e2)，则，

4、则i) (e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1) L(e2)，ii) (e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，iii) (e1)*为正规式，它所表示的正规集为为正规式，它所表示的正规集为(L(e1)*，仅由仅由有限次有限次使用上述三步骤而定义的表达式才使用上述三步骤而定义的表达式才是是 上的正规式，仅由这些正规式表示的字集上的正规式，仅由这些正规式表示的字集才是才是 上的正规集。上的正规集。8正规式正规集aaa|ba,babab(a|b)(a|b)aa，bb,ab,baa*，a,aa, ，aaaa(a|

5、b)* ，a,b,aa,ab,aab,abab, (a|b)*(aa|bb) (a|b)*上所有含有两个相继的a或两个相继的b组成的串例：例： a,ba,b， 上的正规式和相应的正规集为：上的正规式和相应的正规集为：9其中的其中的“ ”读为读为“或或”（也有使用（也有使用“+”代替代替 “ ” 的的）；）；“ ”读为读为“连接连接”；“ ”读为读为“闭包闭包”（即，任（即，任意有限次的自重复连接）。在不致混淆时，括号可省去，意有限次的自重复连接）。在不致混淆时，括号可省去，但规定算符的优先顺序为但规定算符的优先顺序为“ ”、“ ”、“ ”、“ ”、“ ” 。连接符。连接符“ ”一般可省略不写。

6、一般可省略不写。“ ”、“ ”和和“ ” 都是左结合的都是左结合的10 讨论下面两个例子讨论下面两个例子例例1 1 令令 =l=l，dd，则，则 上的正规式上的正规式 r=l(lr=l(l d)d) 定义定义的正规集为的正规集为: l,ll,ld,ldd,: l,ll,ld,ldd,其中其中l l代表字母代表字母,d,d代表数字代表数字, ,正规式正规式 即是即是 字母字母( (字母字母| |数字数字) ) , ,它表示的正规集中的每个它表示的正规集中的每个元素的模式是元素的模式是“字母打头的字母数字串字母打头的字母数字串”,”,就是就是PascalPascal和多数程序设计语言允许的标和多数

7、程序设计语言允许的标识符的词法规则识符的词法规则. .11例例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,12.59,3.6e2,471.88e-1等都是正规等都是正规式表示集合中的元素。式表示集合中的元素。12若两个正规式若两个正规式e e1 1和和e e2 2所表示的所表示的正规集相同，正规集相同，则说则说

8、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 ) ) 正规式的等价正规式的等价13 对正规式，下列等价成立：对正规式，下列等价成立： e1|e2 = e2|e1 交换律交换律 e1 |(e2|e3) = (e1|e2)|e3 结合律结合律 e1(e2e3) = (e1e2)e3 结合

9、律结合律 e1(e2|e3) = e1e2|e1e3 分配律分配律 (e2|e3)e1 = e2e1|e3 e1分配律分配律 e = e = e e1e2 e2 e1 S*=(S|)* 是是“连接连接”的恒等元素（零一律）的恒等元素（零一律） (a*)*=a*L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)14对于任意一个正规文法，存在一个同一语言的正规式。对每一个正规式，存在一个正规文法。即正规式正规文法 正规式正规式正规文法正规文法文法G=（VN，VT，P，S）令VT=，对正规式r，选择一个非终结符S生成Sr，S为G的开始符号。 若x，y都是正

10、规式，对形如Axy的产生式，写成AxB，By。其中B VN二、正规文法与正规式转换二、正规文法与正规式转换* *15 对形如Ax*y的产生式，重写为： AxB Ay BxB By B为新的非终结符，B VN对形如Ax|y的产生式，重写为： Ax Ay 不断利用上述规则进行变换即可。16例：将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)y17最后得到：SaAAaBAdBA BaBBdBB 18 正规文法正规文法正规式正规式转换规则：转换规则： AxB，

11、By 正规式为： A=xy AxA|y 正规式为： A=x*y Ax，Ay 正规式为： A=x|y 例：文法GS：S aAS aA aAA dAA aA d转换为正规式19S 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)20Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a(a|d)+将A代入SaA|a得到如下：21 三、三、确定的

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

13、中： Q是一个有穷集，每个元素表示一个状态；是一个有穷字母表，每个元素是一个输入字符； f是转换函数，是在QQ上的映象上的映象，如： f(Qi ，a)= Qj (Qi, QjQ)； q0是初态， q0 K； ZQ，是终态集。 含义：当前状态为Ki，输入字符a，转换为Kj状态DFADFA映射的唯一性和初态的唯一性映射的唯一性和初态的唯一性23 方法如下： 初始态用 “”或“”表示； 终态点用 “” 或“” 表示； 若f(Ki ，a)= Kj ，则从状态点Ki 到Kj画弧，标记为a。1 1、单词的构成规则用状态转换图表示、单词的构成规则用状态转换图表示DFADFA等价表示法：等价表示法：DFADF

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

15、识别过程。状态上的*表示多读入一个符号。012字母字母或数字其它*26例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定义如下：定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3状态图如下：0312aaaa状态转换图状态转换图bbbb27例: 一个单部电梯对3层楼进行控制的电梯控制系统的DFA描述。问题分析：用户请求（输入）上1、上2、上3下1、下2、下3状态设置（所处楼层）1层2层3层S1S2S328Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA

16、（DFA）S2S3S1上2/下2上3/下3上1/下1下1下2上3上2下1上3292、用矩阵表示、用矩阵表示DFA :方法： 行表示状态 列表示输入字符 元素表示相应状态行和输入字符下的新状态。 “” 标明初态，默认第一行是初态。 终态行在表右端标1，非终态标030 例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定义如下：定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3状态转换矩阵状态转换矩阵31例：baSZa,b表示：f(S,a)=Z f(S,b)=Z f(Z,a)=

17、Z f(Z,b)=ZabSZZZZZ01写成正规式是： (a|b)(a|b)*32Ch2 形式语言自动机理论基础2.2 自动机基础2.2.1 确定的FA（DFA）电梯控制的状态矩阵表示上1下1上2 下2上3下3S1* S1S2*S3*S1S1S1S2S2 S2S2S3S3S3 S3333、DFA接接受（识别）的概念受（识别）的概念： 对于对于*中的任何字符串中的任何字符串t，若存在一条初态到若存在一条初态到某一终态的路，且这条路上所有弧的标记符连接成某一终态的路，且这条路上所有弧的标记符连接成的字符串等于的字符串等于t，则称，则称t可为可为DFA M所接受。所接受。 若若M的初态同时又是终态，

18、则空字可为的初态同时又是终态，则空字可为M所接所接受。受。34 输入字符串输入字符串t（t表示成表示成Tt1形式，形式，T ，t1 *），在），在DFA M上运行的定义为：上运行的定义为：f（Q，Tt1）=f(f(Q,T),t1)，其中，其中Q K。4、接受（识别）的理解：接受（识别）的理解： 设设Q K，函数，函数f(Q, )=Q，则输入字符串是，则输入字符串是空串，并停留在原状态上。空串，并停留在原状态上。 35例：证明例：证明t t= =baabbaab被下图的被下图的DFADFA所接受所接受。f f（S S，baabbaab）=f=f（f f（S S，b b），），aabaab） =

19、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, baa36 DFA的确定性表现在：的确定性表现在： 对任何状态s S，在读入了输入符号a 之后，能够唯一地确定唯一地确定下一个状态 映射函数：SS是一个单值单值函数 从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有最多有n条弧条弧射出射出，而且每条弧以一个不同的输入不同的输入字符字符标记。37 DFA M所能接受

20、的字符串的全体记为L（M）称为语言 （也即句子的集合）结论：结论： 上一个符上一个符号号串集串集V V 是正规的，当且仅当是正规的，当且仅当存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M M，使得，使得V=L(M)V=L(M) 文法是语言的生成系统，是从产生的观点来描述语言的。 自动机是语言的识别系统，是从识别的观点来描述语言的文法和自动机的对比文法和自动机的对比38四、四、 不确定的有穷自动机不确定的有穷自动机NFA 一个不确定的有穷自动机NFA M是一个五元组：M=（Q，f， q0 ，Z），其中： Q是一个有穷集，每个元素表示一个状态； 是一个有穷字母表，每个元素是一个输入字符；

21、 f是一个从Q()到到2Q的映象； q0是初态， q0 Q ； Z Q，是一个终态集。【要点】至少一个初态，若干个终态。39 （1）DFA任何状态都没有没有转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态； （2）DFA对任何状态S和任何输入符号a，最多只有一条标记为a的边离开S，即转换函数：S S是一个单值单值部分函数。40例子例子 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）

22、=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所接受（识别）所接受（识别）41Ch2 形式语言自动机理论基础2.2 自动机基础2.2.2 非确定的FA(NFA)例2.24: 给出一个接收字符串aa*|bb*的NFA M，如下图所示。对字符串aaa的接受路径为0，1，2，2，2，接受路径中边的标记是，a，a，a，它们的连接为字符串aaa，在连接中消失。abastart04132a

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

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

25、以利用可以利用子集法进行确定化子集法进行确定化，对于一个，对于一个NFA M总可以构总可以构造一个等价的造一个等价的DFA M。NFA到到DFA构造基本思路构造基本思路：DFA的每一个状态对于的每一个状态对于NFA的一的一组状态。组状态。DFA利用它的一个状态去记录在利用它的一个状态去记录在NFA读入一个输入读入一个输入符号后可能到达的所有状态。符号后可能到达的所有状态。五、五、NFANFA转换为等价的转换为等价的DFADFA（NFANFA确定化）确定化）454647 -closure(I) = -closure(1)=1，2=I J=5，4，3 Ia= -closure(J)= -closu

26、re(5，4，3) =5，4，3，6，2，7，861a 234578aa 设设a是是 中的一个中的一个字符，定义字符，定义Ia= -closure(J) 其中，其中，J为为I中的某中的某个状态出发经过个状态出发经过一条一条a弧而到达弧而到达的状态集合。的状态集合。48 把确定化的过程把确定化的过程: : 不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个a a和和b b，我们构造一张表我们构造一张表: :IIaIb -Closure(X)49首先，置第首先，置第1行第行第1列为列为 -closure(X)求出求出这一列的这一列的Ia，Ib；然后，检查这两个然后，检查这两个Ia，Ib，

27、看它们是否已在，看它们是否已在表中的第一列中出现，把未曾出现的填入表中的第一列中出现，把未曾出现的填入后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.重复上述过程，知道所有第重复上述过程，知道所有第2，3列子集全列子集全部出现在第一列为止。部出现在第一列为止。50IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4

28、,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab ababab51 现在把这张表看成一个状态转换矩阵，把现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。其中的每个子集看成一个状态。 这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机M，它的初态是，它的初态是 -closure(X) ，它的终，它的终态是含有原终态态是含有原终态Y的子集。的子集。 不难看出，这个不难看出，这个DFA M与与M等价。等价。52Iab0121322143*344*655*656*340123546aabbbabaababab53Ch2

29、形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化综述 求Ia步骤：(1) 求-closure(I)；(2) 求J；(3) 求-closure(J)；NFA确定化关键：(1) 消去弧；(2) 解决映射不唯一问题。-closure(I)求Ia54Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化例2: 有NFA M如下图所示。12385467aaa55Ch2 形式语言自动机理论基础2.2 自动机基础2.2.3 NFA确定化IIa2, 3, 4, 5, 6, 7, 8 3, 8120 -closure(S0)=1,21*2*2, 3, 4, 5, 6, 7, 8

30、 3, 8565758六、确定有穷自动机六、确定有穷自动机DFA的化简的化简（DFA最小化）最小化） 说一个有穷自动机是化简了的，即是说，它说一个有穷自动机是化简了的，即是说，它没有多余状态没有多余状态并且它的状态中并且它的状态中没有两个是互相等没有两个是互相等价的价的。一个有穷自动机可以通过消除多余状态和。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有合并等价状态而转换成一个最小的与之等价的有穷自动机。穷自动机。 将多余状态消除而形成一个最小的等价的DFA。化简不仅是去除死状态，不可能到达状态，还包括状态的合并。 DFA的最小化就是寻求最小状态的最小化就是寻求

31、最小状态DFA591、多余状态的概念： 所谓有穷自动机的多余状态，是指这样的状态：从自动所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。者从这个状态没有通路到达终态。 如下图中的S4状态是多余的。在图中，没有一个状态能到达S4。当S4是多余时，又可以推出S6是多余的。同样也可以推出S8也是多余的。 最小状态最小状态DFA的含义的含义: 1.没有多余状态没有多余状态(死状态死状态) 2.没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）6001S

32、0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价612、等价的条件（状态、等价的条件（状态S和和T） 两个状态两个状态s s和和t t等价：满足等价：满足一致性一致性同是终态或同是非终态同是终态或同是非终态蔓延性蔓延性从从S S出发读入所有出发读入所有a a a a和从和从T T出发出发读入读入a a到达的状态等价。到达的状态等价。623、等价的方法（分割法）等价的方法（分割法）方法：将DFA的状态分割成一些互

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

34、态不等价，则将其作为一个新的状态子集，如果无法区分，则放在同一子集中； 从每个子集中选出一个状态做代表，即可构成简化的DFA； 含有原来初态的子集仍为初态，各终态的子集仍为终态。64Ch2 形式语言自动机理论基础2.2 自动机基础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 再分65Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的

35、化简baa10化简后的DFA M66CBASaaabbbba,CDBAEFSbaaaaaabbbbbba例例2：化简下图的：化简下图的DFA671643257aaaaaaabbbbbbb例例3：将下图中的：将下图中的DFA M最小化。最小化。68Ch2 形式语言自动机理论基础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

36、= 3Ib= 5Ib= 669Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简对q1形成新的划分：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新的划分：70Ch2 形式语言自动机理论基础2.2 自动机基础2.2.4 DFA的化简q2新的划分：q2 =( q5, q6 )=（5，6, 7）由此，对基本划分p0 经考察且划分后，形成新的划分p1：p1 =（q3，q4，q5，q6）= ( 1,2，3,4，

37、5，6,7 )71Ch2 形式语言自动机理论基础2.2 自动机基础2.2.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 )721643257aaaaaaabbbbbbb16435aaaaabbbbb至此所有状态集中的状态皆为等价状态。73 合并状态注意：a、由于一个子集中，各状态等价，故只需将原进入该子集中各状态的弧都改为进入所选

38、的状态，子集中各状态射出的弧均改为从该状态射出。b、含有原来初态的子集仍为初态，含原终态的子集仍为终态74例例4：将下图中的：将下图中的DFA M最小化。最小化。1402357600000000111111751、一个终态（可接受态）组成，一个非终态组成。 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表示,简化后图如下:7614023576000

39、00000111111ADBCE0000011177 正规式和FA之间也可以互相转换，转换的方法是从已知的正规式先构造出等价的-NFA（本节），去掉-NFA中的空动作变换为不含迁移的NFA，然后再把NFA转化为DFA，最后再对DFA化简，求得最小DFA。 上述各种转换关系可用图2-8表示。七、七、正规式和有穷自动机的等价性正规式和有穷自动机的等价性 78正规式和有穷自动机的等价性：正规式和有穷自动机的等价性： 对于对于上的上的NFA MNFA M，可以构造一个，可以构造一个上的正规式上的正规式R R，使得，使得L(R)=L(M)L(R)=L(M)。 对于对于上的每个正规式上的每个正规式R R，

40、可以构，可以构造一个造一个上的上的NFA MNFA M，使得，使得L(M)=L(R)L(M)=L(R)。79Ch2 形式语言自动机理论基础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）方法：在每一条弧上用一个正规式作标记。规则如下：80Y3aXstep2: 利用利用替换规则一替换规则一逐步消去逐步消去 M中的结和弧，并中的结和弧，并用正规式代替原来用正规式代替原来M 中的弧标记，直至只剩下中的弧标记

41、，直至只剩下结为止。结为止。XY81(1)123R1R213R1R2(2)12R1R221R1|R221R1+R2替换为或(3)321R1R2R331R1R2*R3替换为替换为替换规则一替换规则一82Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAY1234bbaa0a,b例1: 有NFA M 如下图所示。a,ba,b83Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAY1234bbaa0a,ba,ba,bX84Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAY123baa,b4X(a|b)*b(a|b)*a用

42、规则(3)消去0结和a,b弧a,b85Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA用规则(3)消去2,4结和2个a|b弧Y13X(a|b)*b(a|b)*ab(a|b)*a(a|b)*86Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FA(a|b)*aa(a|b)*YX用规则(1)消去1,3结(a|b)*b b(a|b)*87Ch2 形式语言自动机理论基础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)

43、*X正规式正规式88例2: L(M)如下图：求正规式R，使L(R)=L(M).解：aba,baba,bxyya|bxa|byx(a|b)(a|b)*因此：L(R)= (a|b)(a|b)*8903412aabba,ba,ba,b例3：M状态图如下：求正规式R，是L(R)=L(M).90解：加解：加x,y结点。结点。a,b03412aabba,ba,bxy91042aabba,ba,bxya,ba,b0aa(a|b)*bb(a|b)*xy92y(a|b)*(aa|bb)(a|b)*x所以 L(R) =(a|b)*(aa|bb)(a|b)* 例4：L(M)如下图，求L(R)-+abbaaba,b9

44、3解：-+abbaaba,b-abbaaba,bxy94-abbaa|ba,bxy-a|ba|b|abbaxy(a|b|abba)*(a|b)xy所以所以 L(R) = (a|b|abba)*(a|b) =(a|b)*(a|b)=(a|b)+95例例5：L(M) 如下图，求如下图，求L(R) .-+abbbbabbaa,ba解：-+abbbbabbaa,ba96abba|abb|bb+a,b-aa*(abba|abb|bb)(a|b)*+-所以 L(R) = a*(abba|abb|bb)(a|b)* 注：注：abba+abb+bb 不能把不能把bb提取出来提取出来972、L(R) NFA，从

45、正规式，从正规式R构造构造NFA由正规式V直接形成拓广的FA状态图。构造上的NFA M，使得L(M)=L(V);方法如下：方法如下：98Ch2 形式语言自动机理论基础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).XYXY99Ch2 形式语言自动机理论基础2.3 正规式与自动机2.3.2 正规式与FAR1R1|R2ABR2AB替换为R1*ABACB替换为R1ACR2BR

46、1R2AB替换为R1替换规则二(1)100例1：L(R) =(a|b)*abb，构造NFA使L(N)=L(R)解：xy(a|b)*abbxyabba,bxyabbabxyababb101例： L(R) =(a|b)*(aa|bb)(a|b)*构造L(M)使与L(R) 等价。102xy(a+b)*(aa+bb)(a+b)*xy(a+b)*aa+bb(a+b)*xyaabba,ba,b103xya baaabbb104八、正规文法和有穷自动机的等价性八、正规文法和有穷自动机的等价性采用下面的规则可以从正规文法采用下面的规则可以从正规文法G直接构造一个有穷直接构造一个有穷自动机自动机NFAM；使得；

47、使得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 A t t的产生式，构造的产生式，构造M M的一个转换函数的一个转换函数f(A,t)=Zf(A,t)=Z105 例例2-6 2-6 已知正规文法已知正规文法G3G3(S(S，A A，BB，aa，b b，c c，P P，S) S)，其中，其中P P内包含以下产生式：内包含以下产生式：根据上述转换方法，与G3等价的FA M为：其中函数的定义式为：106例例2：与文法：与文法GS等价的等价的NFAM如图如图4.11GS: S a A S a A S bBS bBS S A aBA aBA bA A bA B aSB aSB bA B bA B B 107有穷自动机转换成等价的正规文法：有穷自动机转换