子集构造法NFA转换成DFA

左手的ㄟ右手 2022-05-22 21:05 159阅读 0赞

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

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

**目录**

例题一：

例题二：

PS：

评论区：

第一次：

第二次：

第三次：

第四次：

--------------------

## 例题一： ##

![20180602190225817][]

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

![20180602190310382][]

第一步：要根据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

![20180602191555946][]

将这些集合依次标号，这道题是\{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

![20180602202418482][]

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

![2018060220243731][]

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

最后的结果是：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VsaWNlXw_size_16_color_FFFFFF_t_70][]

## PS： ##

《编译原理》 是大三的时候考的一门课，这篇博客是2018年6月2日记录的，其中表述属于个人理解，有一些漏洞和不专业。说实话，当时只是为了应付考试，得到点赞之后也沾沾自喜，但是这个并不能作为别人研究学习的考证，最多像我一样应付考试。

不知这样说会不会被认为是那种“故意掩饰”，可是人家学习，然后对我提出质疑，我又不能就还心安理得的说我这就是我自己写着玩的，会耽误别人学习。总之，评论中大佬们的讨论，我也都仔细看过，虽然我已经无心再研究了，可我真的努力思考了，哭o(╥﹏╥)o，学渣一枚，别为难我，我真的看不懂专业的回复，说一声抱歉吧！

我把我看不懂的评论挂出来，因为评论区格式不好调，希望以后有大佬可以多加指教！嘿嘿！

## 评论区： ##

### 第一次：  ###

Ia 的求法有错，  
这一栏 “然后将\{X，1,2\}中的每一个字符经过a (中间可以有ε)后得到的结点加起来，X的Ia=\{1,2\}, 1的Ia=\{1,2\}, 2的Ia是空集，所以这一行的Ia=\{1,2\}。”  
 应该是这样： 设I是S的一个子集

①J为I中的某个状态经过一条a弧而到达的集合；

②ε-closure(I)：I∪\{s'|从s∈I出发经过任意条ε弧能到达s'\} ；

③Ia=ε-closure(J)

### 第二次： ###

其实，我也是刚学，在考软件设计师，自己看书看到这不太明白，就结合书上网查了查，其中有你这篇。  
说实话，一开始干扰了我好久。。。后来，发现你这表述有问题。  
软件设计师教程里面的不是以图表的形式解题的，结合你这种图表，会更好理解，我本来是想拍照的，但上传不了图片。这个东西首先要搞清楚ε-closure的定义。

### 第三次： ###

还有你这里的表述也有一点问题，

先以S开始，经过任意个ε得到的结点就是第一个I，这道题就是\{X, 1,2\}” 应该是  
 ①结合ε-closure的定义，  
X是开始节点，所以ε-closure（\{X\}）=\{X，1，2\}，此为初态q0，此时S中仅含初态\{X，1，2\}，  
然后  
Ia=ε-closure（q0，a）=ε-closure（\{X，1，2\}，a）=\{1，2\}，  
Ib=ε-closure（q0，b）=ε-closure（\{X，1，2\}，b）= \{1，2，3\}，  
Ia和Ib都不在S中，所以作为一个未标记的新状态加到S中，  
q1=ε-closure（q0，a）=ε-closure（\{X，1，2\}，a）=\{1，2\}，  
q2=ε-closure（q0，b）=ε-closure（\{X，1，2\}，b）= \{1，2，3\}，即加到第一列，作为第一列的第二行和第三行；  
假若在S中，就不需要添加到第一列中；  
第二行，就是  
q1=ε-closure（q0，a）=ε-closure（\{X，1，2\}，a）=\{1，2\}，  
Ia=ε-closure（q1，a）=ε-closure（\{1，2\}，a）=\{1，2\}，  
Ib=ε-closure（q1，b）=ε-closure（\{1，2\}，b）= \{1，2，3\}，  
此时的Ia和Ib都出现过了，所以不需要添加到第一列中；  
其他的以此类推，直到出现的S中不在出现未标记的状态。

### 第四次： ###

参考软件设计师教程（第五版）P78，和这篇文档吧[https://wk.baidu.com/view/edf6ab8bf524ccbff0218419?ivk\_sa=1023194j][https_wk.baidu.com_view_edf6ab8bf524ccbff0218419_ivk_sa_1023194j]

[20180602190225817]: /images/20220523/e83c485f36804710bf4139641ea5cb31.png
[20180602190310382]: /images/20220523/9260aef6e1a44fd1bd76eb94b7b99799.png
[20180602191555946]: /images/20220523/fccc4863356442089bfa724a01905125.png
[20180602202418482]: /images/20220523/1b427da068444bfc9443746a635e7fde.png
[2018060220243731]: /images/20220523/51e77614f82e41fa897bd1f8a30967cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VsaWNlXw_size_16_color_FFFFFF_t_70]: /images/20220523/3acff90fe84b4f47a344e7fbe0dfd8e0.png
[https_wk.baidu.com_view_edf6ab8bf524ccbff0218419_ivk_sa_1023194j]: https://wk.baidu.com/view/edf6ab8bf524ccbff0218419?ivk_sa=1023194j