| 有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。
|
|
|
| （1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是一个五元组（S，Σ，f，s0，Z），其中：
|
|
|
|
|
| .Σ是一个有穷字母表，其每个元素称为一个输入字符。
|
|
|
| .f是S×Σ→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。
|
|
|
|
|
.Z是非空的终止状态集合， 。
|
|
|
| 一个DFA可以用两种直观的方式表示：状态转换图和状态转换矩阵。状态转换图简称为转换图，是一个有向图。DFA中的每个状态对应转换图中的一个节点，DFA中的每个转换函数对应图中的一条有向弧，若转换函数为f（A，a）=Q，则该有向弧从节点A出发，进入节点Q，字符a是弧上的标记。
|
|
|
| （2）不确定的有限自动机（Nondeterministic Finite Automata，NFA）。一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下：
|
|
|
| ①f是S×Σ→2S上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
|
|
|
|
|
|
|
| 任何一个NFA都可以转换为DFA，下面先定义转换过程中需要的计算。
|
|
|
|
|
| 若I是NFAN的状态集合的一个子集，定义ε_CLOSURE（I）如下：
|
|
|
| .状态集I的ε_CLOSURE（I）是一个状态集。
|
|
|
| .状态集I的所有状态属于ε_CLOSURE（I）。
|
|
|
| .若s∈I，那么从s出发经过任意条ε弧到达的状态s'都属于ε_CLOSURE（I）。
|
|
|
|
|
| 由以上的定义可知，I的ε_闭包就是从状态集I的状态出发，经ε所能到达的状态的全体。
|
|
|
|
|
| 假定I是NFAN的状态集的一个子集，a是Σ中的一个字符，定义：
|
|
|
|
|
| 其中，J是所有那些可从I中的某一状态节点出发经过一条a弧而到达的状态节点的全体。
|
|
|
|
|
| 设NFAN=（S，Σ，f，s0，Z），与之等价的DFAM=（S'，Σ，f'，q0，Z'），用子集法将非确定的有限自动机确定化的算法步骤如下：
|
|
|
| ①求出DFAM的初态q0，即令q0=ε_CLOSURE（｛s0｝），此时S'仅含初态q0，并且没有标记。
|
|
|
| ②对于S'中尚未标记的状态qi=｛si1，si2，…，sim｝，sij∈S（j=1，…，m）进行以下处理：
|
|
|
|
|
| .对于每个a∈∑，令T=f（｛si1，si2，…，sim｝，a），qj=ε_CLOSURE（T）。
|
|
|
| .若qj尚不在S'中，则将qj作为一个未加标记的新状态添加到S'，并把状态转换函数f'（qi，a）=qj添加到DFAM中。
|
|
|
| ③重复进行步骤②，直到S'中不再出现未标记的状态时为止。
|
|
|
|
|
|
|
|
|
| 对上图所示的自动机进行化简所得的DFA如下图所示。
|
|
|
|
|
|
|
