摘要
对有限状态机(FA)的最小化理论进行了研究,提出了原机器M与其最小机器M′之间还存在一种更近的关系,即同余关系。为机器M与M′构造相关的代数系统,证明了两者之间存在同余关系。实验表明,同余关系对简化系统描述具有重要意义,为揭示原系统与约简系统之间蕴涵的更为深刻的内在关系提供了必要的理论基础。
Studied minimization theory of finite automata（FA） and proposed the existence of congruence relation, which was much closer than equivalence relation, between minimized automata M＇ and original one M proposed. Proved the existence of congruence relation between M＇ and M by constructing the corresponding algebraic system respectively. Experiment results show the significance of congruence relation for system-simplified description, and it provides the necessary theoretical basis for disclosing the deeply internal relationship between original system and reduction one.
出处
《计算机应用研究》
CSCD
北大核心
2009年第5期1746-1748,共3页
Application Research of Computers
基金
国家自然科学基金资助项目(70572099)
辽宁省自然科学基金资助项目(1050349)
关键词
有限状态机
约简
代数系统
同余关系
finite automata
reduction
algebraic system
congruence relation
