Ⅰ 如题，编译原理中为什么要将NFA转化为DFA
对DFA来说，一个输入必然对应唯一的路径与结果，而这正是我们设计编译器所需要的。
如果从一个状态经过同样的一个输入可以通过两条或更多路径达到不同的状态，我们的编译器就会迷惑（不知道怎么办），只能通过穷举测试每个状态是否可行，而穷举算法的效率通常都很低下。
DFA的最简化是有固定算法的，NFA有没有我不知道，通常最简化之后的DFA要比NFA简单得多
Ⅱ 有穷自动机DFA&NFA (学习笔记)
有穷自动机（DFA和NFA）是一个识别器，它对每个输入字符进行识别和判断，以确定其能到达的最终状态或状态集。有穷自动机分为两类：不确定的有穷自动机NFA（Non-Deeterministic Finite State Automata）和确定的有穷自动机DFA（Deterministic Finite State Automata）。以红绿灯系统为例，红灯（R）、绿灯（G）和黄灯（Y）分别代表不同状态，以零售机为例，它可以接受五角和一块的硬币，但需要累计到至少3元才能进行选择。
在介绍DFA和NFA之前，先介绍一些基本概念。字母表（Alphabet）是符号的有限集合，如{a, b, ... , x, m}，字符串（String）是建立在字母表上的有限符号序列，如对于字母表Σ={a, b, c}，“ababc”是一个字符串，而语言（Language）是建立在字母表上的多个字符串的集合，如{ababc, ab, bc, ..}，句子（Sentence）是语言集合中的元素（字符串）的另一个称呼。
DFA是确定的有穷自动机，其状态间转换的公式为：状态 x 输入字符 --> 状态。DFA的定义包含5个部分：Σ（字母表），S（状态集合），s0（初始状态），F（最终状态），N（转换函数）。在DFA中，“确定”意味着对于一个输入字符，只有唯一的可能状态。例如，从状态S0读取符号0之后的状态为S1，即N (S0, 0) = S1，进一步读取符号1之后的状态为S2，即N (N (S0, 0), 1) = S2。重要定理指出，对于S中所有的状态s，所有Σ*中的字符串α，β，有N*(s, αβ) = N*(N*(s, α), β)。最终状态公式用于描述从任意一个状态，经过一个字符串到达的最终状态的所有可能情况。自动机等同是指如果两个自动机接受相同的语言，那么它们被认为是相等的。状态等同意味着对于所有的输入字符串w，有且只有N*(Sk,w) ∈ F 并且N*(Sk,w) ∈ F，其中F是最终状态的集合，注意非终止状态永远不可能与终止状态等同。状态消除是简化自动机的一种方法，包括等同状态消除和无法到达的状态消除。
NFA（不确定的有穷自动机）对一个输入符号，可能有两种或两种以上的状态。与DFA的主要区别在于DFA没有输入空串之上的转换动作，而NFA对于一个特定的符号输入，可能得到一个状态集。NFA的定义与DFA相同。对于输入字符串w，如果存在状态s属于F（最终状态集），满足R*(s0, w, s)，则w被自动机接受。存在定理指出，如果语言L被一个NFA接受，那么一定存在一些DFA也接受这一语言L。
总体而言，DFA和NFA是用于识别语言的自动机模型。虽然NFA在状态转换上具有不确定性，但可以通过转换算法将NFA转换为等效的DFA。DFA在确定性方面提供了更清晰的操作流程，而NFA则提供了更多灵活的路径选择。理解这两种自动机对于编译学习者来说是至关重要的。
Ⅲ NFA转DFA的子集构造(subset construction)算法
之前 学习编译原理的时候老师有讲过 子集构造法 ，当时我以为自己听懂了，信心满满。可是这两天我做了一些题目，发现自己实际上还是太嫩了，学习浮于表面。之后又重新看了龙书和虎书，对子集构造法有了更深层次的了解。特此发出一篇文章分享我的经验。
概念是我们学习编译原理的重中之重，虽然他很晦涩难懂，但我有必要将其放在最开始。
虎书的概念更偏向于理论化，我当时看的时候一头雾水，但是不要担心， 之后会一点一点解释的 。
首先 ，我们形式化定义 闭包如下：
现在 ，假设我们位于由 NFA 状态 组成的集合 中。从 中的状态出发，输入符号 ，将到达 NFA 新的状态集；我们称这个状态集为 ：
利用 能更形式化地写出 NFA 模拟算法。如果初态是 ，输入字符串是 ，则算法为：
有了 和 算法，就能构造出 DFA ， DFA 的状态 就是 。抽象而言，如果 则存在一条从 到 的标记为 的边。令 是字母表：
个人认为龙书的概念更加通俗易懂，但是由于没有数学公式的归纳，导致理论基础不扎实，有点慌。所以推荐两本书一起看。
首先，是概念：
接着，是算法：
很简单 ，如果开始于 的机器接收字符串 ，始于 的和始于与 接收的串相同 ， 并到达相同状态 ，且两个状态集 同为终态或者非终态 ，那么 是等价的。我们可以把指向 的连线全部指向 ，并删除 ，反之亦然。
NFA 转 DFA 知识总结就到这里，有什么问题请留言，有错误请批评指正，非常感谢您的阅读。
Ⅳ ！！编译原理DFA和NFA
DFA或NFA是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1; 这个程序对应了一个自动机。
对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。
画图出来就是 这4个状态作为顶点，并且有下面几条边
(0,0) --> (0,0)（自环）, (1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环
存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。
最经典体现自动机思想的算法就是KMP算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。