编译原理课程设计--NFA转化为DFA的转换算法及实现

《编译原理课程设计--NFA转化为DFA的转换算法及实现》由会员分享，可在线阅读，更多相关《编译原理课程设计--NFA转化为DFA的转换算法及实现（25页珍藏版）》请在毕设资料网上搜索。

1、 编译原理课程实践报告编译原理课程实践报告 设计名称： NFANFA转化为转化为DFADFA的转换算法及实现的转换算法及实现 二级学院： 数学与计算机科学学院 专 业： 计算机科学与技术 班 级： 计科本 091 班 姓 名： 林玉兰 学 号： 0904402102 指导老师： 梁德塞 日 期： 2012 年 6 月 摘要 确定有限自动机确定的含义是在某种状态， 面临一个特定的符号只有一个转 换，进入唯一的一个状态。不确定的有限自动机则相反，在某种状态下，面临一 个特定的符号是存在不止一个转换，即是可以允许进入一个状态集合。 在非确定的有限自动机 NFA 中,由于某些状态的转移需从若干个可能的

2、后续 状态中进行选择，故一个 NFA 对符号串的识别就必然是一个试探的过程。这种不 确定性给识别过程带来的反复，无疑会影响到 FA 的工作效率。而 DFA 则是确定 的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必 要的。 对于任意的一个不确定有限自动机（NFA）都会存在一个等价的确定的有限 自动机（DFA） ，即 L(N)=L(M)。本文主要是介绍如何将 NFA 转换为与之等价的简 化的 DFA，通过具体实例，结合图形，详细说明转换的算法原理。 关键词：关键词：有限自动机；确定有限自动机（DFA） ，不确定有限自动机（NFA） Abstract Finite

3、automata is determinate and indeterminate two class. Determine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces a particular symbol is the presence of more than one con

4、version, that is to be allowed to enter a state set. Non deterministic finite state automata NFA, because of some state are transferred from a number of possible follow-up state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency of the FA. While the DFA is determined, converting NFA to DFA wil