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

编译原理课程实践报告
设计名称: NFA转化为DFA的转换算法及实现
二级学院: 数学与计算机科学学院
专业: 计算机科学与技术
班级: 计科本091班
姓名: 林玉兰
学号:
指导老师: 梁德塞
日期: 2012年6月
摘要
确定有限自动机确定的含义是在某种状态,面临一个特定的符号只有一个转换,进入唯一的一个状态。不确定的有限自动机则相反,在某种状态下,面临一个特定的符号是存在不止一个转换,即是可以允许进入一个状态集合。
在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择,故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复,无疑会影响到FA的工作效率。而DFA则是确定的,将NFA转化为DFA将大大提高工作效率,因此将NFA转化为DFA是有其一定必要的。
对于任意的一个不确定有限自动机(NFA)都会存在一个等价的确定的有限自动机(DFA),即L(N)=L(M)。本文主要是介绍如何将NFA转换为与之等价的简化的DFA,通过具体实例,结合图形,详细说明转换的算法原理。
关键词:有限自动机;确定有限自动机(DFA),不确定有限自动机(NFA)
Abstract
Finite 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 conversion, 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 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.
Keywords::finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA
目录
: 1
1
1
1
2
不确定有限自动机NFA 2
3
5
5
5
7
4程序实现 9
9
数据流程图 9
10