当前位置:文档之家 > 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最小化 实验目的: 1. 熟练掌握 DFA 及 NFA 的定义及有关概念。 2. 理解并掌握确定的有穷自动机的...

一种新的DFA状态最小化算法

一种新的DFA状态最小化算法 - 提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和...

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

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

DFA的最小化

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

DFA最小化

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

DFA的最小化实验

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

基于信息系统的确定有限自动机最小化算法

基于信息系统的确定有限自动机最小化算法 - 目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行...

基于信息系统的确定有限自动机最小化算法

基于信息系统的确定有限自动机最小化算法 - 目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行...

DFA最小化

DFA最小化 - 编译原理实验 实验名称:DFA 最小化 姓名: 学号: 教师签字: 成绩: 一. 实验目的: 1. 掌握 DFA 各个状态之间的转化和他们之间的等价性的条件。...