1、 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系第3章 有穷自动机 （自动机自动机是一种能进行运算并能实现自我控制的装置，是描述符号串处理的强有力的工具。本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式和有穷自动机之间的相互关系） 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系3.1 有穷自动机的形式定义3.2 NDFA到DFA的转换3.3 正规文法与有穷自动机3.4 正规表达式与FA3.5 DFA在计算机中的表示3.6 小结 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系3.1 有穷自动机的形式定义一个确定的有穷自动机（DFA）M
2、是一个五元式:M=(Q , ，t ,q0 , F) 其中:1. Q 有穷状态集2. 输入字母表3. t 映射函数(也称状态转换函数) QQ t(q , a)=q , q , q Q, a4. q0 初始状态 q0 Q5. F终止状态集 FQ 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系状态转移函数可用一矩阵来表示： 输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3例如: M:（0,1,2,3,a,b,t，0，3） t（0，a）=1 t（0，b）=2 t（1，a）=3 t（1，b）=2 t（2，a）=1 t（2，b）=3 t（3，a）=3 t（3，b）=
3、3所谓确定的状态机，其确定性都表现在状态转移函数是单值函数！ 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系一个DFA也可以用一状态转换图表示： 输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3DFA的状态图表示：1032startaabba,bba 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上能有弧的标记符号连接成符号串，则称为DFA M（接受）识别。DFA M所接受的语言为：L(M)=|t(Q0, )=Qn, Qn ZDFA M所接受的符号串：令=a1a2an，若 t (
4、t ( t (Q0, a1),a2)），an-1）,an)=Qn,且Qn Z，则可以写成 t (Q0, )= Qn,我们称可为M所接受。* 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 自动机的等价性 两个有穷自动机A1和A2， 如果L(A1)=L(A2), 则称自动机A1与A2等价。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 非确定有穷自动机非确定有穷自动机(NFA) 若若t是一个多值函数，且输入可允许为是一个多值函数，且输入可允许为，则有穷自动机是不确定的，则有穷自动机是不确定的,即在某个状态下，对于某个输入字符存在多个后继状态即在某个状态下，对于某
5、个输入字符存在多个后继状态.NFA的形式定义为:一个非确定的有穷自动机NFA M是一个五元式: NFA M=( Q , , t , Q0 , F )其中 Q有穷状态集 输入符号加上,即自动机的每个结点所射出的弧 可以是中的一个字符或是. Q0初态集 F终态集 t转换函数 Q 2Q (2Q -Q的幂集Q的子集构成的集合） 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系NFA M所接受的语言为所接受的语言为: L(M)=| t(Q0,)=Q QF 例： NFA M=(1,2,3,4 , a,b,c,d , t , 1 ,4) 符号 状态 a b c 1 4 2，3 2 2 4 3
6、3，4 4 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系上例题相应的状态图为： 1234startabacac*M所接受的语言（用正则表达式） R=aa b|ac c| 符号 状态 a b c 1 4 2，3 2 2 4 3 3，4 4 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系3.2 NDFA到DFA的转换 已证明：非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的，也就是说，我们能够从：NDFA MDFA M构造成一个使得 L(M)=L(M) 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 如果自动机的弧上允许标记，则称此自动机为
7、自动机，记为NDFA或DFA。 自动机的状态转换图中会出现由若干条弧组成的空移环路或空移。 消除空移环路和空移 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 消除空移环路 找到空移环路之后，要消除它只需把空移环路上的所有节点合并成一个节点，并消除它们所有的弧。如果其中的某一个节点是开始状态或终止状态，则将此合并之后的新节点相应设置为开始状态或终止状态。 消除空移 消除某条弧的空移，需要引入若干条新弧来取代原来弧的作用。 假设状态A有一条弧发出到达状态B，则在消除空移后，如果B是终止状态，则设置A为终止状态，而如果从开始状态经过一条路径到达状态A，则设置B为开始状态。 2007
8、年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 NDFA确定化 子集法 设NDFA A=(,Q ,t ,Q0,F)是一个非确定的有穷自动机，那么可以通过子集法构造一个和它等价的确定有穷自动机DFA A=(,Q, t, q0, F)。构造方法如下： 输入字母表不变 把NDFA A的每一个状态子集都作为DFA A的一个状态状态 DFA A的映射映射定义 t(r1,r2,rm , a) = q = t (r1,a)t (r2,a)t (rm,a) DFA A的开始状态开始状态q0s1 , s2 , , sk，其中，siQ0( i =1,2,k) DFA A的终态集终态集为包含原终止状态的子集
9、组成 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 造表法 造表法中DFA A的输入字母表 、开始状态q0和终态集F的确定都与子集法的构造方法一致。 状态集Q与映射函数t则是随着造表的过程而动态生成。 首先求出开始状态q0在接受各输入字母后状态变迁的结果，将其填入表中。然后把得到的结果作为新的状态，再求其接受各输入字母后状态变迁的结果，填入表中，如此过程不断重复，直到最后无新结果（状态）出现为止，此时造表结束。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系定义1、集合I的-闭包：令令I是一个状态集的子集，定义是一个状态集的子集，定义-closure（I）为：
10、）为：1）若）若sI，则，则s-closure（I）；）；2）若）若sI，则从，则从s出发经过任意条出发经过任意条弧能够到达的任何弧能够到达的任何 状态都属于状态都属于-closure（I）。）。 状态集状态集-closure（I）称为）称为I的的-闭包闭包我们可以通过一例子来说明状态子集的-闭包的构造方法 NDFA的确定化 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例：如图所示的状态图：令I=1，求-closure（I）=？156432aaa根据定义：-closure（I）=1，3 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系我们同样可以通过一例子来说明
11、上述定义,仍采用前面给定的状态图为例- J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合.-I-Ia a是状态子集,其元素为J中的状态,加上从J中每一个状态出发通过弧到达的状态定义2: 令I是NFA M的状态集的一个子集, a 定义: Ia=-closure(J) 其中J = (s,a)SI 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例：令 I=1 Ia=-closure(J) =-closure(（1，a） =-closure(2，4）=2，4，6根据定义1，2，可以将上述的M确定化（即可构造出状态的转换矩阵）156432aaa 2007年年9月月湖北大
12、学数计学院计科系湖北大学数计学院计科系例：有NFA M a1234startabaccI=-closure(1)=1,4Ia=-closure(1,a)(4,a) = -closure(2,3） = -closure (2,3) =2,3Ib= -closure(1,b)(4,b) = -closure(） =Ic= -closure(1,c)(4,c) = I=2,3, Ia=2,Ib=4,Ic=3,4 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系1234startabacc I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4 3,4 3,4 20
13、07年年9月月湖北大学数计学院计科系湖北大学数计学院计科系将求得的状态转换矩阵重新编号DFA M状态转换矩阵： 符号状态abc0 2 341221_3344 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系DFA M的状态图：01423start1,42,342acabbc 注意：包含原初始状态1的状态子集为DFA M的初态 包含原终止状态4的状态子集为DFA M的终态。3,4 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 消除不可达状态 在自动机中，从开始状态出发没有任何一条路径能达到的状态称为不可达状态不可达状态。 注：在使用子集法对NDFA进行确定化的过程
14、中，常会产生一些不可达状态，需要在最后将其消除。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系 DFA的化简“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”一个有穷自动机是化简的 它没有多余状态并且它的状态 中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系定义：(1) 有穷自动机的多余状态有穷自动机的多余状态：从该自动机的开始状态出发,任 何输入串也不能到达那个状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s1
15、01s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例:画状态图可以看出s4,s6,s8为不可达状态应该消除 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系(2)等价状态 状态s和t的等价条件是:1)一致性条件：状态s和t必须同时为可接受状态或 不接受状态.2)蔓延性条件：对于所有输入符号,状态s和t必须 转换到等价的状态里. 对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同的后继，则称s，t是等价的。（任何有后继的状态和任何无后继的状态一定不等价）有穷自动机的状态s和t不等价,称这两个状态是可区
16、别的。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系“分割法”：把一个DFA(不含多余状态)的状态分割成一些 不相关的子集，使得任何不同的两个子集状态 都是可区别的，而同一个子集中的任何状态都 是等价的.例:最小化5724361srartaaaaaaabbbbbbb 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系解:(一)区分终态与非终态12345663731546737414212ab123456637315467374142ab123区号区号 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系123456637315467374142ab124
17、31243123456637315467374142ab5区号区号 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系将区号代替状态号得:12345ab521435523115 5243aaaaabbbbb 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系3.3 正规文法与有穷自动机（1）正则文法G有穷自动机A令正规文法G的终结符号集作为有穷自动机A的字母表。文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符号作为自动机A的开始状态。在自动机A中增加一个新状态Z作为自动机的终止状态。对于文法G的形如U:=aV的产生式，在自动机A中构造形如t(U,a)
18、=V的映射。对于文法G的形如U:=a的产生式，在自动机A中构造形如t(U,a)=Z的映射。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例:求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA|SZABstartaaabbb求得： 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系（2）有穷自动机A 正则文法G自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。对于自动机的映射t（U,a）=V，构造文法的一条产生式 U:= a V对于自动机
19、的终止状态Z，在正规文法中增加一条产生式 Z:= 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例:给出如图NFA等价的正规文法GABCDstartaaabbbbG=（A，B，C，D，a，b，P，A）其中P: A aB A bD B bC C aA C bD C D aB D bD D 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系3.4 正规表达式与FA 正规表达式和正规集合的递归定义正规表达式和正规集合的递归定义有字母表有字母表 , , 定义在定义在 上的正规表达式和正规集合递归定义如下上的正规表达式和正规集合递归定义如下: :1. 1. 和和 都是都是 上
20、的正规表达式上的正规表达式, , 它们所表示的正规集合分别为它们所表示的正规集合分别为: 和和 ; ;2. 2. 任何任何a a , a , a是是 上的正规表达式上的正规表达式, ,它所表示的正规集合为它所表示的正规集合为:a; :a; 3. 3. 假定假定U U和和V V都是都是 上的正则表达式上的正则表达式, , 它们所表示的正则集合分别记为它们所表示的正则集合分别记为L(U)L(U)和和L(V), L(V), 那么那么U|V, UU|V, UV V和和U U* *也都是也都是 上的正则表达式上的正则表达式, , 它们所表示它们所表示的正则集合分别为的正则集合分别为L(U) L(U) L
21、(V)L(V)、 L(U) L(U) L(V) L(V)和和L(U)L(U)* *4. 4. 任何任何 上的正规表达式和正规集合均由上的正规表达式和正规集合均由1 1、2 2和和3 3产生。产生。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系正则表达式中的运算符正则表达式中的运算符： | - - 或（选择）或（选择） - - 连接连接 * * - - 重复重复 / / （）（） - - 括号括号运算符的优先级运算符的优先级： 先先*（闭包）（闭包）, 后后 （连接）（连接） , , 最后最后 | |（或）（或） 在正则表达式中可以省略在正则表达式中可以省略. .正则表达式相等
22、正则表达式相等 这两个正则表达式表示的语言相等这两个正则表达式表示的语言相等 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例：设例：设 = a,b , = a,b ,下面是定义在下面是定义在 上的正规表达式和正规集合上的正规表达式和正规集合正规表达式正规表达式 正规集正规集 ba* b , ba , baa , baaa , a(a|b)* a , aa , ab , aaa , aab , aba , abb , (a|b)*(aa|bb)(a|b)* aa , bb , aaa , baa , abaaba , abbaab , 2007年年9月月湖北大学数计学院计科系湖
23、北大学数计学院计科系正则表达式的性质正则表达式的性质： 设设e1, e2e1, e2和和e3e3均是某字母表上的正则表达式均是某字母表上的正则表达式, , 则有则有: : 单位正则表达式单位正则表达式: : e = ee = e = e = e 交换律交换律: e1 | e2 = e2 | e1: e1 | e2 = e2 | e1结合律结合律: e1|(e2|e3) = (e1|e2)|e3 : e1|(e2|e3) = (e1|e2)|e3 e1(e2e3) = (e1e2)e3 e1(e2e3) = (e1e2)e3分配律分配律: e1(e2|e3) = e1e2|e1e3 : e1(e
24、2|e3) = e1e2|e1e3 (e1|e2)e3 = e1e3|e2e3 (e1|e2)e3 = e1e3|e2e3 此外此外: r: r* * = (r| = (r| ) )* * r r* * * =r =r* * (r|s) (r|s)* * = (r = (r* *s s* *) )* * 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系（1）正则表达式 NDFA (a)对于正则式,所构造NFA: xy (b)对于正则式,所构造NFA: xy (c)对于正则式a,a,则 NFA: xya 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系( d ) AB
25、e1e2ABe1|e2ABe1*ABCe1e2ABe1e2ABCe1( e ) ( f ) 替换成替换成替换成 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例:为R=(a|b) abb构造NFA,使得L(N)=L(R)*012345ababb 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系（2） NDFA 正则表达式 在转换之前，先对NDFA进行扩充，允许状态转换图中弧上可以是正规表达式。具体操作如下： 在NDFA的状态转换图中，新设置一个唯一的开始状态S和一个唯一的终结状态Z。然后，从开始状态S到原开始状态连接弧，再从原终止状态到Z状态也连接弧。修改后的ND
26、FA，显然和原NDFA等价。接着，对新NDFA按照如下替换规则进行替换，直到状态转换图中只剩下状态S和Z为止。当状态转换图中只有状态S和Z时，在S到Z的弧上标记的正规表达式e便是所求结果。 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系(1) ABe1e2ABe1|e2ABe1e2*e3ABCe1e2ABe1e2ABCe2e1e3(2) (3) 替换成替换成替换成 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系例:M:03214starta,ba,ba,bbbaa解: (1)加入S、ZS03412Zaa,ba,ba,babb 2007年年9月月湖北大学数计学院计
27、科系湖北大学数计学院计科系(2)消除M中的所有结点a|bS024Zaabba|ba|bS0Zaa(a|b) *bb(a|b) *a|b解: (1)加xyS03412Zaa,ba,ba,babbSZ(a|b)*(aa|bb)(a|b)* 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系（3）正规文法正规表达式 在转换之前，先将正规文法拓广，其产生式可以是 U:=V 或 U:= 其中U、VVN , VT*转换规则为：产生式U:=V , V:= , U、VVN , 、 VT* ，转换为正规表达式U=产生式U:=U|，转换为U=*产生式U:=|，转换为U=| 2007年年9月月湖北大学数
28、计学院计科系湖北大学数计学院计科系例:有文法Gs SaA|a, AaA|dA|a|d于是: S=aA|a A=(aA|dA)|(a|d)A=(a|d)A|(a|d)由规则: A=(a|d)*(a|d) 代入:S=a(a|d)*(a|d)|a 于是:S=a(a|d)*(a|d)|) 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系（4）正规表达式正规文法算法:1)对任何正规式r,选择一个非终结符S作为识别符号. 并产生产生式 Sr2)若x,y是正规式,对形为Axy的产生式,重写为 AxB By,其中B为新的非终结符,BVN 同样: 对于 Ax*y AxA Ay Ax|y Ax Ay例:将R=a(a|d)*转换成相应的正规文法解:1) Sa(a|d)* 2) SaA A(a|d)*3) SaA A(a|d)A A4) SaA AaA|dA A 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系正规文法正规文法NFA正规表达式正规表达式DFA最小化最小化 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系3.5 DFA在计算机中的表示 矩阵表示法 表结构 2007年年9月月湖北大学数计学院计科系湖北大学数计学院计科系本章重点：正规表达式到最简DFA的转换作业：P58-59 3.2 3.3 3.4 3.7 3.9 3.10
