构造正规式最小DFA方法

1、今天早上去图书馆，去看编译原理，想把这部分搞清楚，看着龙书+国产的某一本不知什么的习题与解析，猜过程。猜原理。终于是看懂了。整体的步骤是三步：一，先把正规式转换为 NFA （非确定有穷自动机），二，在把NFA通过“子集构造法”转化为 DFA ,三，在把DFA通过“分割法”进行最小化。AA4a5X301(bl<z)團£3正w表达式到有隈口动粗的转擬规!<«这样就能转换到NFA 了。给岀一个例题，来自Google book 。本文主要根据这个例题来讲，图2构造与正达式(a* L b") Cba”等&的DFAdKtFri.首先构造正则表达式的NFA,

2、其构过程如图2.11所示中二.子集构造法。同样的例题，把转换好的I1亠02.1 氣4乩机九斜熄川人91(4.6.7,9111,3,4,5.,7.8.9|6(1,6.7,9討5了.时!8?柑NFA确定化，图3这个表是从NFA到DFA的时候必须要用到的。第一列第一行I的意思是从NFA的起始节点经过 任意个e所能到达的结点集合。la表示从该集合开始经过一个 a所能到达的集合，经过一个a的意 思是可以略过前后的e。同样lb也就是经过一个b，可以略过前后任意个至于第二行以及后面的I是怎么确定的。我参考了一些题目才明白，原来就是看上面的la和lb哪个还没岀现在I列，就拿下来进行运算，该列对应的la和lb就

3、是前面我说的那样推导。这步做完以后，为了画岀最后的DFA，那么肯定得标岀一些号来，比如1.2.3.。或者A ° B° c，我一般标的方法是先把I列全部标上1.2.3.递增。然后看1表示的集合和la和lb中的哪个集合一样， 就把那个集合也表示为1.继续向下做。最后会得到这样一个表格。图4远abf OU1264Q2S203360413A65至此，就可以表示岀 DFA 了。就对照上面那个表，从 0节点开始经过a到1.经过b到2，就这样 画就仃了° °最后的DFA如下图，图5这个是怎么来的呢。去看看图会发现有些项之前有双圈标志，这个是因为双圈的表示终态，在NFA

4、图2中，9为终态，所以所有包含9的集合都被认为是终态集，改成1.2.3.。°方便画节点后就需 要把这些点作为终态了。 °三.最小化，分割法。FA的最小化就是寻求最小状态 DFA最小状态DFA的含义：1.没有多余状态（死状态）2.没有两个状态是互相等价（不可区别）两个状态s和t等价的条件：兼容性（一致性）条件一一同是终态或同是非终态传播性（蔓延性）条件从 s岀发读入某个a和从t岀发经过某个a并且经过某个b到达的状态等价。就是相同。DFA的最小化一例子，第一步都是固定的。分成终态和非终态k1= C,D,E,F 组成，一个由非终态 k2= S,A,1 .将M的状态分为两个子集一个由终态B组成，2 .考察S,A,B 是否可分.aSBA因为A经过a为S, B,A,到达C属于k1.而S经过a到达A属于k2.B经过a到达A属于k2，所以K2继续划分3 .考察S,B是否可再分:B经过b到达D属于k1.S经过b到达B属于k2，所以S, B可以划分。划分为S,BD,E,F 是否可再分:4 考察C,因为C,D,E,F经过a和b到达的状态都属于C,D,E,F=k1所以相同，所以不可再分:5. C,D,E,F 以D来代替则，因为 CDEF相同，你也可以用