5 有限状态自动机正规表达式

第五讲

有限状态自动机

正规表达式

几个转换算法的复杂度（选讲）

有限自动机与正规表达式的关系有限状态自动机

正规表达式

结论:有限自动机所表示的语言是正规语言

证明策略RE有限自动机与正规表达式的关系

-NFANFADFA

定理:

L是正规表达式R表示的语言,

则存在一个

-NFA

E,满足L(E)=L(R)=L.

证明:构造性证明.可以通过结构归纳法证明从R可以构造出与其等价的，满足如下条件的

-NFA

：

(1)恰好一个终态;

(2)没有弧进入初态；

(3)没有弧离开终态；



从正规表达式构造等价的

-NFA有限自动机与正规表达式的关系

基础:1对于

，构造为

3对于a

，构造为a2对于

，构造为有限自动机与正规表达式的关系

归纳构造过程(从正规表达式构造等价的

-NFA)

（Thompson构造法）

归纳:1对于E+F

，构造为

有限自动机与正规表达式的关系

归纳构造过程(从正规表达式构造等价的

-NFA)

（Thompson构造法）2对于EF

，构造为

3对于E*

，构造为

有限自动机与正规表达式的关系

归纳:

归纳构造过程(从正规表达式构造等价的

-NFA)

（Thompson

构造法）设正规表达式1*0(0+1)*,构造等价的

-NFA.0+1

1*

有限自动机与正规表达式的关系

举例(从正规表达式构造等价的

-NFA)(0+1)*

1*0(0+1)*

有限自动机与正规表达式的关系

举例(从正规表达式构造等价的

-NFA)

定理:

L是某个DFAD的语言,

则存在一个正规表达式R,满足L(R)=L(D)=L.

证明:构造性证明.以下是两种构造方法

(1)路径迭代法（Kleene构造法）;

(2)状态消去法



从DFA构造等价的正规表达式有限自动机与正规表达式的关系

步骤:

(1)将DFAD的状态集用{1,2,…,n}表达，且初态为1

(2)对所有1

i,j

n,0

k

n，迭代计算R(ikj)；

这里,R(ikj)为表示如下语言的正规表达式：

w

L(R(ikj))iff从i到j有一条标记为w的路径,

且这条路径上除i和j之外的所有状态的编号均不大于k

(3)通过(2)的迭代过程，最终可计算出

R(inj)（i,j=1,2,…,n）

(4)将所有R(1nj)（j为任一终态）相“

”

路径迭代法（从DFA构造等价的正规表达式）有限自动机与正规表达式的关系

计算R(ikj)的迭代过程

基础:k=0Case1i

j若不存在从i到j的弧，则R(i0j)=

；若仅存在一条从i到j的弧，且标记为a

，则R(i0j)=a；若存在多条从i到j的弧，且标记为a1,a2,…,am，则R(i0j)=a1

a2

…

am

；Case2i=j若不存在从i到自身的圈，则R(i0j)=

；若存在一个从i到自身的圈且标记为a

，则R(i0j)=

a；若存在多个从i到自身的圈，且标记为a1,a2,…,am

，则R(i0j)=

a1

a2

…

am

；有限自动机与正规表达式的关系

计算R(ikj)的迭代过程

归纳:假设R(ki-j1)（i,j=1,2,…,n）已经求出.则迭代公式为R(ikj)=R(ki-j1)

R(ki-k1)(R(kk-k1))*R(kk-j1)

Case1路径不经过k.此时，标记该路径的字符串属于

L(R(ki-j1)

);Case2路径经过k至少一次.此时，标记该路径的字符串属于

L(R(ki-k1)(R(kk-k1))*R(kk-j1)

).如下图所示：分析:考虑从i到j的路径（除i和j之外的所有状态的编号不大于k

）R(ki-k1)(R(kk-k1))*R(kk-j1)有限自动机与正规表达式的关系

路径迭代法举例R(101)R(102)R(201)R(202)

1

0

10

有限自动机与正规表达式的关系R(i1j)=R(i0j)

R(i01)(R(101))*R(10j)化简R(111)R(112)R(211)R(212)直接替换

1

(

1)(

1)*(

1)0

(

1)(

1)*0

(

1)*(

1)

0

1

(

1)*01*1*0

0

1R(101)R(102)R(201)R(202)

1

0

10

有限自动机与正规表达式的关系

路径迭代法举例化简R(121)R(122)R(221)R(222)直接替换R(i2j)=R(i1j)

R(i12)(R(212))*R(21j)1*

1*0(

0

1)*

1*0

1*0(

0

1)*(

0

1)

(

0

1)(

0

1)*

0

1

(

0

1)(

0

1)*(

0

1)1*1*0(0

1)*

(0

1)*R(111)R(112)R(211)R(212)

0

1

1*1*0有限自动机与正规表达式的关系

路径迭代法举例结果:初态为1,终态只有一个2，所以，一个与上图的DFA等价的正规表达式为

R(122)=1*0(0

1)*有限自动机与正规表达式的关系

路径迭代法举例

思路:

(1)扩展自动机的概念，允许正规表达式作为转移弧的标记.这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变.

(2)在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补.

以下分别介绍中间状态的消去与正规表达式构造过程.有限自动机与正规表达式的关系

状态消去法（从DFA构造等价的正规表达式）

中间状态的消去

q1qkp1pmP1PmQkQ1R11R1mRkmRk1

R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去s有限自动机与正规表达式的关系

步骤:（假设自动机已转化为扩展的形式）

(1)对每一终态q，依次消去除q和初态q0之外的其它状态;(2)若q

q0，最终可得到一般形式如下左图两状态自动机，该自动机对应的正规表达式可表示为(R+SU*T)*SU*.(3)若q=q0，最终可得到如下右图的自动机，它对应的正规表达式可以表示为R*.(4)最终的正规表达式为每一终态对应的正规表达式之和（并）.有限自动机与正规表达式的关系

状态消去法（从DFA构造等价的正规表达式）

状态消去法举例（推广至非DFA的情形）有限自动机与正规表达式的关系对于终态D有限自动机与正规表达式的关系

状态消去法举例对于终态C有限自动机与正规表达式的关系

状态消去法举例对于终态C对于终态D等价的正规表达式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)有限自动机与正规表达式的关系

状态消去法举例

-NFANFADFARE

几个转换算法从DFA构造NFA

从NFA构造DFA

从DFA构造

-NFA

从

-NFA构造DFA

从DFA构造正规表达式

从正规表达式构造

-NFA

几个转换算法的复杂度（选讲）

从

DFA构造NFA

回顾：设DFAD=(Q,

,

D,q0,F),构造NFAN=

(Q,

,

N,q0,FN

),

其中

N定义为

对q

Q和a

,

若

D(q,a)=p,则

N(q,a)={p}.

设|Q|=n,

该构造过程复杂度为O(n),即线性时间.几个转换算法的复杂度（选讲）

回顾：设NFAN=(Q,

,

N,q0,F),构造D=(QD,

,

D,{q0},FD

),

其中

QD

=

S

S

Q

对S

QD

和a

,

D(S,a)=

N(q,a).

FD=

S

S

Q

S

F

设|Q|=n,

该构造过程复杂度为O(n22n).但实际运行时间的上界可以是O(n2s)，其中s为DFA实际状态数。q

S

从

NFA构造DFA几个转换算法的复杂度（选讲）

从DFA构造

-NFA

回顾：设DFAD=(Q,

,

D,q0,F),构造E=(Q,

,

E,q0,FE

),

其中

E定义为

对任何q

Q,

E(q,

)=

对任何q

Q和a

,

若

D(q,a)=p,则

N(q,a)={p}

设|Q|=n,

该构造过程复杂度为O(n).几个转换算法的复杂度（选讲）

从

-NFA

构造DFA

回顾：设

-NFAE=(QE,

,

E,q0,FE),构造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)

.

设|QE|=n,

该构造过程复杂度为O(n32n).但实际运行时间的上界可以是O(n3s)，其中s为DFA实际状态数。i=1kj=1m几个转换算法的复杂度（选讲）

从DFA构造正规表达式

回顾：

(路径迭代法)