a 开始 0 2 3
状态 A B C D

a 7 6
输入符号 a b B C B D B C B C
b 8

1 b 4 5

9
3.3 有 限 自 动 机 b
C b 开始 A a B a a b a a 开始 0 2 3 b D
状态 A B C D

a 7 6
输入符号 a b B C B D B C B C
a 2 3
开始 0

1 b 4 5

6 7
a 8
b
9
子集构造法
找出U=ε-closure(T) 对于U，以及任意符号a，找出U通过a能到达的集合 V=Move(U,a) ，并计算V'=ε-closure(V) U通过a到达的状态即为V'，U- a -> V'
a 开始 0 2 3

3.3 有 限 自 动 机
3.3.4 DFA的化简 构造最简DFA：
构造状态集合的初始划分π：两个子集——接受状态子集
F和非接受状态子集S – F 应用下面的过程构造πnew
For π 中的每个子集G ，do begin 把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅 当对任意输入符号 a ，s 和 t 的 a 转换都到 π 的同一子集中 在πnew 中，用G的划分代替G End
DFA的化简
构造最简的DFA 接受状态子集{D},非接受状态子集{A,B,C} {A,B,C}->{A,C} {B}

b
C b 开始 a a B a b D a b
A
从正则表达式到有限自动机
3.4 从正则式到有限自动机

从正则式建立识别器的步骤
从正则式构造NFA（本节介绍）
用语法制导的算法，它用正则式语法结构来指导构造

1 b 4 5

6 7
a 8
b
9
3.3 有 限 自 动 机 3.3.3 NFA到DFA的变换
子集构造法：状态转换表的构造
3.3 有 限 自 动 机

例 (a|b)*ab，NFA如下，把它变换为DFA
a 开始 0 2 3

1 b 4 5

6 7
a 8
b
9
3.3 有 限 自 动 机
构造状态集合的初始划分π ：两个子集——接受状态子
集F和非接受状态子集S – F
3.3 有 限 自 动 机
3.3.4 DFA的化简 构造最简DFA：
构造状态集合的初始划分π：两个子集——接受状态子集
F和非接受状态子集S – F 应用下面的过程构造πnew
For π 中的每个子集G ，do begin 把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅 当对任意输入符号 a ，s 和 t 的 a 转换都到 π 的同一子集中 在πnew 中，用G的划分代替G End
2 a 3
开始 0

1 b 4 5

6 7
a 8
b 9
3.4 从正则式到有限自动机 r
9
(a|b)*ab的分解
r4
r7 r5 * ) a r6
r8
b
(
r1
r3 | a
r2
b a 3
开始 0
2

1 b 4 5

6 7
a 8
b 9
3.4 从正则式到有限自动机 r
3.3 有 限 自 动 机
3.3.3 NFA到DFA的变换
子集构造法
子集构造法


ε-closure(s) 从NFA的状态S出发，只用ε转换就能到达的 状态的集合 ε-closure(T) 从NFA的状态集合T中每个状态出发，只用ε
转换就能到达的状态的集合
Move(T,a) 状态集合T中每个状态通过 a能到达的所有状态 集合
N(r)的状态数最多是r中符号和算符总数的两倍 N(r) 只有一个接受状态，接受状态没有向外的转
换
2 a

开始 0
3


1 b 4 5

6 7
a 8
b 9
3.4 从正则式到有限自动机

本方法产生的NFA有下列性质
N(r) 的每个状态有一个用 的符号标记的指向其

它结点的转换，或者最多两个指向其它结点的 转换
过程
把NFA变成DFA （子集构造法，已介绍） 将DFA化简 （合并不可区别状态，也已介绍）
3.4 从正则式到有限自动机

首先构造识别和字母表中一个符号的NFA
重要特点：仅一个接受状态，它没有向外的转换 开始 开始
i
f
i
a
f
识别正则式的NFA
识别正则式a的NFA
3.4 从正则式到有限自动机
9
(a|b)*ab的分解
r4
r7 r5 * ) a r6
r8
b
(
r1
r3 | a
r2
b a 3
开始 0
2

1 b 4 5

如果πnew = π，则πfinal = π；否则令π = πnew ，转上步
3.3 有 限 自 动 机
3.3.4 DFA的化简 构造最简DFA：
构造状态集合的初始划分π：两个子集——接受状态子集
F和非接受状态子集S – F 应用下面的过程构造πnew
For π 中的每个子集G ，do begin 把G划分为若干子集，G的两个状态 s 和 t 在同一子集中，当且仅 当对任意输入符号 a ，s 和 t 的 a 转换都到 π 的同一子集中 在πnew 中，用G的划分代替G End

构造识别主算符为选择的正则式的NFA
重要特点：仅一个接受状态，它没有向外的转换
开始
i
N (s)


N (t)
f
识别正则式s | t 的NFA
3.4 从正则式到有限自动机

构造识别主算符为连接的正则式的NFA
重要特点：仅一个接受状态，它没有向外的转换 开始
i
N (s)
N (t)
f
识别正则式 st 的NFA
a 开始 0 2 3
状态 A B C
输入符号 a b B C B D

1 b 4 5

6 7
a 8
b
9
3.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9}
从正则表达式到有限自动机
3.7~3.9
有限自动机
3.3 有 限 自 动 机 3.3.1 不确定的有限自动机（简称NFA）
一个数学模型，它包括： 一个符号标记离开同一状态有多条边 1、有限的状态集合S 2、输入符号集合 3、转换函数move : S ( {} ) P(S) 4、状态s0是唯一的开始状态 5、F S是接受状态集合 a 识别语言 (a|b)*ab 的NFA
1、有限的状态集合S 2、输入字母集合 3、转换函数move : S S，且可以是部分函数 4、唯一的开始状态 s0 b 5、接受状态集合F S b
识别语言 (a|b)*ab 的DFA
开始 0 a b 1 a a 2
3.3 有 限 自 动 机

例 识别 (a | b)* a b 的DFA
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7}
a 开始 0 2 3
状态 A B C
输入符号 a b B C B

1 b 4 5

6 7
a 8
b
9
3.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9}
a 开始 0 2 3
状态 A B C D

a 7 6
输入符号 a b B C B D B C

1 b 4 5
b 8

9
3.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9}
b 8

1 b 4 5

9
3.3 有 限 自 动 机 b
识别语言 (a|b)*ab 的自动机
开始 A C b a B a a b a a 开始 0 2 3 b D 开始 0 b b
a
b 1 a a 2

1 b 4 5

6 7
a 8
b
9
3.3 有 限 自 动 机 b
a 开始 0 2 3
状态 A B C D

a 7 6
输入符号 a b B C B D

1 b 4 5
b 8

9
3.3 有 限 自 动 机
A = {0, 1, 2, 4, 7} B = {1, 2, 3, 4, 6, 7, 8} C = {1, 2, 4, 5, 6, 7} D = {1, 2, 4, 5, 6, 7, 9}