只讲方法不讲原理。参考龙书二

不知道为什么今天的老是不能上传图片，然后就做成pdf了，http://download.csdn.net/detail/dantangfan/6367655)

用了很久的正则表达式，都不清楚里面的机理和机器的运作方法。这里学习了正则表达式到NFA（Nondeterministic Finite
Automata，不确定的有限状态自动机）再到DFA（deterministic Finite Automata，确定的有限状态自动机）的转换过程。

如正则表达式：

相应的NFA

相应的DFA

从正则表达式到NFA：

NFA的几个组成部分：

1、一个有限的状态集合S，比如说上面的4个状态0、1、2、3，状态也可以有冗余，不过能简化肯定简化更好；

2、一个输入符号集合∑，即输入字母表（input alphabet），要记住，我们假设了代表空串的ε不是∑中的元素，要是一个字符串有不属于∑中的元素，那么肯定不能走完该NFA；

3、一个转换函数（transition function，也可以称为迁移函数），为每个状态和∑∪{ε}中的每个符号都给出了相应的后继状态（next state）的集合；（在生成NFA或者DFA的时候有同样转换函数的状态是可以合并的）

主要就是上面3个组成部分，另外，有两种特殊的状态：

1、一个状态S0被指定为开始状态，或者说是初始状态，也就是最开始接受输入字符的状态，有且只有一个；

2、S的一个子集F被指定为接受状态或者是终止状态集合。（注意，可以包括初始状态）

几个基本概念

对于任意输入空元素ε的NFA有

对于任意输入a的NFS有

假设N(s)和N(t)是正则表达式s和t的NFA

a.假设r=s|t，那么r的NFA是

b.假设r=st，那么r的NFA是

c.如果r=s*，那么r的NFA是

那么我们就可以一步一步的得到最终结果

从NFA到DFA

几个基本概念

设D和T是NFA的状态子集.

ε―closure(D)={t|从状态s∈D出发,通过标记为ε的路径到达状态t}(ε―closure(D))

move(T,a)={t|从状态s∈T出发,经过a转换到达状态t}

那么对于上面的NFA有

那么根据龙书上的算法

可以得到以下图表

然后可以根据图表画出有向图

这个时候还需要对图进行化简，也是最难理解的部分。基本思想就是把ABCD划分成最小集合。

对于任意一个图首先，可以把最终状态分出来{A,B,C,D},{E};

然后对ABCD可以根据每次的输入进行判定。比如输入a时，他们的最终结果都是B，但是输入b时，ABC的结果都还在集合{A,B,C,D}内部，而D的结果为E，超出了本身集合。所以D是跟ABC不同的，继续划分成{A,B,C}{D}{E}.

用同样的方法，可以最终将集合划分成{A,B}{C}{D}{E}.

然后简化有向图，得到最终结果