第三章有穷自动机.ppt

《第三章有穷自动机.ppt》由会员分享，可在线阅读，更多相关《第三章有穷自动机.ppt（70页珍藏版）》请在三一文库上搜索。

1、第三章 有穷自动机,本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。,3.1 有穷自动机的形式定义,有穷状态自动机(Finite-state Automata 或简称FA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器正规表达式(Regular Expression)。因此许多简单的程序语言都可由FA所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理论基础。,有穷自动机分为两类： （1）确定的有穷自动机 (Deterministic Finite Automata简称DFA) （2）不确定的有穷自动机(Nondeter

2、ministic Finite Automata简称NFA) 。,3.1.1 确定有穷自动机的形式定义 一个DFA M(K，f，S，Z)，其中 ()K是一个有限状态集合。 ()是一个字母表，它的每个元素称为一个输入字符。 ()SK，S 称为初始状态,唯一。 ()ZK， Z称为终态集合, 终态也称可接受状态或结束状态。 ()f是转换函数，是一个从K到K的单值映射。f(ki，a)kj（ki,kjK,a）kj称为ki的一个后继状态。,确定性的体现：初始状态唯一； 转换函数为单值映射。 例： 设DFA M=(S,U,V,Q，a,b，f，S，Q)其中 f(S,a)U， f(S,b)V f(U,a)Q，

3、f(U,b)V f(V,a)U， f(V,b)Q f(Q,a)Q，f(Q,b)Q 因为（1）初始状态唯一是S， （2）每个转换函数均为单值映射。 所以该FA为确定有穷自动机。,3.1.2 状态转换表 DFA的映射关系可以由一个矩阵表示，矩阵的行标表示状态，列标表示输入字符，矩阵元素表示f(s,a)的值，这个矩阵称为状态转换表。 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,3.1.3 状态转换图 图中标有的为开始状态，标有双圈的状态为终止状态。 若f(Ki,a)=Kj，则从状态结点Ki到状态Kj画标记为a的弧。,

4、3.1.4 自动机的等价性 为了讨论自动机的等价性，先对DFA中的映射进行扩充。 扩充的转换函数f 设QK，函数f(Q, )=Q，即如果输入字符是空串，则仍停留在原来的状态上。 对QK,T,t1*,f(Q,Tt1)=f(f(Q,T), t1)该定义是一个递归定义，说明当自动机处在状态Q且面临某个输入串Tt1时，则先应用函数 f(Q,T)=P，然后应用函数f(P,t1)。,DFA的确定性表现在转换函数f： KK是一个单值函数，即对任何状态kK和输入符号a，f(k,a)唯一地确定了下一个状态，从状态转换图来看，若字母表含有n个输入字符，那么任何一个状态结点最多有n条弧射出，且每条弧以一个不同的输入

5、字符标记。,自动机接受字符串x 如果对于某一自动机M=(K,f,S,Z)，x*，有f(S,x)=P，且PZ，则x为该自动机M所接受（识别），即自动机从开始状态开始，在读完全部输入串以后，自动机恰恰到达终止状态，则该输入串能被该自动机所接受。,例：DFA M=(S,A,B,C,0,1,S,S)，且定义为(S,0)=B，(S,1)=A，(A,0)=C，(A,1)=S，(B,0)=S， (B,1)=C，(C,0)=A，(C,1)=B 状态图表示，矩阵表示：,自动机处理字符串110101和11101的轨迹 (S,110101)= (S,1),10101)= (A,10101)= (A,1),0101)

6、= (S,0101)= (S,0),101)= (B,101)= (B,1),01)= (C,01)= (C,0),1)= (A,1)= S(接受) (S,11101)= (S,1),1101)= (A,1101)= (A,1),101)= (S,101)= (S,1),01)= (A,01)= (A,0),1)= (C,1)= B(拒绝),所有为自动机M所能接受的串组成一个集合，称这个集合为自动机M所能接受的语言，用L(M)表示： L(M)= t | f(S,t)Z，t* 对于任何两个有穷自动机M和M，如果L(M)=L(M)，则称M与M是等价的。,3.1.5 非确定有穷自动机 NFA定义 一

7、个不确定的有穷自动机NFA M是一个五元组： M=(K, ,f,S,Z) 一个含有m个状态和n个输入字符的NFA可表示为一张状态转换图，该图含有m个状态结，每个结可射出若干条 箭弧与别的结点相连接，每条弧用*中的一个字（不一定要不同的字，且可以为空字）作标记（称输入字），整个图至少含有一个初态结以及若干个终态结。,NFA与DFA的区别 NFA有一个开始状态集，而DFA只有一个开始状态。 NFA的映射是QQ的子集，是一个多值映射，而DFA的映射是QQ，是一个单值映射。 DFA是NFA的特例，对于每个NFA M，存在一个DFA M，使得L(M)=L(M)。,对于*中的任何一个串t，如果存在一条从某

8、一初态结到某一终态结的道路，且这条道路上的所有弧的标记依序连接成的串等于t，则称t可为NFA M所识别（读出或接受）。 若M的某些结既是初态结，又是终态结，或者存在一条从某个初态结到某个终态结的道路，则空字可为M所接受。,例： NFA M=(0,1,2,3,4,a,b,f,0,2,4) f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4 可用状态图或矩阵表示：,3.2.1 确定化造表法 造表法是一种简单而有效的确定化方法。 定义：设NFA M=(Q, , t, Q0, F)，假定I是M中状态集的

9、一个子集，定义_closure(I)如下： 若qI，则q_closure(I)； 若q_closure(I)，q是由q出发经多条弧到达的状态，则q_closure(I)。,3.2 NFA到DFA的转换,定义：假定I是NFA M中状态集的一个子集，a，定义 Ia=_closure(J) 其中J是所有那些可从子集I中的任一状态出发，经过一条a连线(跳过a连线前的连线)而到达的状态(结)的全体。 造表法的具体步骤： 假定给定的NFA M中仅含两个符号a，b。可用如下方法将M确定化：采用造表的方式，该表的每一行有三列(若中含有n个符号，则该表有n+1列)，第一列记为I，第二、三列分别记为Ia ,Ib

10、。,置该表的第一行第一列为_closure(Q0)，即一列包含M初态集Q0 的_闭包。然后计算它的Ia 和Ib,分别填入第二、三列上，一般，若某一行的第一列上的I已确定，便可根据前述定义求出这一行的第二、第三列上的Ia 和Ib。 检查Ia 和Ib，看它们是否已在表的第一列中出现，把未曾出现者之一填入下一空行的第一列上，再计算该行的第二、第三列上的Ia 和Ib。, 重复第二步，直至表中所有第二、第三列上的元素全部再第一列出现为止。 因为M中的状态(子集)的个数是有限的，所以上述三步必定在有限步骤内终止。 将由上述过程得到的最终形式的表看作一个状态转换表，即把其中第一列中的元素作为状态，把Ia ,

11、Ib分别看作是输入符号a，b，把其余信息看作是状态转换函数之值。这个表唯一地刻画了一个确定的有穷状态自动机M，其初态是该表第一行第一列的元素，其终态是该表中所有那些含有原终态的元素。可以证明，这个DFA M和NFA M是等价的。,例：有一NFA M，用造表法使其确定化。,3.2.2 确定的有穷自动机的化简 所谓一个确定的有穷自动机M的化简是指： 寻找一个状态数比M少的DFA M， 使得L(M)=L(M)，可通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 消除多余状态 多余状态是指从该自动机的开始状态出发，任何输入串也不能到达的状态。,A,B,C,3.2.3 合并等价状态

12、 等价状态 若s和t是M的两个不同状态，称s和t等价：如果从状态s出发能读出某个字而停于终态，同样从t 出发也能读出同一个字而停于终态；反之若从t 出发能读出某个字而停于终态，则从s出发也能读出同一个字而停于终态。 如果DFA M的两个状态s和t不等价，则称这两个状态是可区别的。,DFA中，状态s和t等价的条件是： 一致性条件：状态s和t 必须同时为可接受状态(终态)或不可接受状态(非终态)。 蔓延性条件：对于所有输入符号，状态s和t 必须转换到等价的状态里。 分割法合并等价状态 一个DFA M的状态化简过程就是把M的状态集划分成一些不相交的子集，使得任何不同的两子集的状态都是可区分的，而同一

13、子集的任何两个状态都是等价的。最后，从每个子集选出一个代表(代表该子集)，同时消去其它等价状态。,对M的状态集S进行划分的步骤： 把S的终态与非终态分开，分成两个子集，形成基本划分，属于这两个不同子集的状态是可区别的。 假定某个时候已含m个子集，记=I(1) , I(2) , ,I(m) 且属于不同子集的状态是可区别的，再检查中的每个I能否进一步划分，对于某个I(i) ，令I(i) =S1,S2,Sk，若存在一个输入字符使得move(I(i) ,a)不包含在现行的某一子集I(i)中，则将I(i)一分为二。,例：将图示的DFA M最小化。,1、将M状态分为两个子集： P0=(1,2,3,4,5,

14、6,7) 2、1,2,3,4读入a后划为： P1=(1,2,3,4,5,6,7) 3、进一步划分： P2=(1,2,3,4,5,6,7) 4、考察5,6,7,将P2划分为： P3=(1,2,3,4,5,6,7) P3不可再划分，从而1与2，6与7等价。,3.2.4 从化简后的DFA到程序表示 识别标识符的DFA（见图 (a)）需改为图 (b)所示状态，其中，l代表字母，d代表数字。,图(a),图(b),如果赋予状态q0、q1与q2一定的操作，则可得识别单词标识符的程序流程图(见下图)。,3.3 正规文法与有穷自动机 正规文法与有穷自动机FA有着特殊的关系。可以证明：对任何正规文法G，可以构造一

15、个FA，它能而且只能识别语言L(G)；反过来，对任何FA，可以构造一个相应的正规文法G，它能生成由该FA所识别的语言。,2.3.1 从正规文法到FA 设正规文法G有形如UaV(aVT, VVN或V=)的产生式。由正规文法G可以直接构造一个有穷自动机A(简称自动机A)，使L(A)=L(G)。构造步骤如下： 令正规文法G的终结符号集作为有穷自动机A的字母表； 文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符作为自动机A的开始状态；, 在自动机A中增加一个新状态z作为自动机的终止状态； 对于文法G的形如UaV(aVT或a=,VVN)的产生式，在自动机A中构造形如t(U, a)=V

16、的映射； 对文法G的形如Ua(aVT)的产生式，在自动机A中构造形如t(U,a)=z的映射。,2.3.2 从FA到正规文法 从自动机也可直接构造其正规文法。构造步骤如下： 自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。, 对于自动机的映射t(U, a)=V（其中，U、V为自动机的状态标记；a为输入符号），构造文法的一条产生式 UaV U、V为文法的非终结符，a为终结符。 对于自动机的终止状态Z，在正规文法中增加一条产生式 Z,3.4 正规表达式与FA,正规式也称正规则式、正规表达式，与

17、正规文法的功能一样，正规式也可用以描述程序设计语言的单词符号。 3.4.1 正规表达式的操作符 连接 假定有两个正规表达式e1和e2，它们分别产生语言L1和L2，于是定义正规表达式的连接操作为 e1e2=x y|xL1，y L2 其中可省略,选择 可用|或+表示，定义为 e1|e2=x |xL1或xL2 重复 用*表示，表示*中的表达式的0次到若干次的自重复连接，即 e*=x| xL1*,例： 正规表达式110由数字1，1，0连接在一起组成，且表示的语言为L=110 表达式0|1所表示的语言为L=0，1 表达式1*所表示的语言为L=1i|i=0，1，2. 例：用正则表达式表示 标识符=字母(字

18、母|数字)* 实数=(e|+|-)(数字* .数字 数字*),3.4.2 正规表达式的定义 所有正规表达式都可以由下列规则构造出来： 是一个表示空集的正规表达式 是一个正规表达式，它所表示的语言仅包含一个空符号串，即 a是一个正规表达式， aVT它所表示的语言（它所表示的正规集）是单个符号a所组成，即a,如果e1和e2是正规表达式，其表示的语言分别为L1和L2， (e1 )|(e2)是一个表示语言L1L2的正规表达式 (e1 )(e2)是一个表示语言L1L2的正规表达式 (e1 )*是一个表示语言L1*的正规表达式 正规表达式中操作符的优先级顺序为 *，连接，|,例： 正规表达式a*b*表示的

19、正规集是 ambn|m0,n 0 正规表达式(ab)*表示的正规集是 (ab)m|m0 正规表达式(a|b)*表示的正规集是 x|xa,b* 表达式(aa|ab|ba|bb)* 表示在VT=a,b上的所有偶长度的串,3.4.3 正规表达式的等价性 如果两个正规表达式表示相同的语言，则这两个正规表达式相等或等价，故有00*=000*|0 3.4.4 正规表达式的性质 r|s=s|r 或满足交换律 r|(s|t)=(r|s)|t 或满足结合律 (rs)t= r(st) 连接满足结合律 r(s|t)=rs|rt (s|t)r=sr|tr 分配律 r=r，r =r 是连接的恒等元素,例：程序设计语言中

20、的单词都能用正规式来定义，如： =字母,数字上的正规式e1=字母(字母|数字)*表示的是所有标识符的集合 正规式e=dd*定义了无符号整数 令=d,.,e,+,-， 则上的正规式 (d*.dd*| dd*)(e(+|-| )dd*| )表示的是无符号数。,3.4.5 正规文法与正规式 一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法。 正规式转换成正规文法 将上的一个正规式转换成文法G=(VN,VT,P,S)，令其中的VT= ，确定产生式和VN的元素用如下方法：,对任何正规式r，选择一个非

21、终结符S，生成产生式Sr，并将S定为G的识别符号。 若x和y都是正规式，对形如Axy的产生式，重写为 AxB，By两产生式，其中B是新选择的非终结符，即B VN 。 对已转换的文法中的形如Ax*y的产生式，重写为AxA,Ay 对形如Ax|y的产生式重写为Ax，Ay 不断利用上述规则作变换，直到每个产生式最多含有一个VN 为止。,例：将R=a(a|d)*转换成相应的正规文法。 令S是识别符号，首先形成Sa(a|d)*， 下一步，SaA, A (a|d)*，重写为： A(a|d)A，A 进而转变为： SaA，AaA，A dA，A,正规文法转换成正规式 上述过程的逆过程，最后只剩下一个开始符号定义的

22、产生式，并且该产生式的右部不含非终结符，转换规则：,例：文法GS：SaA，Sa，AaA，AdA，Aa，Ad S=aA|a，A=aA|dA|a|d=(a|d)A|(a|d) A=(a|d)*(a|d) S=a(a|d)*(a|d)|a=a(a|d)*(a|d)| )= a (a|d)* 练习：有文法GS：SaS，SaB，BbC，CaC，Ca,3.4.6 正规式和有穷自动机的等价性 正规表达式与有穷自动机等价，是指若给定一正则表达式，也即相应地给定了正则集合L(e)，那么就可构造NFA M，并有L(M)= L(e)；反之，若给定一个DFA M，M接受的语言为L(M)，则必然存在一正则表达式e，且L

23、(e)=L(M)。 正规表达式和FA是定义语言（符号串集）的两种不同形式。同一个语言，既可用FA描述，也可用正规表达式描述。,3.4.7 正规表达式到NFA的转换 先构造一个NFA M的一个广义转换图，其中，只有S与Z两个状态，S是开始状态，Z是终止状态，弧上是正规表达式e。然后，按照下图所示的替换规则对正规表达式e逐步进行分解，直到转换图中所有的弧上都是S中的单个符号或e为止。,替换成,替换成,替换成,例：有=a,b上的正规式R=(a|b)*abb，构造NFA M使L(M)=L(e)。 练习：构造与=a,b上的正规式(a|b)*(aa|bb)(a|b)*等价的自动机。,3.4.8 NFA到正

24、规表达式的转换 一个输入字母表为的NFA M，可构造正规表达式e，使L(e)=L(M)。具体操作如下： 首先对NFA M进行拓广，在M的状态转换图中，设置一个唯一的开始状态S和唯一的终止状态Z，并允许状态转换图中弧上可以为正规表达式。 然后从开始状态S到原来所有的开始状态连接弧，再从原来所有的终止状态到Z状态也连接弧。修改后构成了一个新的NFA，它只有一个初态结点S和一个终态结点Z，这个新的NFA M显然和原NFA M等价。,接着，利用下图所示的替换规则，逐步消去M中属于M的所有结点和有关连线，直到状态转换图中只剩下状态S和Z为止(这个过程称为消结)。在消结过程中，用相应的正规表达式标记连线。

25、,替换成,替换成,替换成,例：NFA M=(0,1,2,3,4,a,b,f,0,2,4),状态图如下，构造正规式R使L(R)=L(M)。,3.5 DFA在计算机中的表示,矩阵表示法 设M是一个二维数组，若t(qi, qj)=qk，则令Mi ,j=k，其中i,k=0,1,2, n；j=1, 2,m。 表结构 DFA的映射t:QQ在计算机中可表示成一种表结构。在这个表结构中，每一个状态对应一个表，表中包括该状态的状态名、从该状态发出的弧数、每条弧上的标记以及弧达到的状态所在表的首地址。,DFA在计算机中的表结构,程序表示法 我们也可以用程序来表示DFA。 例：C语言的注释/*/，其有穷自动机,St

26、ate 1 if the next characterr is “/” then advance the input; State 2 if the next character is “*” then advance the input; State 3 done:=false; while not done do while the next input character is not “*”do advance the input; end while; advance the input; State 4,while the next input character is “*” d

27、o advance the input; end while; if the next input character is “/” then done:=true ; end if; advance the input; end while; accept; State 5 else other processing end if else other processing end if State:=1; Start,while state=1,2,3 or 4 do case state of 1:case input character of “/”:advance the input

28、 state:=2; else state:=Error or Other end case 2:case input character of “*”:advance the input; state:=3; else state=. Error or Other end case,3:case input character of “*”:advance the input; state:=4; else advance the inputand stay in State 3 end case 4:case input character of “/”:advance the input

29、; state:=5; “*”:advance the input;and stay in State 4 else advance the input; state:=3; end case end case end while if state=5 then accept else error,本章小结,1、自动机是一种能进行运算并能实现自我控制的装置。它是描述符号串处理的强有力的工具，是研究扫描器的理论基础。有穷自动机(FA)分为确定有穷自动机(DFA)和非确定有穷自动机(NFA)。 2、DFA=(Q，t，q0，F)，Q是状态集，是输入字母表，t：QQ，q0Q是开始状态，FQ是终止状态集

30、。,3、NFA=(Q，t，Q0，F)，t：QQ的子集，Q0Q是开始状态集。 4、对NFA可采用子集法和造表法进行确定化，将其转化为等价的DFA。对 DFA则可进行最小化(化简)，对DFA化简的基本思想是将状态集分解成若干个互不相交的子集，使每个子集中的状态都是等价的，而不同子集的状态是可区分的。,本章小结,本章小结,5、正规文法与FA有着特殊的关系。从正规文法可直接构造其自动机，反之，由自动机也可直接构造其正规文法。 6、正规表达式与FA也有着特殊的关系。对于字母表上的任意一个正规表达式e，一定可以构造一个NFA M，使L(M)=L(e)。反之，对于一个具有输入字母表的NFA M，在上也可构造一个正规表达式e，使L(e)=L(M)。,本章小结,7、正规语言可用正规文法描述，也可用正规表达式描述。 8、DFA在计算机中有三种表示，一种是矩阵表示，一种是表结构，还有一种是程序表示。,THE END,