编译原理课程设计-NFA的确定化

《编译原理课程设计-NFA的确定化》由会员分享，可在线阅读，更多相关《编译原理课程设计-NFA的确定化（28页珍藏版）》请在毕设资料网上搜索。

1、 计算机系计算机系 编译原理课程设计编译原理课程设计 课课 程程 名名 称称 : 编译原理编译原理 课课 程程 代代 码码 : 436105436105 题题 目目 : NFANFA 的确定化的确定化 年级年级/ /专业专业/ /班班 : 学学 生生 姓姓 名名 : 学学 号号 : 指指 导导 老老 师师 : 开开 题题 时时 间间 : 完完 成成 时时 间间 : - 1 - 目目 录录 一、引 言. - 4 - 二、设计目的与任务. - 4 - 1、设计目的： - 4 - 2、设计任务： - 4 - 三、设计方案. - 5 - 1、总体设计 - 5 - 2、详细设计 - 11 - 3、程序清

2、单 - 14 - 4、程序调试与体会 - 23 - 5、运行结果 - 24 - 四、结 论. - 25 - 五、致 谢. - 26 - 六、参考文献. - 26 - 2 设计进度完成情况. - 27 - - 2 - 摘摘 要要 确定有限自动机确定的含义是在某种状态，面临一个特定的符号只有一个 换，进入唯一的一个状态。不确定的有限自动机则相反在某种状态下，面临个 特定的符号是存在不止一个转换即是可以允许进入一个状态集合。 在非确定的有 限自动机 NFA 中由于某些状态的转移需从若干个可能的后续状态中进行选择， 故一个 NFA 对符号串的识别就必然是一个试探的过程。 这种不确定性给识别过程 带来的

3、反复，无疑会影响到 NFA 的工作效率。而 DFA 则是确定的，将 NFA 转化为 DFA 将大大提高工作效率，因此将 NFA 转化为 DFA 是必要的。对任意的一个不确 定有限自动机（NFA） ，都会存在一个等价的确定的有限自动机（DFA） ，即 L（N） =L(M)。本文主要是介绍如何将 NFA 转换为与之等价的简化 DFA，通过具体实例， 结合图形，详细说明转换的算法原理。 关键词关键词：有限自动机；确定有限自动机（DFA） ，不确定有限自动机（NFA） - 3 - Abstract Finite automata are determinate and indeterminate tw

4、o classes. Determine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata are the opposite. In a certain state, Faces a symbol is the presence of more than one conversion, which is to be allowed to enter a state set

5、. Non deterministic finite state automata NFA, because of some state are transferred from a number of possible follow-up states are chosen, so NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated. Will undoubtedly affect the eff

6、iciency of the NFA .While the DFA is determined, convening NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary. For any a nondeterministic finite automaton (NFA) can be an equivalent deterministic finite automaton (DFA), L (N) =L (M). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detailed description of the algorithm principle of conversion.