通俗易懂理解有限状态自动机 FSA 的表示和原理

有限状态自动机（FSA），通常的作用就是用一种更加直观的方式来表示正则化表达式。

用一个例子来解释FSA（以下简称自动机）的有向图表达形式。我们把羊的语言（叫声）抽象为：baaa…！ 用正则化表达式可以表示为 / baa+！/，那么如何用FSA来表示羊的语言呢，下面看一张图。

上图就是用FSA表示的羊的语言，该FSA是用有向图来表示的，有向图由两个集合组成，节点的集合和连接两节点弧线的集合，节点表示状态，弧线表示进入下一个状态的条件。图中，q0表示初始状态，q4表示终极状态（或接收状态）。

我们知道有向图可以用矩阵来表示，状态转移表其实就是一个矩阵，同样以识别羊的语言为例子，如上图即为用状态转移表表示的FSA，同样有4个状态，0为初始状态，4为终极状态。

用有向图表示FSA时，其识别字符串的工作原理如下：把待识别的字符串放在一个“带子”（tape)上，该带子有若干单元格，每个单元格可以放一个字符，如下图：

FAS从初始状态q0开始，依次识别带子上的字符，若识别到的字符与此时状态到下个状态的弧上的字符相同，则进入下一个状态，相应的带子上的待识别字符也向后移动一个，这样依次识别，当到达终极状态（接收状态）时，识别完成。

下面分析一下不能够成功完成识别的情况。不能成功完成识别分为三种情况：

（1）在带子上识别到的字符与对应的弧上的字符不匹配，则不能进入下一个状态，识别失败。

（2）带子上的字符已经读完，依然没有读到整个需要的字符串。

（3）自动机在某一种非终极状态停住了。

出现这三种情况都称为FSA拒绝（reject）接收输入字符串，即没能成功识别。

依然是上面的例子，用状态转移表表示的FSA如下：

状态转移表中表示了识别的各种状态，它的工作过程简单来说就是从初始状态转移到终极状态。如图，从初始状态０开始，如果遇到ｂ，则进入下一个状态１，如果遇到ａ和！则表示转移失败，定义４为终极状态（用４后面加一个“：”表示），当转移到状态４时，识别成功。

以上只是对用状态转移表表示的FSA的基本原理的理解，我们知道之所以会想到用矩阵来表示有向图，很大程度上是为了方便用代码来表示相关的算法，同样的，用状态转移表也是为了方便用代码来表示FSA的工作过程，这里就不展开细述了，下一篇文章再来细讲一下用代码表示FSA识别字符串的算法，完成之后会把连接附在文末。

python实现简单的FSA： 链接: link.