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

实现DFAM=(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最小化算法的一个容易实现的构造性描述及示例.

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

实现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最小化算法的一个容易实现的构造性描述。