有穷自动机
为了实现对于正规式（可理解为正则表达式）的识别，我们提出了有穷自动机理论，有穷自动机接受正规式的定义符，并不断的识别符号，移动到新的状态，如果出现了识别错误就会报错。
有穷自动机包含确定的有穷自动机（DFA），和不确定的有穷自动机（NFA）。两者的主要区别在于，在同一个状态时，是否通过同样的符号输入能达到不同的状态。如果能就是不确定的，反之就是确定的。另外：NFA还可以接受空字串已达到不同的状态。
三个主要的算法
这其中有三个主要的算法：
正规式 => NFA Thompson算法
这个算法使用了一些模版去对应正则表达式中的符号，只要记住模版，就能推出相应的NFA。
继续阅读 »