子集构造法NFA转换成DFA

教材《编译原理》（龙书）第2版

关于这部分，教材在P94页有说明，但是我觉得不容易理解，下面通过两个例题来理解一下。

例题一：

这一题比较简单，我们直接从答案找解题方法

第一步：要根据NFA画出这个表格，可能有些模糊，表头分别为I，Ia，Ib，状态（是对I这一列自定义的状态名称）

下面我们来说一下第一行的三项如何得出：（S就是开始状态）

 先以S开始，经过任意个ε得到的结点就是第一个I，这道题就是{X, 1,2},

然后将{X，1,2}中的每一个字符经过a (中间可以有ε)后得到的结点加起来，

X的Ia={1,2}, 1的Ia={1,2}, 2的Ia是空集，所以这一行的Ia={1,2}。

后面的Ib也是一样，只不过是经过b后得到的结点的集合.

也就是说I的第一行第一列{X, 1,2}，是从开始符号经过ε得到的集合，而Ia,Ib是集合中每个结点分别经过a,b得到的集合的并集。

第二行的第一列I，是第一行的Ia，如果仔细观察，就可以发现：第一列都是将前面的Ia和Ib作为I计算新的Ia和Ib。

当然要注意重复的状态集合，就没有必要再作为I写一次了。

直到把所有的新状态都作为I写一遍，这个表就完成了。

第二步：根据表格画出DFA

将这些集合依次标号，这道题是{X，1,2}为X，{1,2}为1, {1,2,3}为2，{1,2，Y}为3，根据上面那个表就可以把图画出来了。

关于箭头指向和箭头的值，都要从每一行的三项来看，比如第一行，如果把集合换成自定义的状态编号就是

I       Ia       Ib

X      1       2

意思就是X经过a到达状态1，X经过b到达状态2。

并且由于Y在NFA中是一个接受状态，在表格的状态3中也有Y，所以3是接受状态。

例题二：

将下图NFA转换成DFA

这一个NFA中不含有ε，一开始我也不知该怎么做，和上一题有一些小区别，是我同学给我讲的，如果不对，就不要借鉴了。

区别就在于，每一个集合不再是把所有经过a,b的结点都写入，而是只写第一个经过的结点，例如第一行的Ib，从A经过b的所有结点事{E,B}，但是只记录了一个E。

最后的结果是：

--------------------- 
作者：elice_ 
来源：**** 
原文：https://blog.****.net/elice_/article/details/80550413