第三章有穷自动机

第三章有穷自动机第一页，共七十四页，2022年，8月28日§3.1有穷自动机的形式定义

有穷状态自动机(Finite-stateAutomata或简称FA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器——正规表达式(RegularExpression)。因此许多简单的程序语言都可由FA所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理论基础。

第二页，共七十四页，2022年，8月28日有穷自动机分为两类：（1）确定的有穷自动机(DeterministicFiniteAutomata简称DFA)（2）不确定的有穷自动机(NondeterministicFiniteAutomata简称NFA)。

第三页，共七十四页，2022年，8月28日3.1.1确定有穷自动机的形式定义

一个DFAM＝(K，Σ，f，S，Z)，其中(ａ)K是一个有限状态集合。(ｂ)Σ是一个字母表，它的每个元素称为一个输入字符。(ｃ)S∈K，S称为初始状态,唯一。(ｄ)ZK，Z称为终态集合,终态也称可接受状态或结束状态。(ｅ)f是转换函数，是一个从K×Σ到K的单值映射。f(ki，a)＝kj（ki,kj∈K,a∈Σ）kj称为ki的一个后继状态。第四页，共七十四页，2022年，8月28日确定性的体现：初始状态唯一；转换函数为单值映射。例：设DFAM=({S,U,V,Q}，{a,b}，f，S，｛Q｝)其中

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因为（1）初始状态唯一是S，（2）每个转换函数均为单值映射。所以该FA为确定有穷自动机。

第五页，共七十四页，2022年，8月28日3.1.2状态转换表

DFA的映射关系可以由一个矩阵表示，矩阵的行标表示状态，列标表示输入字符，矩阵元素表示f(s,a)的值，这个矩阵称为状态转换表。

f(S,a)＝U

f(S,b)＝Vf(U,a)＝Q

f(U,b)＝Vf(V,a)＝U

f(V,b)＝Qf(Q,a)＝Q

f(Q,b)＝QabSUVUQVVUQQQQ第六页，共七十四页，2022年，8月28日q1aaabbabbq2q3q03.1.3状态转换图图中标有的为开始状态，标有双圈的状态为终止状态。若f(Ki,a)=Kj，则从状态结点Ki到状态Kj画标记为a的弧。第七页，共七十四页，2022年，8月28日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)。第八页，共七十四页，2022年，8月28日DFA的确定性表现在转换函数f：KK是一个单值函数，即对任何状态kK和输入符号a，f(k,a)唯一地确定了下一个状态，从状态转换图来看，若字母表含有n个输入字符，那么任何一个状态结点最多有n条弧射出，且每条弧以一个不同的输入字符标记。

第九页，共七十四页，2022年，8月28日自动机接受字符串x如果对于某一自动机M=(K,,f,S,Z)，x*，有f(S,x)=P，且PZ，则x为该自动机M所接受（识别），即自动机从开始状态开始，在读完全部输入串以后，自动机恰恰到达终止状态，则该输入串能被该自动机所接受。

第十页，共七十四页，2022年，8月28日例：DFAM=({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状态图表示，矩阵表示：第十一页，共七十四页，2022年，8月28日自动机处理字符串110101和11101的轨迹(S,110101)=((S,1),10101)=(A,10101)=((A,1),0101)=(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(拒绝)第十二页，共七十四页，2022年，8月28日所有为自动机M所能接受的串组成一个集合，称这个集合为自动机M所能接受的语言，用L(M)表示：L(M)={t|f(S,t)Z，t*}对于任何两个有穷自动机M和M’，如果L(M)=L(M’)，则称M与M’是等价的。第十三页，共七十四页，2022年，8月28日3.1.5非确定有穷自动机NFA定义一个不确定的有穷自动机NFAM’是一个五元组：M’=(K,,f,S,Z)一个含有m个状态和n个输入字符的NFA可表示为一张状态转换图，该图含有m个状态结，每个结可射出若干条箭弧与别的结点相连接，每条弧用*中的一个字（不一定要不同的字，且可以为空字）作标记（称输入字），整个图至少含有一个初态结以及若干个终态结。第十四页，共七十四页，2022年，8月28日NFA与DFA的区别NFA有一个开始状态集，而DFA只有一个开始状态。NFA的映射是QQ的子集，是一个多值映射，而DFA的映射是QQ，是一个单值映射。DFA是NFA的特例，对于每个NFAM，存在一个DFAM’，使得L(M)=L(M’)。第十五页，共七十四页，2022年，8月28日对于*中的任何一个串t，如果存在一条从某一初态结到某一终态结的道路，且这条道路上的所有弧的标记依序连接成的串等于t，则称t可为NFAM所识别（读出或接受）。若M的某些结既是初态结，又是终态结，或者存在一条从某个初态结到某个终态结的道路，则空字可为M所接受。

第十六页，共七十四页，2022年，8月28日例：NFAM=({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}可用状态图或矩阵表示：03412aabba,ba,ba,b第十七页，共七十四页，2022年，8月28日§3.2NFA到DFA的转换通过下述步骤可将一个NFA转换成等价的DFA：①寻找并消除空移环路；②消除余下的空移；③确定化。

第十八页，共七十四页，2022年，8月28日3.2.1空移环路的寻找和消除第十九页，共七十四页，2022年，8月28日3.2.2消除空移

下面给出一个消除空移的算法。给定从状态A到B的一个空移(即从状态A到B经由连线的一个转换，换言之，t(A,)={…，B，…})。置t(A,)=，对每个a和Q，如果Qt(B,a)，则将Q加到t(A,a)。如果A是开始状态，则将B也加入开始状态集。如果B是终止状态，则将A也加入终止状态集。

第二十页，共七十四页，2022年，8月28日3.2.3利用状态转换表消除空移

利用FA的状态转换表，可以很容易地消除空移。这种方法的基本步骤是：首先，找出直接经由一个空移到达某个终态的所有状态。每当找到这样一个状态，便将它标记为终态。然后，考虑消除与未被标记为终态的那些状态相关的空移。对表中每一个具有射出ε连线的状态继续按上述方式处理，直到状态转换表不再变动为止。最后从表中删除ε列和没有任何元素的空行，便得到一个不含空移的状态转换表。

第二十一页，共七十四页，2022年，8月28日3.2.4确定化——造表法

造表法是一种简单而有效的确定化方法。定义：设NFAM=(Q,∪{},t,Q0,F)，假定I是M中状态集的一个子集，定义_closure(I)如下：若qI，则q_closure(I)；若q_closure(I)，q是由q出发经多条弧到达的状态，则q_closure(I)。第二十二页，共七十四页，2022年，8月28日定义：假定I是NFAM中状态集的一个子集，a，定义Ia=_closure(J)其中J是所有那些可从子集I中的任一状态出发，经过一条a连线(跳过a连线前的ε连线)而到达的状态(结)的全体。造表法的具体步骤：假定给定的NFAM中仅含两个符号a，b。可用如下方法将M确定化：采用造表的方式，该表的每一行有三列(若中含有n个符号，则该表有n+1列)，第一列记为I，第二、三列分别记为Ia,Ib。

第二十三页，共七十四页，2022年，8月28日①置该表的第一行第一列为_closure(Q0)，即一列包含M初态集Q0的ε_闭包。然后计算它的Ia和Ib,分别填入第二、三列上，一般，若某一行的第一列上的I已确定，便可根据前述定义求出这一行的第二、第三列上的Ia和Ib。②检查Ia和Ib，看它们是否已在表的第一列中出现，把未曾出现者之一填入下一空行的第一列上，再计算该行的第二、第三列上的Ia和Ib。

第二十四页，共七十四页，2022年，8月28日③重复第二步，直至表中所有第二、第三列上的元素全部再第一列出现为止。因为M中的状态(子集)的个数是有限的，所以上述三步必定在有限步骤内终止。④将由上述过程得到的最终形式的表看作一个状态转换表，即把其中第一列中的元素作为状态，把Ia,Ib分别看作是输入符号a，b，把其余信息看作是状态转换函数之值。这个表唯一地刻画了一个确定的有穷状态自动机M，其初态是该表第一行第一列的元素，其终态是该表中所有那些含有原终态的元素。可以证明，这个DFAM和NFAM是等价的。

第二十五页，共七十四页，2022年，8月28日例：有一NFAM，用造表法使其确定化。bbaab01253467891001234bbbbbaaaaa第二十六页，共七十四页，2022年，8月28日3.2.5确定的有穷自动机的化简

所谓一个确定的有穷自动机M的化简是指：寻找一个状态数比M少的DFAM’，使得L(M)=L(M’)，可通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。消除多余状态多余状态是指从该自动机的开始状态出发，任何输入串也不能到达的状态。

第二十七页，共七十四页，2022年，8月28日ABC第二十八页，共七十四页，2022年，8月28日3.2.6合并等价状态

等价状态若s和t是M的两个不同状态，称s和t等价：如果从状态s出发能读出某个字而停于终态，同样从t出发也能读出同一个字而停于终态；反之若从t出发能读出某个字而停于终态，则从s出发也能读出同一个字而停于终态。如果DFAM的两个状态s和t不等价，则称这两个状态是可区别的。

第二十九页，共七十四页，2022年，8月28日DFA中，状态s和t等价的条件是：一致性条件：状态s和t必须同时为可接受状态(终态)或不可接受状态(非终态)。蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。分割法合并等价状态一个DFAM的状态化简过程就是把M的状态集划分成一些不相交的子集，使得任何不同的两子集的状态都是可区分的，而同一子集的任何两个状态都是等价的。最后，从每个子集选出一个代表(代表该子集)，同时消去其它等价状态。第三十页，共七十四页，2022年，8月28日对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)一分为二。第三十一页，共七十四页，2022年，8月28日例：将图示的DFAM最小化。1362457aaaaaaabbbbbbb第三十二页，共七十四页，2022年，8月28日1、将M状态分为两个子集： P0=({1,2,3,4},{5,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等价。第三十三页，共七十四页，2022年，8月28日13645aaabbbbba第三十四页，共七十四页，2022年，8月28日3.2.7从化简后的DFA到程序表示

识别标识符的DFA（见图(a)）需改为图(b)所示状态，其中，l代表字母，d代表数字。

图(a)图(b)第三十五页，共七十四页，2022年，8月28日如果赋予状态q0、q1与q2一定的操作，则可得识别单词标识符的程序流程图(见下图)。

第三十六页，共七十四页，2022年，8月28日§3.3正规文法与有穷自动机正规文法与有穷自动机FA有着特殊的关系。可以证明：对任何正规文法G，可以构造一个FA，它能而且只能识别语言L(G)；反过来，对任何FA，可以构造一个相应的正规文法G，它能生成由该FA所识别的语言。第三十七页，共七十四页，2022年，8月28日2.3.1从正规文法到FA

设正规文法G有形如U→aV(aVT,VVN或V=)的产生式。由正规文法G可以直接构造一个有穷自动机A(简称自动机A)，使L(A)=L(G)。构造步骤如下：①令正规文法G的终结符号集作为有穷自动机A的字母表；②文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符作为自动机A的开始状态；第三十八页，共七十四页，2022年，8月28日③在自动机A中增加一个新状态z作为自动机的终止状态；④对于文法G的形如U→aV(aVT或a=,VVN)的产生式，在自动机A中构造形如t(U,a)=V的映射；⑤对文法G的形如U→a(aVT)的产生式，在自动机A中构造形如t(U,a)=z的映射。第三十九页，共七十四页，2022年，8月28日2.3.2从FA到正规文法从自动机也可直接构造其正规文法。构造步骤如下：①自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。第四十页，共七十四页，2022年，8月28日②对于自动机的映射t(U,a)=V（其中，U、V为自动机的状态标记；a为输入符号），构造文法的一条产生式 U→aVU、V为文法的非终结符，a为终结符。③对于自动机的终止状态Z，在正规文法中增加一条产生式Z→

第四十一页，共七十四页，2022年，8月28日§3.4正规表达式与FA

正规式也称正规则式、正规表达式，与正规文法的功能一样，正规式也可用以描述程序设计语言的单词符号。

正规表达式的操作符连接假定有两个正规表达式e1和e2，它们分别产生语言L1和L2，于是定义正规表达式的连接操作为e1e2={xy|xL1，yL2}其中可省略第四十二页，共七十四页，2022年，8月28日选择可用|或+表示，定义为e1|e2={x|xL1或xL2}重复用*表示，表示*中的表达式的0次到若干次的自重复连接，即e*={x|xL1*}第四十三页，共七十四页，2022年，8月28日例：正规表达式110由数字1，1，0连接在一起组成，且表示的语言为L={110}表达式0|1所表示的语言为L={0，1}表达式1*所表示的语言为L={1i|i=0，1，2...}例：用正则表达式表示

{标识符}=字母(字母|数字)*

{实数}=(e|+|-)(数字*

.数字数字*)第四十四页，共七十四页，2022年，8月28日正规表达式的定义所有正规表达式都可以由下列规则构造出来：①是一个表示空集的正规表达式②是一个正规表达式，它所表示的语言仅包含一个空符号串，即{}③a是一个正规表达式，aVT它所表示的语言（它所表示的正规集）是单个符号a所组成，即{a}第四十五页，共七十四页，2022年，8月28日④如果e1和e2是正规表达式，其表示的语言分别为L1和L2，(e1)|(e2)是一个表示语言L1L2的正规表达式(e1)(e2)是一个表示语言L1L2的正规表达式(e1)*是一个表示语言L1*的正规表达式⑤正规表达式中操作符的优先级顺序为*，连接，|第四十六页，共七十四页，2022年，8月28日例：正规表达式a*b*表示的正规集是 {ambn|m0,n0}正规表达式(ab)*表示的正规集是 {(ab)m|m0}正规表达式(a|b)*表示的正规集是 {x|x{a,b}*}表达式(aa|ab|ba|bb)* 表示在VT={a,b}上的所有偶长度的串第四十七页，共七十四页，2022年，8月28日3.4.3正规表达式的等价性如果两个正规表达式表示相同的语言，则这两个正规表达式相等或等价，故有00*=000*|0正规表达式的性质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 是连接的恒等元素第四十八页，共七十四页，2022年，8月28日例：程序设计语言中的单词都能用正规式来定义，如：={字母,数字}上的正规式e1=字母(字母|数字)*表示的是所有标识符的集合正规式e=dd*定义了无符号整数令={d,.,e,+,-}，则上的正规式 (d*.dd*|dd*)(e(+|-|)dd*|)表示的是无符号数。第四十九页，共七十四页，2022年，8月28日3.4.5正规文法与正规式

一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法。正规式转换成正规文法将上的一个正规式转换成文法G=(VN,VT,P,S)，令其中的VT=，确定产生式和VN的元素用如下方法：第五十页，共七十四页，2022年，8月28日对任何正规式r，选择一个非终结符S，生成产生式Sr，并将S定为G的识别符号。若x和y都是正规式，对形如Axy的产生式，重写为AxB，By两产生式，其中B是新选择的非终结符，即BVN。对已转换的文法中的形如Ax*y的产生式，重写为AxA,Ay对形如Ax|y的产生式重写为Ax，Ay不断利用上述规则作变换，直到每个产生式最多含有一个VN为止。第五十一页，共七十四页，2022年，8月28日例：将R=a(a|d)*转换成相应的正规文法。 令S是识别符号，首先形成Sa(a|d)*，下一步，SaA,A(a|d)*，重写为： A(a|d)A，A 进而转变为：SaA，AaA，AdA，A第五十二页，共七十四页，2022年，8月28日正规文法转换成正规式 上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符，转换规则：第五十三页，共七十四页，2022年，8月28日例：文法G[S]：SaA，Sa，AaA，AdA，Aa，AdS=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)*练习：有文法G[S]：SaS，SaB，BbC，CaC，Ca第五十四页，共七十四页，2022年，8月28日3.4.6正规式和有穷自动机的等价性正规表达式与有穷自动机等价，是指若给定一正则表达式，也即相应地给定了正则集合L(e)，那么就可构造NFAM，并有L(M)=L(e)；反之，若给定一个DFAM，M接受的语言为L(M)，则必然存在一正则表达式e，且L(e)=L(M)。正规表达式和FA是定义语言（符号串集）的两种不同形式。同一个语言，既可用FA描述，也可用正规表达式描述。第五十五页，共七十四页，2022年，8月28日3.4.7正规表达式到NFA的转换先构造一个NFAM的一个广义转换图，其中，只有S与Z两个状态，S是开始状态，Z是终止状态，弧上是正规表达式e。然后，按照下图所示的替换规则对正规表达式e逐步进行分解，直到转换图中所有的弧上都是S中的单个符号或e为止。第五十六页，共七十四页，2022年，8月28日替换成替换成替换成第五十七页，共七十四页，2022年，8月28日例：有={a,b}上的正规式R=(a|b)*abb，构造NFAM使L(M)=L(e)。练习：构造与={a,b}上的正规式(a|b)*(aa|bb)(a|b)*等价的自动机。第五十八页，共七十四页，2022年，8月28日3.4.8NFA到正规表达式的转换一个输入字母表为的NFAM，可构造正规表达式e，使L(e)=L(M)。具体操作如下：①首先对NFAM进行拓广，在M的状态转换图中，设置一个唯一的开始状态S和唯一的终止状态Z，并允许状态转换图中弧上可以为正规表达式。②然后从开始状态S到原来所有的开始状态连接弧，再从原来所有的终止状态到Z状态也连接弧。修改后构成了一个新的NFA，它只有一个初态结点S和一个终态结点Z，这个新的NFAM′显然和原NFAM等价。第五十九页，共七十四页，2022年，8月28日③接着，利用下图所示的替换规则，逐步消去M′中属于M的所有结点和有关连线，直到状态转换图中只剩下状态S和Z为止(这个过程称为消结)。在消结过程中，用相应的正规表达式标记连线。第六十页，共七十四页，2022年，8月28日替换成替换成替换成第六十一页，共七十四页，2022年，8月28日例：NFAM=({0,1,2,3,4},{a,b},f,{0},{2,4}),状态图如下，构造正规式R使L(R)=L(M)。03412aabba,ba,ba,b第六十二页，共七十四页，2022年，8月28日§3.5DFA在计算机中的表示

矩阵表示法设M是一个二维数组，若t(qi,qj)=qk，则令M[i,j]=k，其中i,k=0,1,2,…,n；j=1,2,…,m。表结构DFA的映射t:QQ在计算机中可表示成一种表结构。在这个表结构中，每一个状态对应一个表，表中包括该状态的状态名、从该状态发出的弧数、每条弧上的标记以及弧达到的状态所在表的首地址。第六十三页，共七十四页，2022年，8月28日DFA在计算机中的表结构

第六十四页，共七十四页，2022年，8月28日程序表示法我们也可以用程序来表示DFA。例：C语言的注释/*…*/，其有穷自动机12345/**/*otherother第六十五页，共七十四页，2022年，8月28日{State1}ifthenextcharacterris“/”thenadvancetheinput;{State2}ifthenextcharacteris“*”thenadvancetheinput;{State3}done:=false;whilenotdonedowhilethenextinputcharacterisnot“*”doadvancetheinput;endwhile;advancetheinput;{State4}第六十六页，共七十四页，2022年，8月28日whilethenextinputcharacteris“*”doadvancetheinput;endwhile;ifthenextinputcharacteris“/”thendone:=true;endif;advancetheinput;endwhile;accept;{State5}else{otherprocessing}endifelse{otherprocessing}endifState:=1;{Start}第六十七页，共七十四页，2022年，8月28日whilestate=1,2,3or4docasestateof1:caseinputcharacterof“/”:advancetheinputstate:=2;elsestate:=…{ErrororOther}endcase2:caseinputcharacterof“*”:advancetheinput;state:=3;els