论文部分内容阅读
实现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最小化算法的一个容易实现的构造性描述及示例．