确定型有穷状态自动机的同态压缩  

The Homomorphism Compression of DFA

作　　者：文杰[1] 

机构地区：[1]贵州大学计算机科学系,贵州贵阳550025

出　　处：《广西师范学院学报（自然科学版）》2010年第4期95-99,共5页Journal of Guangxi Teachers Education University(Natural Science Edition)

基　　金：国家自然科学基金(600863005;61011130038)

摘　　要：对于确定型有穷状态自动机(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.

关 键 词：确定型自动机 状态等价 极小化 同态压缩 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]