当前位置:文档之家 > DFA最小化算法的探讨与改进

DFA最小化算法的探讨与改进

DFA最小化算法的探讨与改进

引言

“编译原理”是计算机专业的一门综合性较强的专业课程,主要介绍如何将高级语言翻译为低级语言的编译程序的工作原理和实现技术。该课程建立在高级语言或汇编语言基础上,综合运用编译理论及数据结构、离散数学等前修课程的相关知识,具有很强的理论性和严密的逻辑性,可以使学生真正了解计算机的工作过程,对提高学生计算机软件素质具有很大作用。本文结合教学工作实际,针对词法分析中确定的有穷自动机(DFA)的最小化算法和具体的做法进行深入的探讨,并对现有算法进行了合理的改进。

1DFA及DFA的化简

编译程序一般包括词法分析、语法分析、语义分析、中间代码生成、目标代码生成、代码优化、表格管理和出错处理等成分。词法分析是编译程序要做的首要工作,它接收输入的源程序符号串,按照构词规则分割为一个个的单词符号并输出。

有穷自动机是一种能进行运算和自我控制的装置,能准确识别单词符号。因此,可以通过构造有穷自动机来实现词法分析程序的自动构造。有穷自动机分为确定的有穷自动机DFA和不确定的有穷自动机NFA两种。

定义1DFA 一个确定的有穷自动机M是一个五元组,M=( K,Σ, f , S , Z),其中:K是一个有穷集,其元素称为状态;Σ是
一个有穷字母表,其元素称为输入符号;S∈K,称为初态;ZÌ K,是终态集;f是转换函数,是K×Σ→K 上的映射,f(ki,a)=kj,(ki∈K,kj∈K)表示状态ki,输入符为a时,转换为状态kj。

定义1DFA 一个确定的有穷自动机M是一个五元组,M=( K,Σ, f , S , Z),其中:K是一个有穷集,其元素称为状态;Σ是一个有穷字母表,其元素称为输入符号;S∈K,称为初态;ZÌ K,是终态集;f是转换函数,是K×Σ→K 上的映射,f(ki,a)=kj,(ki∈K,kj∈K)表示状态ki,输入符为a时,转换为状态kj。

定义2无用状态从自动机的开始状态出发,任何输入串也不能到达的那个状态;或者从这个状态没有通路到达终态的状态。

定义3等价状态如果说两个状态s 和t 是等价的, 应满足如下条件:(a) 一致性条件:s 和t 必须同时为终态或为非终态;(b) 蔓延性条件:对于所有输入符号,状态s 和t 必须转换到等价的状态里。

一个DFAM可以通过消除无用状态和合并等价状态而转化为一个最小化的与之等价的DFAM’。该过程称为DFA的化简。

2“分割法”化简DFA

对一个DFAM最少化的基本思想是:把M的状态集划分为一些不相交的子

下载Word文档免费下载:

DFA最小化算法的探讨与改进下载

(共1页)

对DFA最小化算法等价性问题的探讨与改进

DFA最小化算法等价性问题的探讨与改进 - 有穷自动机极小化问题的研究,在程序测试、模糊系统、概率自动机等方面具有重要意义。利用自动机状态集上的等价关系对...

DFA最小化算法

DFA最小化算法 - DFA最小化算法 ? 前提:理解多余状态,死状态,等价状态, 可区别状态 DFA的化简算法:对于DFA M=(S,Σ,f,S0,Z) (1)首先将DFA的状态集进行...

实验五-DFA的最小化

实验五-DFA的最小化 - 编译原理实验报告 实验五:DFA最小化 实验目的: 1. 熟练掌握 DFA NFA 的定义有关概念。 2. 理解并掌握确定的有穷自动机的...

编译原理实验六:DFA最小化

编译原理实验六:DFA最小化 - 实验六:DFA 最小化 一:要求 输入: DFA。 输出: 最小化的 DFA。 二:实验目的 1. 熟练掌握 DFA 及 NFA 的定义及有关概念。...

DFA最小化

DFA最小化 - 编译原理实验报告 实验名称 DFA 的最小化 实验时间 院系 班级 学号 姓名 1. 试验目的 掌握 DFA 的最小化 2. 实验原理 所谓自动机的化简问题....

DFA的最小化

DFA的最小化 - 确定的有穷自动机(DFA) 的最小化 DFA的最小化 1.什么是最小化? 2.能不能最小化? 3.怎样最小化? 1.什么是最小化? 定义:DFA的最小...

DFA的最小化实验

DFA的最小化实验_计算机软件及应用_IT/计算机_专业资料。DFA最小化,可运行结果...DFA最小化求解标记表 5页 免费 DFA最小化算法的探讨与改... 2页 2下载...

DFA最小化

DFA最小化 - 学号:E10914066 专业:计算机科学与技术二班 姓名:王安 实验日期: 2012/5/25 教师签字: 成绩: 《编译原理》 课程实验报告 实验五: DFA ...

编译原理实验DFA最小化

编译原理实验DFA最小化 - 2016.11.09 确定有穷自动机的最小化 目录 一、实验名称 ...

DFA最小化

DFA最小化_IT/计算机_专业资料。实验报告 实验名称 课程名称 姓名 编译原理 夏...DFA最小化算法的探讨与改... 2页 2下载券 DFA最小化求解标记表 5页 ...