正则表达式所使用的理论模型就是有穷自动机，其具体实现称为正则引擎（regex engine）。用正则表达式处理字符串，首先需要生成自动机（“编译”正则对象）；之后无论输入什么字符串，正则引擎都只需要老老实实地在状态之间游走。
图8-2显示了正则表达式a(bb)+a对应的自动机。
[图片上传失败...(image-cd0daa-1545311176685)]
在这台有穷自动机中，s0、s1…、s4是各个状态，s0为开始状态，s4为最终状态；转移函数很直观：比如当前状态是s0，输入字符a，则转移到s1；如果当前状态s0，输入的不是a，则直接退出。这也很好理解：该正则表达式只能匹配以a开头的字符串，否则不匹配。
图8-3说明了这台有穷自动机对字符串abbbba的处理过程。
[图片上传失败...(image-d8d5d3-1545311176685)]
在经历了一系列对状态转移之后，字符串abbbba处理完毕，自动机停留在最终状态上，也就是说，字符串abbbba可以由正则表达式a(bb)+a匹配。
同一个正则表达式对应的有穷自动机不止一台，可能是若干台，这些有穷自动机是等价的。同样是a(bb)+a，它可以对应到如下对两台完全等价对有穷自动机。
[图片上传失败...(image-9e26f2-1545311176685)]
仔细观察发现，第二台自动机有些奇怪，在输入ab之后，再输入b，它所处第状态是不确定的：可能在s1，也可能在s3。但是输入a(bb)+a能匹配的字符串，它确实可以抵达最总状态s4.
图8-5所示的自动机看起来更加奇怪，但它仍于a(bb)+a是完全对应的。
[图片上传失败...(image-4ae298-1545311176685)]
在状态s3，即便没有输入任何字符，也不会停下来，而是凭空转义到s1。也就是说，在某个时刻，自动机到底处于s3还是s1，这时不确定的！但是对于这种不确定性，并不会影响自动机对于正则表达式a(bb)+a到匹配。也就是说，这台自动机与之前的两台自动机是完全等价的。
根据状态的确定与否，一般我们会把有穷自动机（正则引擎）分为两类：一类是确定型有穷自动机（definite finite automata，简称DFA），在任何时刻，它所处的状态是确定无疑的；另一台是非确定型有穷自动机（non-definite finite automata，简称NFA），在某个时刻，它所处的状态可能是不确定的。
图8-6把上面的三台自动机做了分类，第一台是DFA，另两台是NFA。
[图片上传失败...(image-c82872-1545311176685)]
可以证明，DFA和NFA之间存在等价关系：也就是说，每一台DFA都可以等价转换为一台NFA，反过来也成立（具体证明过程很复杂，这里略去，有兴趣可自行查阅计算理论相关资料）。
比较正则表达式a(bb)+a和这三台自动机，会发现NFA构造起来更直观，实际上这是普遍规律：从正则表达式出发，构造NFA的难度要小于DFA。但是正如之前说的，DFA在任意时刻必定处于某个确定的状态，而NFA可能处于若干状态之中的一个，所以，如果使用NFA，就必须保存所有可能的状态，并且在某种状态不可行时“回退”到之前保存的状态，这就是正则表达式匹配中的重要概念：回溯。
网友评论