I I
a
= ε-closure(MoveTo(I,a)) I
b
= ε-closure(MoveTo(I,b))
1[S] 2[A] 3[Q]
2[A] 2[A] 4[B,Z]
3[Q] 3[Q] 5[D,Z]
4[B,Z] 3[Q] 6[D]
5[D,Z] 2[A] 7[B]
6[D] 2[A] 7[B]
7[B] 3[Q] 6[D]
因为4,5 状态包含Z, 所以都是终态,1,2,3,6,7 都是非终态;
1态输入 b 后为3, 是非终态;2 和 3输入 b后为 4和 5 是终态, 所以 1和 2,3 是不同的状态;
2和 3 是相同等价状态;4和 5 是等价状态;6 何是等价状态;
所以, 最后剩下: 1,2,4,6四个状态.
a
6
2
b
a
a
1
b
a
b
b
4
最小化的DFA
1 2 4
3
7
6
a
b
b
a
a
5
b
a
b
a
b
a
b
b
a
第 4 页 / 共 29 页