第三章有穷自动机

第三章有穷自动机3.1概述——有穷自动机的意义有穷状态自动机(Finite-stateAutomataFSA)或简称FA是具有离散的输入\输出系统的数学模型。系统内部具有有穷个状态，系统的状态概括了对过去输入状况的处理信息，系统只需根据当前所处的状态和面临的输入就可以决定系统的后继行为，系统处理了当前的输入后，系统的内部状态也将发生变化。电梯控制装置、文本编辑程序、编译技术中的词法分析程序，计算机以及人脑都是有穷状态系统。

1-91,3,5,7,93.1概述——有穷自动机的模型104397TAS1,3,5,7,9输入带有穷控制器读头0-93.2有穷自动机的形式定义

定义3.1

一个确定有穷自动机DFSA是一个五元组M=(Q,,t,q0,F)其中，Q：是非空有穷状态集,其中的每个元素称为一个状态；：是有穷输入字母表，它的每一个元素称为一个输入符号；t：是一个单值映射QQ，也称状态转换函数，t(q,x)=q意指：当现行状态为q，面临的输入符号为x时，将转到下一状态q，q称为q的一个后继状态；q0Q称之为开始状态；FQ称为终止状态集，至少由一个终止状态组成。3.2.1状态转换表（矩阵）

DFA转换矩阵:

该矩阵行表示状态集；列表示输入字母表；矩阵元素表示t（q,a）的值。即某行状态面临某列输入字符所唯一转向的下一个状态。该矩阵称为状态转换矩阵

3.2.1状态转换表（矩阵）例3.1有穷自动机

A=(Q,,t,q0,F)其中，Q={S,A,B,G,H}，={+，-，·，d}，S是开始状态，终止状态集F={B,H}，映射t:QQ由下表所示的状态转换表给出。

符号状态+-·d

SAAGB

AGB

HB

GH

H3.2.2状态转换图(1)一个DFA也可表示成一张状态转换图。DFA状态：用圆圈节点表示；初始状态节点：用“右向双(单)箭头”表示；终止状态节点：用“双圈”表示；状态变迁：用单向弧线表示，上面必须标记激励变迁的符号。3.2.2状态转换图例3.2有穷自动机A(记为DFSAA)，A=(Q,,t,q0,F)其中，Q={q0,q1,q2,q3}，={a,b}，q0是开始状态，终止状态集F={q0}，映射t:QQ由下图所示的状态转换图给出。

在图中，状态q0用双圆圈标记，表明它是终止状态；同时，用一个箭头标记，表明它是开始状态。

3.2.3构形和移动（1）对于一个给定的输入串,假定一个DFSA已经完成了若干次移动,为了预测它的进一步行为,只需要知道”当前状态”和”尚待扫描的输入串”,这两类信息对于在某一次的特定应用中,位于某个特定时刻的DFSA提供了一种完整的描述,这种描述就称为构形。3.2.3构形和移动（2）构形(q0，ω)称为初始构形，其中q0是初始状态，ω是由该自动机可接收或拒绝的任何输入串。构形(q,)称为终止构形，其中是空串，qF(终态集)。自动机的移动(记为├)是从一种构形到另一种构形的转换。DFSA的工作过程就是一系列的移动过程。记号├+称为├的传递闭包；├*称为├的自反闭包。├*表示“0次或多次移动”；├+表示“一次或多次移动”。

3.2.3构形和移动（3）DFSAM所识别的语言L（M）可表示为：L（M）={ω*︱（q0,ω)├*(q,)＆qF}自动机接受(识别)字符串1）自动机所接收字符

如果对某一自动机M=（Q,,t,q0,F）x∈,

有t（q0,x）=P,且P∈F

，则称字符x被自动机所接收。2）自动机所接收输入串自动机从开始状态读完全部输入串后，自动机恰好到达终止状态，则称输入串被自动机所接收。自动机接受(收)字符串3）自动机接收语言

自动机M所能接收的串组成一个集合，则称该集合为自动机M所能接收（识别）的语言。用L（M）表示：

L（M）＝{ω∣t(q0,ω)∈F,ω∈*

}3.2.4自动机的等价性定义3.2M和M是等价的，当且仅当对每一个串x，M接收x当且仅当M接收x。定义3.3如果M仅通过重新标记它的状态就能转换称M,则M和M称为同构的(Isomorphic)。FSA的一个基本定理是：对每一个自动机M，存在一个等价的具有最少状态个数的自动机M，而且对于每一个其状态个数与M相同且等价于M的自动机M″,必是与M同构的。换句话说，M在结构上是唯一的。3.2.5非确定有穷状态自动机定义3.4

一个非确定有穷自动机NDFSA是一个五元组

NDFSA=(Q,,t,q0,F)其中，Q是一个非空有穷状态集，是一个非空有穷输入字母集，映射t为QQ的子集(即t是一个多值映射)，Q0Q是开始状态集，FQ是终止状态集。

同样的，NDFSA也可以用状态转换表和状态转换图表示。

3.2.5非有穷状态自动机

非确定有穷自动机与确定有穷自动机的主要区别有三：1．NDFSA有一个开始状态集，而DFSA只有一个开始状态。2．NDFSA的映射是QQ的子集，是一个多值映射，而DFSA的映射是QQ，是一个单值映射。3．NDFSA在没有扫描任何输入符号的情况下，也可以进行移动，这种移动称为空移。我们用表示法：

t(q,)={某些状态的集合}将这种情况包括在状态转换函数中。注意，甚至当输入串已经完全扫描完之后还可能需要空移。3.3NDFSA到DFSA的转换

3.3.1NFA的确定化

NFA确定化的定义

NFA的确定化是指对任意给定的NFA都能相应地构造一DFA，使它们接受相同的语言。NDFSA到DFSA的转换NFA确定化为DFA的方法——子集法

对于一个NFA，由于状态转换函数t是一个多值函数，因此总存在一些状态q，对于它们有t(q,a)={q1,q2,q3,…qn},它们是NFA状态集合的一个子集，为了NFA转化为DFA，把状态集合{q1,q2,q3,…qn}看作一个状态A，也就是说让DFA的每一个状态代表NFA状态集合的某个子集，这个DFA使用它的状态去记录在NFA读入输入符号之后可能到达的所有状态的集合，这样就可以把NFA转化为DFA了。这种构造方法称为子集法。NDFSA到DFSA的转换

利用构造-closure的方法将NFA确定化为DFA定义3.5：设NDFSAM=(Q,∪{},t,Q0,F)，假定I是M中状态集的一个子集，定义-closure(I)如下：①若qI，则q–closure(I);②若q-closure(I)，q是由q出发经多条弧所到达的状态，则q

-closure(I)。定义3.6假定I是NDFSAM中状态集的一个子集，a，定义

Ia=-closure(J)其中J是所有那些可从子集I中的任一状态出发，经过一条a连线(跳过a连线前的ε连线)而到达的状态(结)的全体。NDFSA到DFSA的转换

NFAN=(Q,∑,T,S,Z)DFAM=(Q′,∑,T′,S′,Z′)(1)首先将从NFAN的初态S出发经过任意条ε弧所能到达的状态组成的集合作为确定化后的DFAM

的初态S′。(2)从S′出发，经过对任意输入符号a∈∑的状态转移所能到达的状态（包括读入输入符号a之后所有可能的ε转移所能到达的状态）所组成的集合作为M的新状态。NDFSA到DFSA的转换（3）如此重复，直到不在有新的状态出现为止。（4）在所产生的状态中，含有原NFA终态的子集作DFA的终态。

消除不可达状态

在自动机中，从开始状态没有任何一条路径能达到的状态称为不可达状态。由于不可达状态事实上是无用的，因此也称多余的状态，可以删除它们。下面给出识别可达状态的算法。当该算法终止时，每一个未标记的状态就是不可达状态。识别DFSA中可达状态的算法。①标记开始状态S；②给定任意标记过的状态P，如果对某个输入符号存在从状态P到Q的转换，则标记每一个这样的状态Q；

重复步骤②，直到不再有可标记的状态为止。

3.3.2DFA的化简（最小化）DFA的化简所谓DFA的化简是指寻找一个状态数比M少的确定的有穷自动机M，使得L(M)=L(M)。化简后的DFAM′应满足两个条件:(1)没有多余状态;（不可达状态）

(2)它的状态集合中,没有两个状态是相互等价的。定义3.7假定q1和q2是M中的两个不同状态，称q1和q2是等价的当且仅当如果从状态q1出发能扫描任意串w而停止于终态，那么从状态q2出发也能扫描同一个串w而停止于终态；定义3.8如果两个状态q1和q2不等价，则称这两个状态是可区分的。3.3.2DFA的化简（最小化）化简方法

DFAM最小化的方法是把M的状态集合Q划分成一些不相交的子集，使得每个子集中的任何两个状态是等价的，而任何两个属于不同子集的状态都是可区分的；然后在每个子集中任取一个状态作为代表，而删去子集中其余状态，并把射向其余状态的弧都改为射向作为“代表”的状态中。3.3.2DFA的化简（最小化）化简的具体步骤：

（1）将DFAM的状态集Q分成两个子集：终态集F和非终态集Q-F，形成初始分划П。（2）对П建立新的分划ПNew

，对П的每个状态子集G，进行如下变换：①把G分划成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于П的同一子集。②用G分划出的所有新子集替换G，形成新的分划ПNew

。3.3.2DFA的化简（最小化）（3）如果ПNew＝П，则执行第（4）步；否则令П=ПNew

，重复第（2）步。（4）分划结束后，对分划中的每个状态子集，选出一个状态作代表，而删去其他一切等价的状态，并把射向其他状态的箭弧改为射向这个作为代表的状态。这样得到的DFAM′是与DFAM等价的一切DFA中状态数最少的DFA。举例.从化简后的DFA到程序表示

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

如果赋予状态q0、q1与q2一定的操作，则可得识别单词标识符的程序流程图(见下图)。

3.4正规文法与有穷自动机

正规文法与有穷自动机FA有着特殊的关系。可以证明：对任何正规文法G，可以构造一个FSA，它能而且只能识别语言L(G);反过来，对任何FSA，可以构造一个相应的正规文法G，它能生成由该FSA所识别的语言。

从正规文法到FSA

设正规文法G有形如U→aV(aVT,VVN或V=)的产生式。由正规文法G可以直接构造一个有穷自动机A(简称自动机A)，使L(A)=L(G)。构造步骤如下：

①令正规文法G的终结符号集作为有穷自动机A的字母表；②文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符作为自动机A的开始状态；③在自动机A中增加一个新状态z作为自动机的终止状态；④对于文法G的形如U→aV(aVT或a=,VVN)的产生式，在自动机A中构造形如t(U,a)=V的映射；⑤对于文法G的形如U→a(aVT)的产生式，在自动机A中构造形如t(U,a)=z的映射。

3.4.2从FA到正规文法

从正规文法可直接构造其自动机，反之，由自动机也可直接构造其正规文法。构造步骤如下：①自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。②对于自动机的映射t(U,a)=V（其中，U、V为自动机的状态标记；a为输入符号），构造文法的一条产生式U→aVU、V为文法的非终结符，a为终结符。③对于自动机的终止状态Z，在正规文法中增加一条产生式Z→

3.5正规表达式与FA

3.5.1正规表达式的定义正规语言又称正规集。正规表达式简称正规式是正规文法更紧凑的表示方法,是用来描述正规语言的。以下是正规表达式的一些相关定义。3.5.1正规表达式的定义定义3.9

字母表上的正规表达式和正规集递归定义如下：①a，a是上的一个正规表达式，它所表示的正规集为{a}。②空串是上的一个正规表达式，它所表示的正规集为{}。③空集是上的一个正规表达式，它所表示的正规集为。④设e1与e2都是上的正规表达式，它们所表示的正规集分别为

L(e1)与L(e2)，则i)e1e2也是正规表达式，它所表示的正规集为

L(e1e2)=L(e1)∪L(e2)；ii)e1e2也是正规表达式，它所表示的正规集为

L(e1e2)=L(e1)L(e2)；iii)(e1)*也是正规表达式，它所表示的正规表达式为

L((e1)*)=(L(e1))*。举例：3.5.1正规表达式的定义例：设有字母表∑={a,b}，根据正规式与正规集的定义，有以下的正规式和正规集正规式正规集

a{a}a∣b{a,b}ab{ab}(a∣b)(a∣b){aa,ab,ba,bb}a*{ε,a,aa,aaa,…,任意个a的串}（a∣b）*

{ε，a,b,aa,ab,ba,bb,…所有a,b组成的串}(a︱b)

*(aa︱bb)(a︱b)

*∑*上所有含两个连续的a或两个连续的b组成的串3.5.1正规表达式的定义例:Σ={d,·,e,+，-}则Σ上的正规式

d*(·dd*∣ε)(e(+∣-∣ε)dd*∣ε)表示的是实数。其中d为0～9中的数字。比如：2，12.59,3.6e2和471.88e-1等等都是该正规集所表示集合中的元素。例:Σ={字母，数字}上的正规式e1=字母（字母︱数字）*表示的是所有标识符的集合，或者用l代表字母，d代表数字，则Σ={l，d},则e1=l(l︱d)*,e2=dd*则定义了无符号整数。3.5.1正规表达式的定义例:设Σ={a,b,c},则aa*bb*cc*是Σ上的一个正规式,它所表示的正规集L={abc,aabc,abbc,abcc,aaabc,...}={ambncl∣m,n,l≥1}例:设程序设计语言字母表是键盘字符集合,则程序设计语言部分单词符号可用如下正规式定义:

关键字if|else|while|do

标识符l(l|d)*l代表字母,d代表数字整常数dd*

关系运算符<|<=|>|>=|<>3.5.1正规表达式的等价性定义3.10

设e1与e2是上的两个正规表达式，若L(e1)=L(e2)，则称e1与e2等价，记为e1=e2，如

a(ba)*=(ba)*a3.5.1正规表达式的运算性质定理3.1设e1、e2和e3都是上的正规表达式，则①e1e2=e2e1(交换律)②(e1e2)e3=e1(e2e3),(e1e2)e3=e1(e2e3)（结合律）③e1(e2e3)=e1e2e1e3,(e1e2)e3=e1e3e2e3

（分配律）④

e1=e1=e1⑤()*=(空集的闭包是空串)⑥e1=e1=

⑦e1*=e1|e1*⑧(e1*)*=e1*

⑨e1|=e1

3.5.2正规表达式的文法描述正规表达式是由下面的CFGGR=（N,,P,R）描述的。其中，N={R，C，L}

={|,(,),*,a,}产生式集合P为：R→R|C(选择) R→CC→CL(连结) C→LL→(R)(括号) L→R*(闭包)L→a(正规语言中的任何符号) L→(空串)

该文法描述了操作符：连结，选择和闭包的优先级以及形成正规表达式的结构规则。运算符的优先级从高到低：闭包、连结、选择正规表达式与FSA的对应性

正规表达式和FSA是定义语言（符号串集）的两种不同形式。同一个语言，既可用FSA描述，也可用正规表达式描述。正规表达式到NDFSA的转换对于字母表上任意一个正规表达式e，一定可以构造一个NDFSA

M，使L(M)=L(e)。先构造一个NDFSAM的一个广义转换图，其中，只有S与Z两个状态，S是开始状态，Z是终止状态，弧上是正规表达式e。然后，按照下图所示的替换规则对正规表达式e逐步进行分解，直到转换图中所有的弧上都是中的单个符号或为止。

正规表达式到NDFSA的转换（1）替换成（2）替换成（3）替换成3.5.5NDFSAM到正规表达式的转换

对于一个具有输入字母表的NDFSA

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

3.5.5NDFSAM到正规表达式的转换（1）替换成（2）替换成（3）替换成正规文法和正规式间的转换正规文法到正规式的转换方法：（1）将正规文法中的每一个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。从文法的规则到正规式方程的变换规则：若A→a,则有A=a。若A→aB∣β,则有A=aB+β。（2）依照求解规则：若x=ax︱β(或x=ax+β)，则解为x=a*β。若x=xa︱β(或x=xa+β),则解为x=βa*。和正规式的分配率、交换率和结合率求关于文法开始符号的正规式方程组的解。这个解就是关于文法开始符号S的一个正规式，显然它表示了由该正规文法所描述的语言。举例.正规文法到正规式的转换设有正规文法G[