4有限状态自动机

第四讲

有限状态自动机

确定有限自动机

非确定有限自动机

确定与非确定有限自动机的等价性有限状态自动机

带

-转移的非确定有限自动机

有限自动机的一个应用—文本搜索

（确定）有限自动机的最小化

有限状态集

有限输入符号集

转移函数

一个开始状态

一个终态集合q0q1q2q3确定有限自动机

有限自动机的五要素

有限状态集

有限输入符号集

转移函数

一个开始状态

一个终态集合

一个确定有限状态自动机

DFA

(deterministicfiniteautomata)是一个五元组

A=(Q,

,

,q0,F).:Q

Q

q0

Q

F

Q确定有限自动机

确定有限自动机的形式定义

Q={q0,q1,q2,q3}

={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}q0q1q2q3确定有限自动机

转移图表示的DFA

q0q1q2

q301q2q1q3q0q0q3q1q2确定有限自动机

Q={q0,q1,q2,q3}

={0,1

}

(q0,0)=q2,(q0,1)=q1(q1,0)=q3,(q1,1)=q0(q2,0)=q0,(q2,1)=q3(q3,0)=q1,(q3,1)=q2

q0

F={q0,q3}

转移表表示的DFA

q1q2q3q0确定有限自动机

DFA如何接受输入符号串q2q3q0q1确定有限自动机

DFA如何接受输入符号串q2q0q1q3确定有限自动机

DFA如何接受输入符号串q2q3q0q1确定有限自动机

DFA如何接受输入符号串q1q2q3q0确定有限自动机

DFA如何接受输入符号串q1q3q0q2确定有限自动机

DFA如何接受输入符号串q1q0q2q3

确定有限自动机

DFA如何接受输入符号串q1q2q3q0确定有限自动机

DFA如何接受输入符号串q1q3q0q2确定有限自动机

DFA如何接受输入符号串q1q2q3q0

确定有限自动机

DFA如何接受输入符号串q1q2q3q0确定有限自动机

DFA如何接受输入符号串q2q3q0q1确定有限自动机

DFA如何接受输入符号串q2q0q1q3确定有限自动机

DFA如何接受输入符号串q1q3q0q2确定有限自动机

DFA如何接受输入符号串q1q2q3q0确定有限自动机

DFA如何接受输入符号串q2q3q0q1

确定有限自动机

DFA如何接受输入符号串

设一个DFAA=(Q,

,

,q0,F)

:Q

Q

扩充定义

:Q*

Q

对任何q

Q，定义：

1(q

,)=q

2若w=xa,其中x

*,a

,则

(q

,w)=((q

,x)

,a)确定有限自动机

扩展转移函数适合于输入字符串

q0q1q2

q301q2q1q3q0q0q3q1q2

举例

(q0,)

=q0(q0,0)

=(q0,0)

=q2(q0,00)

=(q2,0)

=q0(q0,001)

=(q0,1)

=q1(q0,0010)

=(q1,0)

=q3确定有限自动机

扩展转移函数适合于输入字符串q1q0q3q2

设一个DFAA=(Q,

,

,q0,F)

定义A的语言：

L(A)=

w

w

*

(q0,w)

F

设L是

上的语言，如果存在一个DFAA=(Q,

,

,q0,F)，满足L=L(A)，

则可以证明L

是一个正规语言.确定有限自动机

DFA

的语言

举例

=0,1

上的语言L=w

w中

0

、1

数目的奇偶性相同，则L是一个正规语言.可证L是如下DFA的语言.

证明

留作思考题

(采用互归纳法,

参考Example2.4

和Example1.23)q0q1q2q3确定有限自动机

DFA

的语言(1)(2)非确定有限自动机

非确定有限自动机举例

有限状态集

有限输入符号集

转移函数

一个开始状态

一个终态集合

一个非确定有限状态自动机

NFA

nondeterministicfiniteautomata)是一个五元组

A=(Q,

,

,q0,F).q0

Q

F

Q

与DFA唯一不同之处

:Q

2Q非确定有限自动机

非确定有限自动机的形式定义(1)(2)pq

r0{q}

{q}

{q,r}

1pq

r0{p}{r}

{r}

1{p,q}非确定有限自动机

转移图和转移表表示的NFA

0100111010

非确定有限自动机

NFA如何接受输入符号串

设一个NFAA=(Q,

,

,q0,F)

:Q

2Q

扩充定义

:Q*

2Q

对任何q

Q，定义：

1(q

,)={q}

2若w=xa,其中x

*

,a

,并且假设

(q

,x)={p1,p2,

,pk},则

(q

,w)=

(pi

,a)i=1k非确定有限自动机

扩展转移函数适合于输入字符串

举例

(p

,

)

={p}

(p

,0)

={q}

(p

,01)

={q,r}

(p

,010)

={q}

(p

,0100)

={q}

(p

,01001)={q,r}

pq

r0{q}

{q}

{q,r}

1非确定有限自动机

扩展转移函数适合于输入字符串

设一个NFAA=(Q,

,

,q0,F)

定义A的语言：

L(A)=

w

w

*

(q0,w)

F

设L是

上的语言，如果存在一个NFAA=(Q,

,

,q0,F)，满足L=L(A)，则可以证明L也是一个正规语言.

非确定有限自动机NFA

的语言定理:

L是某个DFA的语言,当且仅当L也是某个NFA的语言.

证明:分两步证明.

(1)设L是某个DFAD的语言,则存在一个

NFAN,满足L(N)=L(D)=L;

(2)设L是某个NFAN的语言,则存在一个

DFAD,满足L(D)=L(N)=L

DFA和NFA的等价性

设L是某个DFAD=(Q,

,

D,q0,F)的语言,则存在一个NFAN,满足L(N)=L(D)=L.

证明:定义N=(Q,

,

N,q0,F),其中

N定义为

对q

Q和a

,

若

D(q,a)=p,则

N(q,a)={p}.

需要证明:对任何w*

,

D(q0,w)=piff

N(q0,w)={p}.

归纳于|w|易证上述命题.DFA和NFA的等价性

从DFA

构造等价的NFA

设L是某个NFAN=(QN,

,

N,q0,FN)的语言,则存在一个DFAD,满足L(D)=L(N)=L.

证明:定义

D=(QD,

,

D,{q0},FD

),

其中

QD

=

S

S

QN

对S

QD

和a

,

D(S,a)=

N(q,a)

FD=

S

S

QN

S

FN

需要证明:对任何w*

,

D({q0}

,w)=

N(q0,w).

归纳于|w|可证上述命题.q

SDFA和NFA的等价性

从NFA

构造等价的DFA（子集构造法）pq

r0{q}

{q}

{q,r}

10

{q}1

{p}{q}

{r}{p,q}

{p,r

}

{q,r

}

{p,q,r

}

{q}{q,r}

{q}{q,r}{q}

{q}{q,r}{q}{q,r}

DFA和NFA的等价性

子集构造法举例01{p}

{p,q,r}{p}{p,q}pq

r0{p}{r}

{r}

1{p,q}{p}{p,q}{p,q}{p,r}{p,q,r}

{p,r}{p,r}{p,q,r}DFA和NFA的等价性

子集构造法举例定理:

设N=(QN,

,

N,q0,FN)是一个NFA,通过子集构造法得到相应的DFAD=(QD,

,

D,{q0},FD

),则对任何w*

,

D({q0}

,w)=

N(q0,w).

证明:归纳于|w|1

设|w|=0,即w=

.

由定义知

D({q0}

,

)=

N(q0,

)={q0}

.2

设|w|=n+1,并w=xa,a

.注意到|x|=n.

假设

D({q0}

,x)=

N(q0,x)={p1,p2,

,pk}.

则

D({q0}

,w)=

D(

D({q0}

,x),a)=

D({p1,p2,

,pk},a)=

N(pi,a).=

N(q0,w)i=1kDFA和NFA的等价性

从NFA

构造等价的DFA（子集构造法）

实践中,通过子集构造法得到的DFA的状态数目与原NFA的状态数目大体相当

在较坏的情况下,上述DFA的状态数目接近于所有子集的数目

举例由如下NFA构造的DFA的状态数目至少为2nq0q1q2qnDFA和NFA的等价性

子集构造法得到的状态数

上页例子的证明要点，采用反证法假设由此NFA构造的DFA的状态数目少于2nq0q1q2qn

考虑长度为n的0,1串共有2n个，所以存在两个不同的串a1a2…an和b1b2…bn

作为该DFA的输入，可以到达同一状态q.（byPigeonholePrinciple）

若a1

b1，则q既是终态又是非终态，矛盾；

一般情况，若ak

bk，设a1a2…an00…0（k-1个0）或b1b2…bn00…0（k-1个0）作为输入串时该DFA

到达状态p,则p既是终态又是非终态，矛盾。DFA和NFA的等价性

子集构造法得到的状态数

举例设计一个NFA用来在文本中搜索字符串web

和ebb.

解下图为一个满足条件的NFA，其中

代表所有ASCII

字符的集合.

文本搜索

举例构造与前面NFA

等价的DFA.

–w–e

–w–e

–w–e–b

–w–e–b

–w–e–b

–w–e–b

–w–e

文本搜索q1q0q2q3q5

,+,–q4比较：NFAwithout

q0q1q2q3q4q

5+,–带

-转移的非确定有限自动机

举例

一个

-NFA

是一个五元组A=(Q,

,

,q0,F).

有限状态集

有限输入符号集

转移函数

一个开始状态

一个终态集合q0

Q

F

Q

与NFA的不同之处

:Q

（

）2Q带

-转移的非确定有限自动机

带

-转移的非确定有限自动机（

-NFA）

的形式定义q1q0q2q3q5

,+,–q4

{q1}

+,–.0,1,…,9q0q1q2q3q4q5{q1}

{q2}{q3}{q3}{q5}{q3}{q1,q4}带

-转移的非确定有限自动机

转移图和转移表表示的

-NFAq1q0q2q3q5

,+,–q4

该

-NFA可以接受的字符串如：

3.14

+.314

–314.带

-转移的非确定有限自动机

-NFA如何接受输入符号串q1q0q2q3q5

,+,–q4

状态q的

-闭包，记为ECLOSE(q)，定义为从q经所有的

路径可以到达的状态（包括q自身），如：

ECLOSE(q0)={q0,q1}

ECLOSE(q2)={q2}

ECLOSE(q3)={q3,q5}带

-转移的非确定有限自动机

-闭包（closure）

设

-NFAA=(Q,

,

,q0,F)，q

Q，ECLOSE(q)

为满足如下条件的最小集：

（1）q

ECLOSE(q)（2）ifp

ECLOSE(q)andr

(p,

),thenr

ECLOSE(q)

对于右图，有：

ECLOSE(1)={1,2,4,5,6,7

}

ECLOSE(2)={2,4,5,6,7

}

ECLOSE(7)={5,7

}

带

-转移的非确定有限自动机

-闭包

设一个

-NFAE=(Q,

,

,q0,F)

:Q

2Q

扩充定义

:Q*

2Q

对任何q

Q，定义：

1(q

,)=ECLOSE(q)

2若w=xa,其中x

*

,a

,假设

(q

,x)={p1,p2,

,pk},并且

令

(pi

,a)={r1,r2,

,rm}，

则

(q

,w)=

ECLOSE(rj)i=1kj=1m带

-转移的非确定有限自动机

扩展转移函数适合于输入字符串q1q0q2q3q5

,+,–q4

举例计算

(q0,5.6)

(q0,)

=ECLOSE(q0)={q0,q1}

(q0,5)

(q1,5)

={q1,q4}

(q0,5)

=ECLOSE(q1)

ECLOSE(q4)={q1,q4}

(q1,.)

(q4,.)

={q2,q3}

(q0,5.)

=ECLOSE(q2)

ECLOSE(q3)={q2,q3,q5}

(q2,6)

(q3,6)

(q5,6)

={q3}

(q0,5.6)

=ECLOSE(q3)={q3,q5}带

-转移的非确定有限自动机

扩展转移函数适合于输入字符串

设一个

-NFAE=(Q,

,

,q0,F)

定义E的语言：

L(E)=

w

w

*

(q0,w)

F

设L是

上的语言，如果存在一个

-NFAE=(Q,

,

,q0,F)，满足L=L(E)，则可以证明L也是一个正规语言.

带

-转移的非确定有限自动机

-NFA的

语言定理:

L是某个

-NFA的语言,当且仅当L

也是某个DFA的语言.

证明:分两步证明.

(1)设L是某个DFAD的语言,则存在一个

-NFAE,满足L(E)=L(D)=L;

(2)设L是某个

-NFAE的语言,则存在一个

DFAD,满足L(D)=L(E)=L;

带

-转移的非确定有限自动机

-NFA与DFA的等价性

设L是某个DFAD=(Q,

,

D,q0,F)的语言,

则存在一个

-NFAE,满足L(E)=L(D)=L.

证明:

定义

E=(Q,

,

E,q0,F),

其中

E定义为

对任何q

Q,

E(q,

)=

对任何q

Q和a

,

若

D(q,a)=p,则

E(q,a)={p}.

需要证明:

对任何w*

,

D(q0,w)=piff

E(q0,w)={p}.

归纳于|w|易证上述命题.带

-转移的非确定有限自动机

从DFA构造等价的

-NFA

设L是某个

-NFAE=(QE,

,

E,q0,FE)的语言,则存在一个DFAD,满足L(D)=L(E)=L.

证明:定义

D=(QD,

,

D,qD,FD

),

其中

QD

=

S

S

QE

S=

ECLOSE(S)

qD=ECLOSE(q0)

FD=

S

S

QD

S

FE

对S

QD

和a

,

令S={p1,p2,

,pk}，

并设

E(pi

,a)={r1,r2,

,rm}，

则

D(S,a)=

ECLOSE(rj)

.

需要证明:对任何w*

,

D(qD,w)=

E(q0,w).

归纳于|w|可证上述命题.i=1kj=1m带

-转移的非确定有限自动机

从

-NFA

构造等价的DFA（修改的子集构造法）q1q0q2q3q5

,+,–q4{q0q1}{q1}{q1q4}{q2}{q2q3q5}{q3q5}带

-转移的非确定有限自动机

修改的子集构造法举例

设E=(QE,

,

E,q0,FE)是一个

-NFA,通过修改的子集构造法得到相应的DFAD=(QD,

,

D,qD,FD

),则对任何w*

,

D(qD,w)=

E(q0,w).

证明:归纳于|w|1

设|w|=0,即w=

.

由定义知

D(qD,

)=qD=ECLOSE(q0)

=

E(q0,

).2

设|w|=n+1,并w=xa,a

.注意到|x|=n.

假设

D(qD,x)=

E(q0,x)={p1,p2,

,pk}.i=1k

并设

E(pi

,a)={r1,r2,

,rm}.

则

D(qD,w)=

D({p1,p2,

,pk},a)=

ECLOSE(rj)

=

E(q0,w)j=1m带

-转移的非确定有限自动机

从

-NFA

构造等价的DFA（修改的子集构造法）

知识回顾：集合上的等价关系与集合的划分DFA状态集合上的一个等价关系

计算状态集划分的算法—填表法

最小化的DFA（确定）有限自动机的最小化

知识回顾：集合上的等价关系与集合的划分

等价关系

设Q为一个集合，二元关系R是Q上的一个等价关系,

当且仅当满足以下条件：

1.自反性

对任何a

Q,aRa成立；

2.对称性

对任何a,b

Q,如果aRb成立,

则有bRa成立；

3.传递性

对任何a,b,c

Q,如果aRb和bRc成立,

则有aRc成立.（确定）有限自动机的最小化

等价关系与划分

设Q为一个集合，R是Q上的一个等价关系,由R产生的所有等价类（或块）的集合构成Q的一个划分.

解释

1.等价类

对任何a

Q,a所在的块用[a]表示,定义为

[a]

=

{x|xRa}

；

2.每一元素都属于唯一的块

即满足（1）

a

Q[a]=Q;和

（2）对任何a,b

Q,或者[a]=[b]

,或者[a]

[b]=（确定）有限自动机的最小化

知识回顾：集合上的等价关系与集合的划分DFA状态集合上的一个等价关系

设一个DFAD=(Q,

,

,q0,F),定义Q上的一个二元关系R为：对任何p,q

Q,

pRqiffw

*.('(p,w)

F

'(q,w)

F

)

结论上述关系R是等价关系.证明：1.自反性对任何q

Q,qRq成立；

2.对称性对任何p,q

Q,pRq

qRp成立；3.传递性对任何p,q,r

Q,设pRq和

qRr成立,即对任何w

*,'(p,w)

F

'(q,w)

F和

'(q,w)

F

'(r,w)

F成立；由此，也有

'(p,w)

F

'(r,w)

F成立.所以，qRr成立（确定）有限自动机的最小化

若pRq,称p和q等价（equivalent）.若p和q不等价，则称p和q是可区别的（distinguishable）.

关系R对应有限状态集Q的一个划分；该划分的每个块是Q的一个子集；

同一划分块中的所有状态之间都是相互等价的；分属不同划分块的任何两个状态之间都是可区别的.

DFA

的优化

通过合并等价的（或不可区别的）状态关键：如何计算上述划分？（确定）有限自动机的最小化DFA状态集合上的一个等价关系

设状态

r

和s

通过某个输入符号a

可分别转移到p

和q（即

(r,a)=p,(s,a)=q），则有

p

和

q

可区别

r

和s

可区别（确定）有限自动机的最小化

有关可区别性的几个有用的结果

这是因为：若p和q可为字符串w

区别,则r和s可为字符串aw

区别.（∵

'(r,aw)='(p,w),'(s,aw)='(q,w)

）

设状态

r

和s

通过某个输入符号a

可分别转移到p

和q（即

(r,a)=p,(s,a)=q），则有

r

和

s

不可区别

p

和q

不可区别（确定）有限自动机的最小化

有关可区别性的几个有用的结果（前页结果的逆否

）

设状态

r

和s

通过某个输入符号a

可分别转移到p

和q（即

(r,a)=p,(s,a)=q），则有

r

和

s

可由ax

区别

p

和q

可由x

区别（确定）有限自动机的最小化

有关可区别性的几个有用的结果（∵

'(r,ax)='(p,x),'(s,ax)='(q,x)

）

计算状态集划分的算法—填表法

填表算法（table-fillingalgorithm）基于如下递归地标记可区别的状态偶对的过程:

基础

如果p为终态，而q为非终态，则p和q标记为可区别的；

归纳

设p和q已标记为可区别的,如果状态r和s

通过某个输入符号a可分别转移到p和q，

(r,a)=p,(s,a)=q,则r和s也标记为可区别的；（确定）有限自动机的最小化

计算状态集划分的算法—填表法

填表算法举例xxxxxxxxxxxxx(1)区别所有终态和非终态(2)区别(1,3),(1,4),(2,3),(2,4),(5,6),(5,7)xxxxx(3)区别(3,4)x(4)结束.划分结果：{1,2},{3},{4},{5},{6,7}（确定）有限自动机的最小化

填表算法的正确性还需证明：如果两个状态没有被填表算法标记，则这两个状态一定是等价的

证明反证法.

假定状态r和s没有被填表算法标记，但这两个状态不是等价的，即是可区别的.

设字符串w可用于区别状态r和s，即

'(r,w)和

'(s,w)两个状态中，一个是终态，一个是非终态.不妨设前者为终态,后者为非终态.

首先不可能有w=

,否则,状态r为终态,

而s为非终态，依填表算法,r和s第一步就被标记.

设w=ax,并且

(r,a)=p,

(s,a)=q,则p和q可被x

区别.但同样p和q不可能被填表算法标记(否则,r和s将被标记).同样也有,x

.该过程不可能一直下去,终将产生矛盾.（确定）有限自动机的最小化

计算状态集划分的算法—填表法

通过合并等价的状态进行DFA

的优化

步骤

1.删除所有从开始状态不可到达的状态及与其相关的边,

设所得到的DFA

为A=(Q,

,

,q0,F)

；

2.使用填表算法找出所有等价的状态偶对；

3.

根据2的结果计算当前状态集合的划分块，每一划分块中的状态相互之间等价，而不同划分块中的状态之间都是可区别的.包含状态q的划分块用[q]表示.

4.构造与A等价的DFA

B=(QB,

,

B,[q0],FB

),其中

QB={[q]|q

Q},FB={[q]|q

F},B([q],a)=[

(q,a)]（确定）有限自动机的最小化

结论对任何w

*,

B([q0],w)

FB,iff

(q0,w)

F

举例

划分结果：

{1,2},{3},{4},

{5},{6,7}

等价的状态偶对为：

（1,2）,（6,7）

新的状态集合：

[1],[3],[4],[5],[6]（确定）有限自动机的最小化

通过合并等价的状态进行DFA

的优化

最小化的DFA

问题假定一个DFA

为A,用上述优化步骤构造出与A等价的DFA

M;那么是否存在一个状态数目比M还少的DFAN,它接受的语言同A和M完全一样?

假设存在一个这样DFAN.现将M和N相并,即状态、转移规则都相并,

这里假定M和N之间没有重名的状态,

因而也没有相交的转移边,

原来的终态还是终态,原来的两个初态中任选一个作为新的初态.同时还假定M和N的每一状态都是从其相应的初态可以到达的，否则我们将去掉不可达状态，得到状态数目更小的

DFA.（确定）有限自动机的最小化

最小化的DFA（确定）有限自动机的最小化

结论对任何DFA

A,用前述优化步骤构造出与A等价的

DFA

M;那么M的状态数目不多于任何语言为L(A)的DFA

对M和N相并后的DFA

运用填表算法可以得出:

1.

M和N的初态是不可区别的,因为L(M)=L(N);2.若r和s是不可区别的,

则对于任何输入符号,

r

和s的后继状态之间也是不可区别的;3.M

的任一状态至少与N