编译原理课件-(3)

第3章 有穷自动机,（自动机是一种能进行运算并能实现自我控制的装置，是描述符号串处理的强有力的工具。本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式和有穷自动机之间的相互关系）,Compiler,2007年9月,湖北大学数计学院计科系,3.1 有穷自动机的形式定义 3.2 NDFA到DFA的转换 3.3 正规文法与有穷自动机 3.4 正规表达式与FA 3.5 DFA在计算机中的表示 3.6 小结,2007年9月,湖北大学数计学院计科系,3.1 有穷自动机的形式定义,一个确定的有穷自动机（DFA）M是一个五元式: M=(Q , ，t ,q0 , F),其中: 1. Q 有穷状态集 2. 输入字母表 3. t 映射函数(也称状态转换函数) Q×Q t(q , a)=q , q , q Q, a 4. q0 初始状态 q0 Q 5. F终止状态集 FQ,2007年9月,湖北大学数计学院计科系,例如: 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,所谓确定的状 态机，其确定 性都表现在状 态转移函数是 单值函数！,2007年9月,湖北大学数计学院计科系,一个DFA也可以用一状态转换图表示：,2007年9月,湖北大学数计学院计科系,换言之：若存在一条初始状态到某一终止状态的路径，且这条路径上能有弧的标记符号连接成符号串，则称为DFA M（接受）识别。,DFA M所接受的语言为：L(M)=|t(Q0, )=Qn, Qn Z,DFA M所接受的符号串： 令=a1a2¨¨¨an，若 t ( 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是一个多值函数，且输入可允许为，则有穷自动机是不确定的, 即在某个状态下，对于某个输入字符存在多个后继状态.,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,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,3.2 NDFA到DFA的转换,2007年9月,湖北大学数计学院计科系,如果自动机的弧上允许标记，则称此自动机为自动机，记为NDFA或DFA。 自动机的状态转换图中会出现由若干条弧组成的空移环路或空移。, 消除空移环路和空移,2007年9月,湖北大学数计学院计科系,消除空移环路 找到空移环路之后，要消除它只需把空移环路上的所有节点合并成一个节点，并消除它们所有的弧。如果其中的某一个节点是开始状态或终止状态，则将此合并之后的新节点相应设置为开始状态或终止状态。,消除空移 消除某条弧的空移，需要引入若干条新弧来取代原来弧的作用。 假设状态A有一条弧发出到达状态B，则在消除空移后，如果B是终止状态，则设置A为终止状态，而如果从开始状态经过一条路径到达状态A，则设置B为开始状态。,2007年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的终态集为包含原终止状态的子集组成,2007年9月,湖北大学数计学院计科系,造表法 造表法中DFA A的输入字母表 、开始状态q0和终态集F的确定都与子集法的构造方法一致。 状态集Q与映射函数t则是随着造表的过程而动态生成。 首先求出开始状态q0在接受各输入字母后状态变迁的结果，将其填入表中。然后把得到的结果作为新的状态，再求其接受各输入字母后状态变迁的结果，填入表中，如此过程不断重复，直到最后无新结果（状态）出现为止，此时造表结束。,2007年9月,湖北大学数计学院计科系,定义1、集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为： 1）若sI，则s-closure（I）； 2）若sI，则从s出发经过任意条弧能够到达的任何 状态都属于-closure（I）。 状态集-closure（I）称为I的-闭包,我们可以通过一例子来说明状态子集的-闭包的构造方法, NDFA的确定化,2007年9月,湖北大学数计学院计科系,例： 如图所示的状态图： 令I=1， 求-closure（I）=？,根据定义： -closure（I）=1，3,2007年9月,湖北大学数计学院计科系,我们同样可以通过一例子来说明上述定义,仍采用前面给定的状态图为例,- J是从状态子集I中的每个状态出发,经过标记为a的弧而 达到的状态集合.,-Ia是状态子集,其元素为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确定化（即可构造出状态 的转换矩阵）,2007年9月,湖北大学数计学院计科系,例：有NFA M,a,I=-closure(1)=1,4 Ia=-closure(1,a)(4,a) = -closure(2,3） = -closure (2,3) =2,3 Ib= -closure(1,b)(4,b) = -closure(） = Ic= -closure(1,c)(4,c) = I=2,3, Ia=2,Ib=4,Ic=3,4,2007年9月,湖北大学数计学院计科系,I Ia Ib Ic,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,2007年9月,湖北大学数计学院计科系,将求得的状态转换矩阵重新编号 DFA M状态转换矩阵：,2007年9月,湖北大学数计学院计科系,DFA M的状态图：,0,1,4,2,3,start,1,4,2,3,4,2,a,c,a,b,b,c,3,4,2007年9月,湖北大学数计学院计科系, 消除不可达状态,在自动机中，从开始状态出发没有任何一条路径能达到的状态称为不可达状态。,注：在使用子集法对NDFA进行确定化的过程中，常会产生一些不可达状态，需要在最后将其消除。,2007年9月,湖北大学数计学院计科系, DFA的化简,“对于任一个DFA，存在一个唯一的状态最少的等价的DFA” 一个有穷自动机是化简的 它没有多余状态并且它的状态 中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态 而转换成一个最小的与之等价的有穷自动机。,2007年9月,湖北大学数计学院计科系,2007年9月,湖北大学数计学院计科系,1)一致性条件：状态s和t必须同时为可接受状态或 不接受状态. 2)蔓延性条件：对于所有输入符号,状态s和t必须 转换到等价的状态里.,对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同 的后继，则称s，t是等价的。 （任何有后继的状态和任何无后继的状态一定不等价）,有穷自动机的状态s和t不等价,称这两个状态是可区别的。,2007年9月,湖北大学数计学院计科系,“分割法”：把一个DFA(不含多余状态)的状态分割成一些 不相关的子集，使得任何不同的两个子集状态 都是可区别的，而同一个子集中的任何状态都 是等价的.,2007年9月,湖北大学数计学院计科系,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,区号,区号,2007年9月,湖北大学数计学院计科系,区号,区号,2007年9月,湖北大学数计学院计科系,将区号代替状态号得:,2007年9月,湖北大学数计学院计科系,3.3 正规文法与有穷自动机,（1）正则文法G有穷自动机A,令正规文法G的终结符号集作为有穷自动机A的字母表。 文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符号作为自动机A的开始状态。 在自动机A中增加一个新状态Z作为自动机的终止状态。 对于文法G的形如U:=aV的产生式，在自动机A中构造形如t(U,a)=V的映射。 对于文法G的形如U:=a的产生式，在自动机A中构造形如t(U,a)=Z的映射。,2007年9月,湖北大学数计学院计科系,例:求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA|,2007年9月,湖北大学数计学院计科系,（2）有穷自动机A 正则文法G,自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。 对于自动机的映射t（U,a）=V，构造文法的一条产生式 U:= a V 对于自动机的终止状态Z，在正规文法中增加一条产生式 Z:=,2007年9月,湖北大学数计学院计科系,例:给出如图NFA等价的正规文法G,2007年9月,湖北大学数计学院计科系,3.4 正规表达式与FA,正规表达式和正规集合的递归定义,有字母表, 定义在 上的正规表达式和正规集合递归定义如下: 1. 和都是 上的正规表达式, 它们所表示的正规集合分别为:和; 2. 任何a , a是 上的正规表达式,它所表示的正规集合为:a; 3. 假定U和V都是 上的正则表达式, 它们所表示的正则集合分别记为 L(U)和L(V), 那么U|V, UV和U*也都是 上的正则表达式, 它们所表示 的正则集合分别为L(U) L(V)、 L(U) L(V)和L(U)* 4. 任何