前言： 正则语言等价描述模型的转换
RG : (regular grammar) 正则文法
RE : (regular expression) 正则表达式
DFA : (deterministic finite automaton) 确定的有穷状态自动机
NFA : (non-deterministic finite automaton) 不确定的有穷状态自动机
ε-NFA : (non-deterministic finite automaton with ε-moves) 带空移动的不确定有穷状态自动机
RE转DFA
举例：（a|b）*abb
1. RE转NFA
拆分成(a|b)*和abb两个部分
1）构造(a|b)*
a. 对于a构造如下NFA:
b. 对于b的构造如下NFA:
c. a|b的NFA如图4所示
d. (a|b)*的NFA如图5所示
2） 构造abb，连接在图5所示NFA后面即可,最终结果如图6所示
2. NFA转DFA
1) NFA状态集上的操作
2） 图6中NFA转DFA
a) 开始状态A是ε-closure(0),即A={0,1,2,4,7}。
注意：状态0也是可以从自身出发经过ε到达的状态
b) NFA输入字母表为{a,b}
先计算状态A经过a所得到的集合B--ε-closure(move(A,a))
move(A,a)={3,8}
ε-closure（{3,8})）={1,2,3,4,6,7,8}
同理，计算状态A经过b得到的集合C:ε-closure(move(A,b)) =ε-closure({5})={1,2,3,6,7}
之后对集合B,C继续这个处理过程，最终使得这个DFA的所有状态都被加上标记,结果如图8所示
构造DFA结果如图9所示
3. DFA最小化
1) 初始分组
分为非接受状态组和接受状态组
{A,B,C,D}和{E}
2) 分割
因为组{E}只包含一个状态，不能再被分割了
另一个{A,B,C,D}
考虑输入a的时候，这些状态都转向B，因此使用以a开头的串无法区分这些状态
考虑输入b的时候，A,B,C转到组{A,B,C,D}的某个成员上，而D转向另一个组的成员E 上，因此将{A,B,C,D}分割成{A,B,C}和{D},得到新一轮状态组{A,B,C}{D}{E}
3) 再次分割
考虑组{A,B,C}
输入b时，A,C到达{A,B,C}中的元素，B到达另一个组中的元素D,因此分割后的状态组为{A,C}{B}{D}{E}
4) 分割完成
{A,C}无法再进行分割，所以最终的状态组就为{A,C}{B}{D}{E}
5) 最小DFA
从状态组中挑选出A,B,D,E作为对应组的代表，其转换函数如图10所示
最终的DFA如图11所示
参考
形式语言与自动机理论
编译原理（紫龙书）
