形式语言与编译（三）NFA 、e-NFA to DFA

这三种自动机定义的语言是同一种语言，都是正规语言

DFA定义的语言可以被NFA接受；NFA定义的语言可以被DFA接受

每一个NFA都能转化为等价的DFA

每个DFA都是NFA的特例

观察：NFA中每一个状态映射为一个状态子集

IDEA: 每个状态子集映射为单一的DFA状态 (子集构造方法 subset construction theory)

包含原来状态中终止状态的状态定义为新的终止状态

有了原始的NFA的状态，构造的对应的DFA的子集状态可能有\(2^n\)个。所以我们可以把所有的可能状态列出来，然后连线就可以了。看看每一个状态都有可能去哪些状态。反正所有的状态已经列出来了。。。(妙！！！)

记得最后判定这些列出来的子集含不含终止状态！！！

使得每一个NFA的状态子集DFA都有唯一的状态与之对应

注意：有时候对于所有已经划分好的NFA状态子集进行连线时发现，会有一些状态不可达，也就是这些状态与其他状态彼此孤立。因此需要删除不可达状态。也就是下面所示：

删除不需要的（不可达）状态，然后就得到真正的DFA，上图完了还得标上终止状态。

NFA到DFA的子集构造算法描述

算法总结：

最后可以对状态集合命名，比如上面的\(\{q_0\}\)命名成A

但是当状态数比较大的时候，比如状态数为10，那么是不是意味着要生成\(2^{10}\)个子集合，但是最终却要删去这\(2^{10}\) 中的绝大多数。感觉白白创建，白白浪费资源

优化方法：

为避免枚举幂集，采用"惰性创建状态的方法"。

其实就是不经过上面图中中间表格，而是由第一个表格直接生成具有可达状态的第三个表格，省去了中间巨量无用幂集的创建。直接生成最后有用的可达状态

本着按需引进 的目的

不清楚表格一共有多少行，我们一行一行分析。这就和子集构造法不一样了，子集构造法是一下子把这个表有多少行，每一行是什么都先知道，然后连线的

拿着刚开始的初始状态，一行一行往下进行；当有新状态产生的时候，把这个新产生的状态添加到我们需要确定的可达状态子集 ，一直到没有新状态产生。

随着处理过程，需要引进状态，我们再引进。

这个动态构造算法比子集构造法要好。节省时间、空间、还不用删去不可达状态。实验课推荐这个方法！！！

定理：由NFA通过子集构造法或者动态构造法得到的DFA，和我们原来的NFA，这两个自动机是等价的，有\(L(DFA)=L(NFA)\)

证明过程可以由归纳法。也就是前面讲的扩展转移函数 和 **串=串+一个字符 **

但是！！！我们也有这个担忧一般来说DFA的状态数要比NFA大得多

其实，\(\varepsilon\)就是不接受任何字符可以转换状态的。\(\varepsilon\)增加了状态机的灵活性

感觉有个\(\varepsilon\)被接受的概率显著增大了，几乎能从40%到93%！！！，就是这么神乎其神

超级灵活，但是也有不接受的，比如上面的11，还是不能接受

例题：构造NFA，接受这样一个串，偶数个0或者奇数个1。（两个自动机用\(\varepsilon\)连接就行）就是用来处理OR的

带\(\varepsilon\) 的NFA就是做题方便，还是帮助人理解、思考。正真在计算机中处理，还是要变成DFA。可以先知道带\(\varepsilon\) 的NFA与DFA处理能力是一样的

只有DFA是面向机器的，NFA、\(\varepsilon\) -NFA是面向人的(或者说是面向做题的(滑稽！)) 最终在机器中都得落实到DFA中。但是一般问题也不是说不能用DFA做，是可以做的，就是比较麻烦！！！

由于\(\varepsilon\) 弧比较*，因此引入团或者叫闭包的概念。就是说它们非常相似，是一伙的。

\(\varepsilon\) -cloure of a state q 我们也叫做 E-CLOURE(q).就是q状态通过\(\varepsilon\)连接起来的那些状态的集合

消除\(\varepsilon\) 有如下几个规则

通过\(\varepsilon\) 能够到达最终状态的状态都是最终状态
通过一个终结符前前后后有多个\(\varepsilon\) ，可以将这些合并成最后只有一个终结符 \(\varepsilon\)\(\varepsilon\)\(\varepsilon\) a\(\varepsilon\)\(\varepsilon\)\(\varepsilon\)\(\varepsilon\) -> a

算法思想：\(\varepsilon\)-NFA 转化成 NFA 再转化成 DFA

\(\varepsilon\)-NFA =NFA = DFA 三者的功能是一样的

证明略

都是接受正规语言RE