有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机有两类：确定的有限自动机和不确定的有限自动机。
1.确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机DFA M是个五元组M=(S,Σ,f,s0,Z)，其中：
S是一个有限集，其每个元素称为一个状态。
Σ（xigema）是一个有穷字母表，其每个元素称为一个输入字符。
f是S✖Σ→S上的单值部分映像。f(A,a)=Q表示当前状态为A、输入为a时，将转换到下一个状态Q，称Q为A的一个后继状态。
s0∈S，是唯一的一个开始状态。
Z是非空的终止状态集合，Z⊆S。
一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。
状态转换图是一个有向图（双圈表示的结点是终态结点）。DFA中的每个状态对应转换图中的一个结点，DFA中的每个转换函数对应图中的一条有向弧，如转换函数为f(A,a)=Q，则该有向弧从结点A出发，进入结点Q，字符a是弧上的标记。
2.不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定的有限自动机的区别如下：
f是S✖Σ→2^S上的映像。对于S中的一个给定状态及输入字符，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
有向弧上的标记可以是字符串。
显然，DFA是NFA的特例。
网友评论