引发血案的 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) (源代码)

Tagged with:  
  • http://blog.pluskid.org pluskid

    还好啦还好啦,当时编译原理的题目都是一个状态图就画一页的,手工画还挺好玩的。 ^_.

  • http://lihdd.net quark

    @pluskid : 我周围的人和我自己都觉得写一个“略”比较合适 ._.

  • http://watashi.ws/blog/ watashi

    很好玩的样子

    • http://lihdd.net quark

      其实不太好玩的,本来期待 Mathematica 能完成这些事情的,那样就好玩一些……

  • http://hzqtcblog.appspot.com/ hzqtc

    留言测试- -

  • http://hzqtcblog.appspot.com/ hzqtc

    其实很久以前我本来想说的是,当年我学这个的时候也折腾过,不过最后还是人肉画了。

  • http://lihdd.net quark

    @hzqtc : 测试通过 (:

  • Mike

    @pluskid : 表示考试的时候就一点都不好玩了

  • digiter

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

    • http://lihdd.net quark

      @digiter : 我这里也说了是 “32 个状态,64 条边”,一样的啊?