有限自动机

有限自动机：

百度百科:有限自动机

通俗来说就是一个抽象的数学模型，由一个初态，若干个中间态和若干个终态组成，在每一个状态下，接收到输入信息后转移状态到可以转移的下一个状态，如果状态到终态则可以终止(程序上来说则是可以退出)。这种抽象的数学模型称为有限自动机。例如这是某个有限自动机的状态转移图：

其中q0为初态，当q0状态时，接收到条件 a 则转移状态到q1，接受条件 b 转移状态到q2。

q1为中间态，以单圈标识，在q1状态时，接收到条件 a 或者 b 则转移状态到q1(即保持状态不转移)。

q2为终态，以双圈标识，在q2状态时，接收到条件 a 时可以转移状态到q2(保持状态不转移)，接受字符 b 时转移状态到q1，并且可以终止。

有限状态机是一个处理信息的简单机器。通过对文本字符串 T 进行扫描，找出模式 P 的所有出现位置。给它输入一个模式串，会得到一个YES或者NO的结果。

它只对每个文本字符检查一次，并且检查每个文本字符时所需的时间为常数。因此，在模式预处理完成并建立好自动机后进行匹配所需要的时间为 O(n) 。

一个有限自动机 M 是一个 5 元组（Q，q， A， ∑，δ）

例如，对于0101111001串构建一个判断1的个数是否为偶数个的有限自动机

最后结果为红色区域，表明这个是一个偶数。

又例如，对P="ababaca"构建有限自动机，如以下a图所示

对于每一状态，会根据接受字符的情况来变化。

如b图所示，左边坐标表示状态；右边表示模式串P的匹配情况；上方表示输入情况。

例如第一行：当状态为0时，此时匹配的是P串的字符a。当输入为a时，转入状态1；输入为b，c时，转入状态0.

如c图所示：表示的是文本串T的匹配情况。在文本串之下的是状态的情况，当状态为7时，匹配成功。

P：模式串（要找到的串）

∑：有限的字母表（对于一个串，我们应该知道其出现了多少种字母，如aabcc的字母表为a、b、c）

k：根据状态q和输入的字符的不同，所设置的该转移到的状态

双层for在做的事：对于每一个状态q，又对于每一个字母表中的字符，k为最可能的最大状态（要么是当前状态q+2，要么是长度m加1，注意这里多了1），然后k自减，直到Pk是Pq合上字符a的 后缀 时，设置状态函数状态。（参考KMP找最长公共前后缀）

简单来说，就是对于文本串的每一个字符，不断更新当前状态q，当q为模式串长度m时，说明找到串了。

有限自动机。图灵机中，控制读写头动作的控制器是有限自动机。控制读写头动作的控制器是一台时序机，即有限自动机，具有有限个内在状态，包括初始状态和终止状态。控制器内存有 *** 作程序，即指令序列，用来驱动存储带左右移动和控制读写头的 *** 作。

---