整个流程是这样的
我们直接来看一个例子，使用上面的算法来实现我们最后的目标
(a|b)*ba(ab)*
明确：开始状态和接受状态，终结状态要画两个圈,值得注意的是，由于*也可以代表出现了0次，10号状态也是接受状态
举个例子，对S1={1,2,3,5,8}
如果此时收到‘a’，我们可以轻易画出转移的路线{1->{},2->{},3->{4,7,8,2,3,5},5->{},8->{}}
把他们合并起来，即S1通过a到S2={2,3,4,5,7,8}
如果此时收到’b’，同理画出路线{1->{},2->{},3->{},4->{},5->{6,7,8,2,3,5},8->{9}}
把他们合并起来，即S1通过b到S3={2,3,5,6,7,8,9}
| S | a | b |
|---|---|---|
| S1={1,2,3,5,8} | S2={2,3,4,5,7,8} | S3={2,3,5,6,7,8,9} |
| S2={2,3,4,5,7,8} | S2={2,3,4,5,7,8} | S3={2,3,5,6,7,8,9} |
| S3={2,3,5,6,7,8,9} | S4={2,3,4,5,7,8,10,11,14} | S3={2,3,5,6,7,8,9} |
| S4={2,3,4,5,7,8,10,11,14} | S5={2,3,4,5,7,8,12} | S3={2,3,5,6,7,8,9} |
| S5={2,3,4,5,7,8,12} | S2={2,3,4,5,7,8} | S6={2,3,5,6,7,8,9,11,13,14} |
| S6={2,3,5,6,7,8,9,11,13,14} | S5={2,3,4,5,7,8,12} | S3={2,3,5,6,7,8,9} |
| S | a | b |
|---|---|---|
| S1 | S2 | S3 |
| S2 | S2 | S3 |
| S3 | S4 | S3 |
| S4 | S5 | S3 |
| S5 | S2 | S6 |
| S6 | S5 | S3 |
只要记住对每个状态我们都要询问从a可以走到哪，从b可以走到哪，这样状态就不会遗漏
我们要给接受状态画两个圈圈，S4、S6包含我们的接受状态
这个算法先把集合分成两个初始的集合,一个是接受状态，一个是非接受状态
Non-Accept={S1,S2,S3,S5}
Accept={S4,S6}
不如先考察Non-Accept集合吧
接受‘a’，S1->S2,S2->S2,S3->S4,S5->S2
我们发现可以把{S1,S2,S5}分成一类，{S3}自成一派
继续，考虑{S1,S2,S5}
接受‘a’，他们最终都会变成S2，显然这个不是一个划分
接受’b’呢？S1->S3,S2->S3,S5->S6
我们又得到了一个划分
{S1,S2} {S5}
无法继续划分了
对Accept集合，我们发现无论是’a’还是‘b’都不能把它俩分开，干脆让他俩在一个集合里好了
如果还不懂的话，可以看一下这个论文
https://www.docin.com/p-553259613.html
