NFA转DFA【编译原理】

       NFA转DFA的算法在编译原理的课本上有，当时看了好多遍都不懂。现在我通俗的说一下究竟是怎么转化。用一个例子来说明怎么实现NFA转DFA与DFA简化。

一个NFA如图所示：

构造转化表的算法如下：

1、 从NFA的初始状态开始，把从初始状态跳空能到的状态以及该状态跳空能到的状态，设为T0，放到表格的第二行第一列，直到没有新的状态能够由已得到的状态跳空得到为止。T0={ 0,1,2,4,7 }。

2、第二列的状态分别对应NFA图来分别跳a，跳a后的状态填在第二列（Ia列）。第二行第二列由第二行第一列的T0状态跳a得到。T0集合的元素跳a可得到的元素{3,8}，以及该元素{3,8}跳空可得到的元素设为T1，放到表格第二行第二列。 T1={1,2,3,4,6,7,8}。

3,、跳b的情况也与跳a的情况类似，把第二步的跳a改成跳b即可。

4、经过2、3步得到的状态分别填在第一列，用2-3的步骤生成经跳a、跳b得到的状态分别填在Ia列Ib列。

5、重复2-4步。

6、当表中的所有状态都出现在第一列时说明表的构造完成。

构造完成的表如下：

    含0的为初态，含10的为终态，重新命名各个状态，令T0、T1、T2、T3、T4用0、1、2、3、4分别表示，该DFA的状态转换图如图所示：