有限自动机最小化算法的实现

An Implementation of the Minimization Algorithm of DFA

实现DFA M=(Q,Σ,δ,q0,F)最小化算法的关键问题是如何编程求取商集Q/Rk(即状态的k阶区分)。本文引入等价关系Sk与商集Q/Sk(状态的严格k阶区分),证明了Rk=Rk-1∩Sk,因此Q/Rk是Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体。为了求取Q/Sk,引入Q的子集Hk,利用集合的交、差运算可由Hk求取Q/Sk,从而仅利用集合运算便可求取Q/Rk。基于上述讨论,给出了DFA最小化算法的一个容易实现的构造性描述。

A key problem of implementing the minimization algorithm of DFA M = （ Q, ∑ ,δ , q0, F ） is how to program to solve quotient set Q / Rk （i.e. k-order partition of states）. A equivalence relation Sk on Q and quotient set Q / Sk （exact k-order partition of states） are introduced, and Rk = Rk-1 ∩ Sk is proved, then elements of Q / nk are all nonempty intersections of each equivalence class belonging to Q / Rk-1 and each one belonging to Q / Sk. A subset Rk of Q is introduced for solving Q / Sk only to use intersection and difference operations, therefore Q / Rk is solved only to use set operations. A constructive minimization algorithm of DFA easily to be implemented is represented based on the above discussion.