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

• 作者: 文杰
• 来源期刊: 南宁师范大学学报（自然科学版）
• 关键词: 确定型自动机 状态等价 极小化 同态压缩
• 年，卷（期）: 2010,（4）
• 页码范围: 95-99
• 分类号: TP301
• 语种: 中文
• DOI: 10.3969/j.issn.1002-8743.2010.04.020

摘要

对于确定型有穷状态自动机(DFA),通过定义状态集上的等价关系≈Q,借助于等价关系,可以在平方时间内构造出接受相同语言的极小化自动机.本文在DFA之间引入同态关系,证明了同态压缩下DFA接受相同语言.