NFA转DFA的算法在编译原理的课本上都有,只不过课本上的算法太拗口,不好记!我在这里边说的都很通俗,只要看得懂字的都会懂。在本篇文章里用一个例子来说明怎么实现NFA转DFA与DFA简化,NFA转DFA会讲的比较细,DFA简化只是大概带过。 有一个NFA,如图: 要是想把NFA转成DFA,首先需要构造一张表(最主要的就是这张表),如图: 上图没有给出全部的转换关系,当然,大家这么聪明,在看了构造表的算法之后就会自己构造转换表了。构造转换表的算法如下(表中的第一列是给为化简的DFA状态取的名字,第二列也是DFA中的状态,第三列和第四列是DFA在某一状态在读取a、b时跳转到的状态):
在构造了表之后就可以通过这个表来构造相应的DFA了(有X的是初态,有Y的是终态),在这里不再赘述怎么用表来构造DFA。 在构造了DFA之后就需要来化简它了,化简DFA的算法如下:
上述所说的方法结合例子来看就更容易理解了! |
|
来自: 心灵地图sxh > 《DFA and NFA》