上篇讲述确定有穷自动机和不确定有穷自动机,本篇讲述不确定有穷自动机和确定有穷自动机之间的转换。从百度文库中找到一个示例感觉很合适。
如图所示:
1.具有ε动作的NFA状态转换表
|
a |
b |
ε |
0 |
Φ |
Φ |
1, 7 |
1 |
Φ |
Φ |
2, 4 |
2 |
3 |
Φ |
Φ |
3 |
Φ |
Φ |
6 |
4 |
Φ |
5 |
Φ |
5 |
Φ |
Φ |
6 |
6 |
Φ |
Φ |
1, 7 |
7 |
8 |
Φ |
Φ |
8 |
Φ |
9 |
Φ |
9 |
Φ |
Φ |
Φ |
2.分别求ε-closure
ε-closure(I)就是状态集I中,任意状态S经过任意的 ε能到达的状态集合。
ε-closure(0) = {0,1,2,4,7}
ε-closure(1) = {1,2,4}
ε-closure(2) = {2}
ε-closure(3) = {1,2,3,4,6,7}
ε-closure(4) = {4}
ε-closure(5) = {1,2,4,5,6,7}
ε-closure(6) ={1,2,4,6,7}
ε-closure(7) = {7}
ε-closure(8) = {8}
ε-closure(9) = {9}
3.转换算法:
move(I,a)是从I中的某一状态经过一条a弧而到达的状态全体。
ε-closure(0) ={0,1,2,4,7} = A
ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8} = B
ε-closure(move(A,b))=ε-closure({5})={1,2,4,5,6,7} = C
ε-closure(move(B,a))=ε-closure({3,8}) = B
ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9} = D
ε-closure(move(C,a))=ε-closure({3,8}) = B
ε-closure(move(C,b))=ε-closure({5}) = C
ε-closure(move(D,a))=ε-closure({3,8}) = B
ε-closure(move(D,b))=ε-closure({5}) = C
4.DFA的转换表
状态 |
输入符号 |
|
a |
b |
|
A |
B |
C |
B |
B |
D |
C |
B |
C |
D |
B |
C |
5.状态转换图
本篇到这里,编译原理入门教程就到这里了。