关于有限状态机最小化理论的一个注记

A Note on Minimization Theory of Finite Automata

对有限状态机的最小化理论进行了研究,提出了原机器M与其最小机器M′之间还存在一种更近的关系,即同余关系.为机器M与M′构造相关的代数系统,证明了二者之间存在同余关系.阐述了同余关系对系统描述的意义,为应用有限状态机简化复杂过程提供了进一步的理论依据.

Minimization theory of Finite Automata （FA） was studied and the existence of congruence relation, which is much closer than equivalence relation, between minimized automata and original one was proposed. The existence of congruence relation between them was proved by constructing the corresponding algebraic system respectively. The paper discusses the significance for system description of congruence relation in detail, and provides the further theoretical basis for applying FA to simplifying complicated processes.