编译原理（二）DFA与NFA

一般凭直观构造出的自动机都是NFA，而要把NFA转换成DFA，要用子集构造法。构建DFA的目的是，，，反正DFA比NFA有用。一般是正则表达式->NFA->DFA。

定义真的是蛮变态的，还是自己总结的清楚简单直接明白。

这个图是一个NFA，NFA的写法就是从一个开始，最后的那个状态用双圈表示，这里的意思就是从0开始，找0的闭包是为A，然后看输入符号a后的那一个闭包就是B，然后一直往下写就是了：

然后就按照表画自动机就可以了。有限自动机也是有双圈。

这么简单的事情愣是说的那么复杂。。。

紧接着就是DFA的化简，化简一样是说的超级啰嗦。

首先分成两类，结束符D单独一类，剩下组成的一类，然后看转移条件，是每个节点的转移，如果不是只在自己的G内转移，就要拆分，把指向别的的那个单独拆出来。只有那个B节点的指向D了，这就是指向G1了，这个是没错的，如果只有一个节点了，它还指向别的，那就不用管了。因为只拆分多个的。

噢错了，是一个通路只能走向一个类，例如b走向G2，G1的话，那么就需要进行拆分，是这个意思。

正则文法,正则表达式,有限自动机都是等价的，文法就是bison的那些，正则表达式很简单了，它们都是等价的。

自动机转换成正则文法或者正则表达式也是蛮简单的吧。