自动机理论（Automata）

自动机的本质是一个有向图，节点为状态编码，而边为输入符号，自动机根据当前节点和对应的输入符号寻找状态转移，从而在进入到不同状态时触发对应动作。而根据自动机的确定性与否，又可以划分为确定有限自动机（DFA）和非确定有限自动机（NFA）。对于DFA而言，每个状态对于一个输入，有且仅有一个目标状态，即任意节点A连出的边中，不会有重复的符号。而对于NFA，则可以有多个不同的目标状态，即一个节点，可以有多个连出边都是同一个符号。

DFA和NFA其实功能上是等价的，因为任意NFA，都可以通过子集构造法来转换到一个对应的新DFA上，当然，往往新构造的DFA会比原NFA大很多，甚至有时是指数增长的。