形式语言与自动机PPT学习教案.pptx

会计学
1
形式语言与自动机
2
2021/4/29
从 DFA 构造等价的正则表达式
（中间状态的消去）
x
y
r1r2
x
z
r1
y
r2
代之以：
x
y
r1+r2
x
y
r2
r1
代之以：
x
y
r1*
x
z

y

r1
代之以：
第1页/共37页
3
2021/4/29
从 DFA 构造等价的正则表达式
（中间状态的消去）






q1
qk
p1
pm
P1
Pm
Qk
Q1
R11
R1m
Rkm
Rk1






R11+ Q1S* P1
R1m+ Q1S* Pm
Rkm+ QkS* Pm
Rk1 + QkS* P1
q1
p1
qk
pm
消去 s
第2页/共37页
4
2021/4/29
从 DFA 构造等价的正则表达式
（状态消去法）
步骤:

(1) 对每一终态q，依次消去除 q 和初态 q0 之外的其它状态;
(2) 若q q0，最终可得到一般形式如下左图的状态自动机，
该自动机对应的正则表达式可表示为 ( R+SU*T )*SU*.
(3) 若q= q0，最终可得到如下右图的自动机，它对应的正则
表达式可以表示为 R*.
(4) 最终的正则表达式为每一终态对应的
正则表达式之和（并）.
第3页/共37页
5
2021/4/29
状态消去法举例
对于终态C
对于终态D
等价的正则表达式
(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)
第4页/共37页
6
2021/4/29
状态消去法举例
0
1
3
4
2
5
6
7
a
b
a
a
b
b
a
b




0
1
2
5
6
7
a+b
a+b




aa
bb
0
2
5
7
(a+b)*
(a+b)*
aa+bb
0
7
(a+b)* (aa+bb) (a+b)*
第5页/共37页
7
2021/4/29
定理: L 是正则表达式 R 表示的语言, 则存在一个 - NFA E ,满足 L(E) = L(R) = L.

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

(1) 恰好一个终态;

(2) 没有弧进入初态；
(3) 没有弧离开终态；


从正则表达式构造等价的 - NFA
第6页/共37页
8
2021/4/29
基础:
从正则表达式构造等价的 - NFA
（归纳构造过程）
1 对于  ，构造为

3 对于 a ，构造为
a
2 对于  ，构造为
第7页/共37页
9
2021/4/29
归纳:
从正则表达式构造等价的 - NFA
（归纳构造过程）
1 对于 R+S ，构造为




第8页/共37页
10
2021/4/29
归纳:
从正则表达式构造等价的 - NFA
（归纳构造过程）
2 对于 RS ，构造为

3 对于 R* ，构造为




第9页/共37页