编译原理课程设计（NFA转DFA） - CSDN文库

需积分: 20 163 浏览量更新于2023-03-16 评论 2 收藏 311KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

目录

摘要…………………………………………………………………………………………1

一、引言……………………………………………………………………………………2

二、设计任务与目的 ………………………………………………………………………2

三、设计方案与实施………………………………………………………………………2

1、总体设计

2、详细设计

3、程序清单

4、程序调试与体会

5、运行结果（截图）

四、结论………………………………………………………………………………………20

五、小结………………………………………………………………………………………21

六、参考文献…………………………………………………………………………………22

编译原理课程设计

《编译原理》课程设计

-- NFA的确定化设计

一、引言

在编译系统中,词法分析阶段是整个编译系统的基础。对于单词的识别，有限自动机FA是一种十分

有效的工具。有限自动机由其映射f是否为单值而分为确定的有限自动机DFA和非确定的有限自动机

NFA。在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择，故

一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响

到FA的工作效率。而DFA引擎在任意时刻必定处于某个确定的状态，它搜索是无需象NFA一样必须记

录所有的可能路径（trace multiple possible routes through the NFA），这也是DFA运行效率高

于DFA的原因。而已经证明DFA是NFA的一个特例，即对于每一个NFA M存在一个DFA M’’，使得

L(M)=L(M’’)。

二、设计目的与任务

通过本课程设计教学所要求达到的目的是：充分理解和掌握NFA，DFA以及NFA确定化过程的相关

概念和知识，编程实现对输入NFA转换成DFA输出的功能。

三、设计方案

1、总体设计

完成该设计所用到的理论知识、及对问题的功能进行分析，并总结出实现整个问题的程序模块，及

其功能。

 基本概念

NFA和DFA的概念

是不确定性有限状态自动机的简写，的定义为：

一个不确定性有限状态自动机由以下部分所组成：

 一个有限的输入字符集

 一个有限的状态集

 状态转换函数，为的幂集

 一个结束状态集，是的子集

! 一个初始状态"属于

 表示为### #"

例如，下图就是一个不确定性有限状态自动机：

$

剩余23页未读，继续阅读

评论0

rokyou

粉丝: 10
资源: 2

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈