当前位置:文档之家 > 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的最小化_计算机软件及应用_IT/计算机_专业资料。编译原理实验DFA...DFA最小化算法研究 暂无评价 3页 ¥2.00 一种新的DFA状态最小化算... ...

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

熟练掌握 DFA 及 NFA 的定义及有关概念。 2. 理解并掌握确定的有穷自动机的最小化算法。 三:实验原理 1.化简 DFA 关键在于把它的状态集分成一些两两互不...

DFA最小化算法中状态等价判断方法

DFA最小化算法中状态等价判断方法_信息与通信_工程科技_专业资料。对使用"分割法"最小化DFA中出现的当一个状态没有相应的产生式存在时如何进行分割,提出了正确使用...

DFA最小化

编译原理实验报告 实验名称 DFA最小化 实验时间 院系 班级 学号 姓名 1....下面具体介绍 DFA 的化简算法: (1) 首先将 DFA M 的状态划分出终止状态集 ...

DFA的最小化实验

DFA的最小化实验_计算机软件及应用_IT/计算机_专业资料。DFA最小化,可运行结果...DFA最小化 7页 1下载券 DFA最小化 6页 2下载券 DFA最小化算法研究 暂无评...

DFA最小化

DFA最小化_计算机软件及应用_IT/计算机_专业资料。编译原理实验之确定自动机最小...DFA最小化算法研究 暂无评价 3页 ¥2.00 NFA到DFA确定化及最小... 暂...

编译原理实验DFA最小化

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

DFA的最小化

确定的有穷自动机(DFA) 的最小化 DFA的最小化 1.什么是最小化? 2.能不...DFA最小化算法研究 暂无评价 3页 ¥2.00 DFA-DFA 103页 免费 DFA 12页 ...

一种将NFA到最小化DFA的方法

一种将NFA到最小化DFA的方法_IT/计算机_专业资料。关于自动机的文章%...8 基于 )*+ 上的动态主页开发研究 9] 计算 等[ 8 机应用研究, (<) 7#...