引发血案的 NFA 就是下面这个，来自最近的《编译原理》作业的一道题：
将这个 NFA 转化成 DFA
把 NFA 变成 DFA 是有明确的办法的。只是，如果试着画一画上面这个图，就会发现另外一个问题，到底要画多少条线，几个圈，会不会把自己绕糊涂呢 
于是我就想去找一个程序，可以自动完成这种枯燥的 NFA 到 DFA 的转换工作 。在 pluskid 的这篇日志里面看到了 reAnimator 这个在线工具，它可以把一串正则表达式的NFA和最简的DFA画出来。不过只能处理简单的情况，像上面那样
(a|b)*a(a|b)(a|b)(a|b)(a|b)
的表达式根本没法画出图来 
reAnimator 作者的博客上面介绍了它的实现，但具体细节并没有公开，只好再去找其他的工具……
直觉说 Mathematica 很可能提供了相关的功能。很遗憾找了半天没找到内建的和 FA 有关的函数，惊喜的是在网上有一个叫做 Finite Automata 的 Mathematica 包，看起来功能全面，挺不错。但是用一下就发现它的实现（比如，NFA 到 DFA 的转换）是有错误的，果断放弃 
再找到的就是一个叫做 Visual Automata Simulator 的软件，提供了 NFA 到 DFA 转换的功能，看起来很不错。用它完成了转换工作，血案由此产生了：一共画出来了 32 个状态和 64 条边……
经过简单的测试， VAS 软件并不会做最小化 DFA 的工作，那么上面的结果可不可以再简单一点呢？比如下面的这个 DFA：
可以被最小化到：
试试看？我在 VAS 的代码上加了课本上介绍的最小化 DFA 的方法，结果对刚才的 64 条边的图毫无效果 
那么就把这个图打印出来吧，都到这一步了，写一个“略”在作业本上不太好吧。不过，VAS 自己没有自动排版功能，线条和圆圈画得非常乱。在 VAS 中不难实现一个导出 dot 文件的功能，然后就可以用 graphviz 来排版了 
最后排出来大概是这个样子，还是挺乱的样子，也许自动排版成这个样子算是很好了吧。
我觉得 VAS 这个工具还是挺好的，在官方 1.2.2 版本上我添加了 DFA 最小化和导出到 dot 文件两个功能，擅自把版本号改成了 1.2.3。放在这里，也许什么时候会被用一下：
还好啦还好啦，当时编译原理的题目都是一个状态图就画一页的，手工画还挺好玩的。
@pluskid : 我周围的人和我自己都觉得写一个“略”比较合适
很好玩的样子
其实不太好玩的，本来期待 Mathematica 能完成这些事情的，那样就好玩一些……
留言测试- –
其实很久以前我本来想说的是，当年我学这个的时候也折腾过，不过最后还是人肉画了。
@hzqtc : 测试通过
@pluskid : 表示考试的时候就一点都不好玩了
我自己写了个NFA->DFA->最小化的程序，结果从你的正则式得到了32个节点的图……不知道是我的程序写搓了还是对龙书的最小化算法理解不深
@digiter : 我这里也说了是 “32 个状态，64 条边”，一样的啊？
Thank you for your entire labor on this web site. My mom take interest in participating in investigations and it is obvious why. My partner and i learn all regarding the lively tactic you produce simple things through your web site and in addition invigorate response from the others on the subject then our favorite princess is truly studying a whole lot. Take advantage of the rest of the year. You have been doing a superb job.