加载中…正规表达式转换成NFA，最终化简为DFA
(2013-01-21 13:21:20)
标签：
杂谈 |
分类： Linux |
http://s13/mw690/697b9689gd3c5a70036bc&690
确定化：
|
|
0 |
1 |
|
{X,1,Y} |
{1,Y} |
{2} |
|
{1,Y} |
{1,Y} |
{2} |
|
{2} |
{1,Y} |
φ |
|
φ |
φ |
φ |
给状态编号：
|
|
0 |
1 |
|
0 |
1 |
2 |
|
1 |
1 |
2 |
|
2 |
1 |
3 |
|
3 |
3 |
3 |
http://s16/mw690/697b9689gd3c5a980b38f&690
最小化：
1、将所有状态作为一个大的集合：{0、1、2、3}
2、将这个集合进行划分，如{0、1、2}、{3}这样子也是可以的。
3、划分后按照这个集合中的状态取下一个元素为0的时候，{0、1、2}这个集合根据上面的（给状态编号）表格结果状态有1、1、1。 这个是符合的，但是取1的时候，结果状态有2、2、3 不一致，所以必须对这个集合再次进行划分，把导致不一致的拆开。所以有了{0、1}和{2}这两个集合。
4、最后加上第一个划分的{3}，总共有三个集合{0、1}{2}{3}，构成三个新的状态0,1,2
当然，前面的话必须从整个大地集合开始划分，即{0\1\2\3}把取一个元素的时候不一致结果的区分出来。
5、最后由于{3}这个状态时不可达的，为空的，所以将这个状态删除。
喜欢
0
赠金笔
后一篇：查看伪静态网站编程语言的方法