自动机
自动机，顾名思义，就是能够自动完成事情的“机器”。但是为什么要用自动机，什么又叫“自动”呢？
我们看看普通的处理方式，简单的就是if了，例如：判断某字符串是否是“Hello,Word”,我们都会这么写：
if（str == “Hello,Word”）
普通的比较可以满足大部分的场景，但对于正则表达式这种比较的话，普通的if就完全不能满足了，例如a*b|c，可以是如下字符串：
ab
aab
aaaab
c
………….
这种情况我们不可能采用普通的if来判断了，因为不可能穷举所有的字符串。所以我们要另辟蹊径，自动机就应运而生了。
我们这里讲的自动机有两个：一个是确定有限自动机，又叫DFA；一个叫不确定有限自动机，又叫NFA。由于自动机的核心就是通过“状态”和“状态变迁”实现的，所以自动机又叫状态机。
1) NFA
为什么叫不确定自动机呢？就是因为存在“不确定性”了。
什么不确定呢？就是一个输入可能对应多个状态转换，所以就不确定了。
通过NFA来识别字符串的过程很简单，即每输入一个字符，都判断当前的状态集中哪些状态上有此字符的转换，然后把所有转换后的状态又记录下来，依此循环，直到字符输入结束或者状态机结束。
不知道大家有没有发现，NFA的识别过程其实非常类似将NFA转换到DFA的子集构造算法的过程。如下图：
NFA识别过程，假如识别aabb
（1）初始状态：0，1，2，4，7
（2）输入a，转换到如右的状态：3, 6, 7, 1 , 2 ,4,
（3）输入a，转换到如右的状态：8, 3, 6 , 7, 1, 2, 4
（4）输入b，转换到如右的状态：9, 5, 6, 7, 1, 2, 4
（5）输入b，转换到如右的状态：10, 5, 6, 7, 1, 2, 4
由于此时已经没有输入字符了，而且最终状态10也包含进来了，因此aabb就接受了。
NFA->DFA的子集构造算法：
（1）初始状态：0，1，2，4，7（第一个子集）
（2）输入a，转换到如右的状态：3, 6, 7, 1 , 2 ,4（第二个子集）
（3）输入a，转换到如右的状态：8, 3, 6 , 7, 1, 2, 4（第三个子集）
………………………..(依次类推)…………………………………………..
2) DFA.
介绍到这里，相信大家都已经明白DFA的概念了。
所谓确定，就是指一个输入只能对应一个转换。
而DFA来识别字符串就更简单了，由于转换是确定的，所以直接将输入字符输入进行转换即可。
3) NFA和DFA比较.
复杂度：当然是DFA高了；
速度：当然是DFA快了
到这里正则表达式系列相关知识也就结束了，当然我在这里知识提纲挈领，让大家能够从整体上把握这些相关的东东，不至于上来就被一堆术语和名词弄晕了，同时也把关键的地方点了一下，希望能够起到让大家茅塞顿开的效果。
当然更加详细和深入的研究还需要各位自己深入钻研了，推荐《编译原理（龙书）》和《精通正则表达式》两本书。
