这三种自动机定义的语言是同一种语言，都是正规语言
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$-NFA 转化成 NFA 再转化成 DFA
$\varepsilon$-NFA =NFA = DFA 三者的功能是一样的
证明略
都是接受正规语言RE
原文：https://www.cnblogs.com/fennleo/p/13143575.html