词法分析备忘

构造最小DFA：

1. 构造NFA（课本上的构造法是不带ε边的，少了消ε的过程）
2. NFA->DFA
3. 最小化DFA

构造NFA：

连接、并、重复

NFA->DFA：

从初始状态集合{S}开始，跑所有字符集，若得到新的状态集则入队。

带有终结状态的集合仍然是终结状态。

对状态重新编号。

DFA的最小化：

1. 构造一个初始划分Π：终态集合，非终态集合。
2. 对Π重新划分，直到不能划分出新的Π。

划分：

对于Π中每一个组G，若G中的两个状态对所有符号两个状态转换后的状态都处于Π的同一个组中，则这两个状态划分后仍在同一个组。否则在两个不同的组。

重新编号组。含有初始状态的仍是初始状态，含有终结状态的仍是终结状态。

词法分析备忘

原文：http://www.cnblogs.com/zinthos/p/4167966.html