摘要
对于确定型有穷状态自动机(DFA),通过定义状态集上的等价关系≈Q,借助于等价关系,可以在平方时间内构造出接受相同语言的极小化自动机.本文在DFA之间引入同态关系,证明了同态压缩下DFA接受相同语言.
By defining equivalent relationship on status sets,it was proved that a new DFA（Deterministic Finite Automaton） can be constructed which accepts the same language accepted by original DFA in square time.In this paper,we defined a homomorphism relationship,and proved that the new homomorphism compression DFA acceptes the same language accepted by original DFA.
出处
《广西师范学院学报（自然科学版）》
2010年第4期95-99,共5页
Journal of Guangxi Teachers Education University(Natural Science Edition)
基金
国家自然科学基金(600863005
61011130038)
关键词
确定型自动机
状态等价
极小化
同态压缩
DFA
status equivalent
status minimize
homomorphism compression
