算法：正则表达式转NFA

从正则表达式到自动机的转换

• 正则表达式：简洁、精确地描述词法单元的模式

• 自动机：便于机器执行的计算模型

  • NFA：易于从正则式转换（空串跳转）

  • DFA：可由NFA转换，便于机器高效模拟执行。

  • DFA最小化，优化空间使用率

从正则表达式到NFA

基本思想：根据正则表达式的递归定义，按照正则表达式的结构递归地构造出相应的NFA

算法分为两个部分：

• 基本规则处理空串和单符号的情况

• 对于每个正则表达式的运算，建立组合相应NFA的方法

转换算法

基本规则部分：

归纳部分：

NFA到DFA（子集构造法）

基本思想：

• 目标DFA每个状态对应一个NFA状态集合（子集）

• 目标DFA状态之间的转换对应NFA状态集合之间的转换

• 理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个，但对于大部分应用，NFA和相应的DFA的状态数量大致相同

算法中使用到的基本操作：

I	Ia	Ib
0,1,2,4,7	1,2,3,4,6,7,8	1,2,4,5,6,7
1,2,3,4,6,7,8	1,2,3,4,6,7,8（出现过）	1,2,4,5,6,7,9
1,2,4,5,6,7	1,2,3,4,6,7,8（出现过）	1,2,4,5,6,7（出现过）
1,2,4,5,6,7,9	1,2,3,4,6,7,8（出现过）	1,2,4,5,6,7,10
1,2,4,5,6,7,10	1,2,3,4,6,7,8（出现过）	1,2,4,5,6,7（出现过）

第一行的I表示从NFA开始状态开始，只通过空串转换能到达的NFA状态集合。每一行的Ia表示枚举I集合中的每一个状态，仅通过一次a的转换可以到达的状态集合（如果通过a的转换到达的集合后还有通过空串转换能到达的集合，也算在Ia中），Ib同理。

如果Ia和Ib中的集合没有在I中出现过，则新起一行，将Ia和Ib作为新的I重复以上运算，直到所有的Ia和Ib都在I中出现过为止。

State	a	b
A	B	C
B	B	D
C	B	C
D	B	E
E	B	C

DFA状态数量的最小化

DFA状态越小，空间效率就越高。一个正则语言可对应于多个识别此语言的DFA，通过DFA的最小化可以得到状态数量最少的DFA（不计同构，这样的DFA是唯一的）。

状态的区分

如果存在串x，使得从状态s1和s2，一个到达接受状态而另一个到达非接受状态，那么x就区分了s1和s2。如果存在某个串区分了s和t，我们说s和t是可区分的，否则它们是不可区分的。不可区分的两个状态就是等价的，可以合并。

先将所有的状态划分为包含接受状态和不包含接受状态的两个集合：

初始划分为{A,B,C,D}和{E}，然后查找{A,B,C,D}通过a能够转换到的状态集合，如果该集合为{A,B,C,D}自身的子集，则可以合并，否则需要划分。

{A,B,C,D}通过a可以得到B，为子集，不需要划分；通过b可以得到{C,D,E}，不是子集需要划分，其中得到{C,D}的为{A,B,C}，得到{E}的为{D}，所以划分为{A,B,C},{D}。

接着处理{A,B,C}，B可以通过b得到D，所以需要再次划分为{A,C},{B}。

最后最小化为{ A, C }, { B }, { D }, { E }。