DFA 的化简

DFA 的化简

对于一个 NFA ,当把它确定化之后,得到的 DFA 可能含有较多的状态,还应该对其进行化简。任何正规语言都有一个唯一的状态数目最少的 DFA 。而且,对于同一个语言,可以存在多个识别该语言的 DFA 。从任意一个接受相同语言的 DFA 出发,通过分组合并等价的状态,总可以得到这个状态数最少的 DFA 。

1.DFA 的化简

所谓一个 DFA M 的化简是指寻找一个状态数比 M 少的 DFA M’ ,使得 L ( M ) = L ( M’ )。

化简了的 DFA M’ 满足两个条件:

(1 )没有多余状态。
(2 )它的状态集中,没有两个状态是互相等价的。

2. 有穷自动机的多余状态

所谓有穷自动机的多余状态是指从该自动机的开始状态出发,任何可识别的输入串也不能到达的状态。

3. 等价状态

设 DFA M = ( Q ,Σ , f , S 0 , F ), s , t ∈ Q 。若对任何 α ∈ Σ * , f ( s , α ) ∈ F 当且仅当 f ( t , α )∈ F ,则称状态 s 和 t 是等价的。如果 s 和 t 不等价,则称 s 和 t 是可区别的。例如,终态与非终态是可区别的。因为终态有一条到达自身的 ε 道路,而非终态没有到达终态的 ε 道路。

5. 化简方法

DFA M 最小化的方法是把 M 的状态集 Q 分划成一些不相交的子集,使得每个子集中任何两个状态是等价的,而任何两个属于不同子集的状态都是可区别的;然后在每个子集中任取一个状态作“代表”,而删去子集中其余状态,并把射向其余状态的箭弧都改为射向作为“代表”的状态中。

下面给出化简算法的具体执行步骤。

输入:一个 DFA M 。
输出:接受与 M 相同语言