一种非确定型有穷自动机的极小化方法

• 作者: 张丽
• 来源期刊: 宁夏大学学报（自然科学版）
• 学科: 工学
• 关键词: 自动机 非确定型自动机 子语言自动机 同态 极小化
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 计算机应用与自动控制
• 页码范围: 148-151
• 分类号: TP301
• 字数: 4254字
• 语种: 中文
• DOI: 10.3969/j.issn.0253-2328.2012.02.006

摘要

自动机状态极小化是寻求状态数较少的自动机,使其与原自动机接受相同的语言.确定型有穷状态自动机(DFA)极小化问题在平方时间内可解,通过状态集上引入等价关系导出的商自动机即为接受相同正则语言的极小化自动机.而非确定型有穷状态自动机(NFA)极小化问题尚未找到有效算法.尽管NFA可以转化为DFA且接受的语言不变,但可能会出现状态数指数级增加.从语言B可以构造一个接受自己的子语言自动机,同态压缩映射子语言自动机为最终系统,从而为接受语言B的极小化自动机.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张丽	贵州大学计算机科学与信息学院	24	69	5.0	7.0