一个 NFA 引发的血案

引发血案的 NFA 就是下面这个,来自最近的《编译原理》作业的一道题:

ex_nfa2dfa

将这个 NFA 转化成 DFA

把 NFA 变成 DFA 是有明确的办法的。只是,如果试着画一画上面这个图,就会发现另外一个问题,到底要画多少条线,几个圈,会不会把自己绕糊涂呢 .~.

于是我就想去找一个程序,可以自动完成这种枯燥的 NFA 到 DFA 的转换工作 。在 pluskid 的这篇日志里面看到了 reAnimator 这个在线工具,它可以把一串正则表达式的NFA和最简的DFA画出来。不过只能处理简单的情况,像上面那样

(a|b)*a(a|b)(a|b)(a|b)(a|b)

的表达式根本没法画出图来 o.o reAnimator 作者的博客上面介绍了它的实现,但具体细节并没有公开,只好再去找其他的工具……

直觉说 Mathematica 很可能提供了相关的功能。很遗憾找了半天没找到内建的和 FA 有关的函数,惊喜的是在网上有一个叫做 Finite AutomataMathematica 包,看起来功能全面,挺不错。但是用一下就发现它的实现(比如,NFA 到 DFA 的转换)是有错误的,果断放弃 :sigh:

再找到的就是一个叫做 Visual Automata Simulator 的软件,提供了 NFA 到 DFA 转换的功能,看起来很不错。用它完成了转换工作,血案由此产生了:一共画出来了 32 个状态和 64 条边……

经过简单的测试, VAS 软件并不会做最小化 DFA 的工作,那么上面的结果可不可以再简单一点呢?比如下面的这个 DFA:

dfa_normal

可以被最小化到:

dfa_minimized

试试看?我在 VAS 的代码上加了课本上介绍的最小化 DFA 的方法,结果对刚才的 64 条边的图毫无效果 ._.

那么就把这个图打印出来吧,都到这一步了,写一个“略”在作业本上不太好吧。不过,VAS 自己没有自动排版功能,线条和圆圈画得非常乱。在 VAS 中不难实现一个导出 dot 文件的功能,然后就可以用 graphviz 来排版了 (:

最后排出来大概是这个样子,还是挺乱的样子,也许自动排版成这个样子算是很好了吧。

我觉得 VAS 这个工具还是挺好的,在官方 1.2.2 版本上我添加了 DFA 最小化和导出到 dot 文件两个功能,擅自把版本号改成了 1.2.3。放在这里,也许什么时候会被用一下:

Visual Automata Simulator 1.2.3 (jar) (源代码)

10 thoughts on “一个 NFA 引发的血案

  1. 我自己写了个NFA->DFA->最小化的程序,结果从你的正则式得到了32个节点的图……不知道是我的程序写搓了还是对龙书的最小化算法理解不深

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>