我觉得大学时候编译原理我学的还是挺明白的了，当最近因为工作需要用到编译原理这块的知识，好尴尬，全部不记得了！其实这个结果不出乎意料，因为学校的教育是教与背，学生们很少真正理解知识，也很难真正明白如何去应用，时间久了当然全部忘记。算了，不说了，搞的像个愤青。。。

痛定思痛，我决定静下心来再次学一遍、去真正理解，顺便结合需求使用场景，这个过程很美妙，而且保证未来这些知识点不再会轻易从脑海里流逝。

在此声明，本文记录了相关的知识点和举例，以帮我未来快速勾起回忆、梳理知识点，目的是未来需要时看上一眼我就全想起来了。本文不适合新手来读，因为里面没有深入讲解原理，也没有硬性的概念。如果你希望随时查看NFA和DFA的相关知识点，欢迎阅读本文，它可以帮助有相关知识背景的同学快速回顾。

FA——finite automata，有穷自动机，是描述机器特定类型算法的数学方法，有穷自动机可用作描述在输入串中识别模式的过程，因此可以被作为构造扫描程序。FA作为一种识别装置，它能准确地识别正规集。
DFA——deterministic finite automata，确定的有穷自动机。
NFA——nondeterministic finite automata，不确定的有穷自动机。

一个确定的有穷自动机DFA，可以用五元组M表示，M=（K，Σ，f，S，Z）
1. K是一个有穷集，它的每个元素称为一个状态。
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表。
3. f是转换函数，是在 K × Σ → K 上的映射，即如 f(ki, a) = kj (ki∈K, kj∈K)。即当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态。
4. S ∈ K 是唯一的一个初态。
5. Z ⊆ K 是一个终态集，即结束状态。

例如，DFA M =({s0, s1, s2}，{a,b}, f , s0 ,{s2} )

状态转移函数：
f(s0, a) = s1
f(s0, b) = s2
f(s1, a) = s1
f(s1, b) = s2
f(s2, a) = s2
f(s2, b) = s1

状态转换图：

状态转换矩阵：

一个不确定的有穷自动机NFA，同样用五元组M表示，M=（K，Σ，f，S，Z）
1. K是一个有穷集，它的每个元素称为一个状态。
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表。
3. f是转换函数，是在 K × Σ^* → K 上的多值映射，Σ^*代表接受空字符。
4. S ⊆ K 是初始状态集（注意和DFA不同）。
5. Z ⊆ K 是一个终态集，即结束状态。

例如，DFA M =({s0, s1, s2},{a,b}, f , {s0, s2}, {s1})

状态转移函数：
f(s0, a) = s2
f(s0, b) = {s0, s2}
f(s1, b) = s2
f(s2, b) = s1

状态转换图：

状态转换矩阵：

正规表达式两个重要的等价性：
1. 如果R是字母表 Σ 上的一个正规式，则必然存在一个NFA M，使得L(M) = L(R)。
2. 对于任意一个NFA M，一定存在一个DFA M’与其等价，即L(M) = L(M’)。

正规式 --> NFA

NFA --> DFA
状态集合I的ε_闭包
设I是FA M的状态子集，则以下状态属于ε_CLOSURE(I)：
1. 若s_i ∈ I，则s_i ∈ ε_CLOSURE(I)
2. 若s_i ∈ I，则对从s_i出发经过任意条ε通路所能到达的状态s_j，都有s_j ∈ ε_CLOSURE(I) 。

定义I_a = ε_CLOSURE(J)，其中：
I = {s₁, s₂, …, s_n}
J = f(I, a) = f(s₁, a) ∪ f(s₂, a) ∪ … ∪ f(s_n, a)

如上图，我们可以得到：
1. I={1}, ε_CLOSURE(I) = {1, 2}
2. I={5}, ε_CLOSURE(I) = {5, 6，2}
更深入的，I={1, 2}，可以得到：
J = f(I, a) = f({1, 2}, a) = ε_CLOSURE(5, 3, 4) = {2, 3, 4, 5, 6, 7, 8}

按照这一规则，我们可以将NFA转换成DFA。

转换后的矩阵为：

最终如图所示：

DFA --> 最简DFA

转换方式如下：
1. 首先将DFA的状态集按照终态与非终态分为两个子集，形成初始划分H。
2. 对每个子集G进行变换：
a) 把G划分为新的子集，使得G的两个状态s1和s2属于同一子集,当且仅当对任何输入符号a,状态s1和s2的后继状态都属于同一子集。
b) 用G划分出的所有子集替换G，形成新的划分H'
3. 如果H' == H 执行4，否则令H = H'，重复执行。
4. 划分结束后，一个子集只对应一个状态，作为代表状态，删去其它一切等价状态，并将对应的弧射向这个代表状态。

举个例子，如下图是一个DFA图：

1. 初始集合划分为，集合A = {0, 1, 2,}，集合B = {3, 4}。
2. 由于1a，2b落在了集合B中，因此集合A需要继续划分，为{0}{1}{2}。
3. 检查集合B，由于3a，3b，4a，4b都落在了本身集合B中，因此不进行划分。
4. 最终划分结果为{0}{1}{2}{3, 4}，重命名为0/1/2/3。
5. 得到新的最近DFA。

至此，关于 NFA 和 DFA 的相关知识点，总结完毕！