编译原理：从正规式到NFA、NFA到DFA及DFA最小化详解
编译原理：从正规式到NFA、NFA到DFA及DFA最小化详解
编译原理中的正规式到NFA、NFA到DFA以及DFA最小化是理解词法分析器和语法分析器的基础。本文将详细介绍这三个转换过程，帮助读者掌握编译原理的核心概念。
1. 前言
整体转换过程分为三步：
- 把正规式转换为NFA（非确定有穷自动机）
- 将NFA通过“子集构造法”转换为DFA
- 最后把DFA通过分割法进行最小化
2. 正规式转换为NFA
通过反复运用下图所示的转换规则，可以将正则表达式转换为有限自动机：
- 对于 ε，构造为
- 对于a（输入的字符以a为例），构造为
- 对于 a | b，构造为
- 对于 ab，构造为
- 对于 a*构造为
例如：
3. 子集构造法确定DFA
假设我们有一个NFA如下：
将上图根据子集构造（详细方法见编译原理随笔）法转换为DFA，如下图：
这个表是从NFA到DFA的时候必须要用到的。第一列第一行I的意思是从NFA的起始节点经过任意个ε所能到达的结点集合。
Ia表示从该集合中的每个结点开始经过一个a所能到达的集合，经过一个a的意思是可以略过前后的ε，同样Ib也就是经过一个b，可以略过前后任意个ε。
至于第二行以及后面的I是怎么确定的，可以根据上一行中Ia,Ib的值确定。第一行Ia{2,4,6,7,9}，Ib{5,6,7,8,9,}，故I的值可取{2,4,6,7,9}，
{5,6,7,8,9,}。可以发现上面的Ia和Ib哪个还没出现在I列，就拿下来进行运算，该列对应的Ia和Ib的值可根据子集构造法推出。如果还不太明白，
仔细观察上图你会发现I中的几个值都在Ia和Ib中出现了，而且是完全出现。
这步做完以后，为了画出最后的DFA，那么肯定得标出一些号来，比如1，2，3。或者A，B，C，我一般标的方法是先把I列全部标上 1，2，3 递增。
然后看1表示的集合和Ia和Ib中的哪个集合一样，就把那个集合也表示为1.继续向下做。最后会得到这样一个表格。如下图：
至此，就可以表示出DFA了。就对照上面那个表，从0节点开始经过a到1经过b到2，就这样画就行了。最后的DFA如下图，见下图：
双圈的表示终态，这个是怎么来的呢。去看看图4，会发现有些项之前有双圈标志，这个是因为在NFA图2中，9为终态，所以所有包含9的集合都被认为是终态集，改成1.2.3.。方便画节点后就需要把这些点作为终态了。
4. 分割法实现DFA最小化
最小化就是寻求最小状态DFA
最小状态DFA的含义:
1、没有多余状态(死状态)
什么是多余状态？
从这个状态没有通路到达终态，即S1
从开始状态出发，任何输入串也不能到达的那个状态，即S2
2、没有两个状态是互相等价（不可区别）
两个状态s和t等价的条件：
兼容性（一致性）条件——同是终态或同是非终态
传播性（蔓延性）条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里。
例如：
假定s和t是M的两个不同状态，如果从状态s出发读出某个字w而终止于终态，同样，
从状态t出发读出某个字w而终止于终态，我们称s和t等价。
DFA的最小化—例子，第一步都是固定的。分成终态和非终态：
1．将Ｍ的状态分为两个子集一个由终态k1=｛Ｃ，Ｄ，Ｅ，Ｆ｝组成，一个由非终态k2=｛Ｓ，Ａ，Ｂ｝组成。
2．考察｛Ｓ，Ａ，Ｂ｝是否可分。
因为Ａ经过a到达C属于k1.而S经过a到达A属于k2。B经过a到达A属于k2，所以K2继续划分为{S，B}，{A}。
3．考察｛Ｓ，Ｂ｝是否可再分：
B经过b到达D属于k1。S经过b到达B属于k2，所以S，B可以划分。划分为{S},{B}
4．考察｛Ｃ，Ｄ，Ｅ，Ｆ｝是否可再分：
因为Ｃ，Ｄ，Ｅ，Ｆ经过a和b到达的状态都属于｛Ｃ，Ｄ，Ｅ，Ｆ｝=k1所以相同，所以不可再分。
5．｛Ｃ，Ｄ，Ｅ，Ｆ｝以｛Ｄ｝来代替则，因为CDEF相同，你也可以用C来代替。无所谓的最小化的DFA如图：
5. 总结
本文详细介绍了编译原理中正规式到NFA、NFA到DFA以及DFA最小化的转换过程。这些内容是理解词法分析器和语法分析器的基础，对于计算机科学专业的学生和相关领域的从业者具有重要的参考价值。
注：本文部分内容参考自“正规式—>最小DFA详解 - 码小兔 - 博客园”，在此表示感谢。