确定的有限自动机的表示

确定的有限自动机： Deterministic Finite Automata，简称DFA。 一个确定的有限自动机是个五元组: (S，∑，f，s_{0， Z)，其中：}

（1）S是一个有限集合，它的每个元素称为一个状态。

（2）∑是一个有穷字母表，它的每个元素称为一个输入字符。

（3）f是SX∑ →S上的单值部分映像。f(A, a)=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。

（4） s₀ ∈S，是唯一的一个开始状态。

（5）Z是非空的终止状态集合，Z⊆S。

状态转换图：简称为转换图，是一个有向图。DFA中的每个状态对应转换图中的一个结点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f(A，a)=Q，则该有向弧从结点A出发，进入结点Q，字符a是弧上的标记。

状态转换矩阵：就是用一个二维数组表示确定的有限自动机。

例如：确定的有限自动机M1= ({s₀，s₁，s₂，s₃}， {a，b}，f，s₀，{s₃})，其中f为：f(s₀，a)=s₁，f(s₀，b)= s₂ ， f(s₁，a)= s₃ ， f(s₁，b)= s₂ ， f(s₂，a)= s₁ ， f(s₂，b)= s₃ ， f(s₃，a)= s_3；