精选优质文档-倾情为你奉上编译原理实验报告实验四：有穷状态自动机的确定化实验目的：1. 熟练掌握DFA及NFA的定义及有关概念。2. 理解并掌握确定的有穷自动机的化简等算法。实验要求：1.输入： 非确定有限（穷）状态自动机。2.输出： 确定化的有限（穷）状态自动实验原理：1.由定义可见，不确定有限自动机NFA与确定有限自动机DFA的主要区别是：（1）NFA的初始状态S为一个状态集，即允许有多个初始状态；（2）NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。即DFA中的F是单值函数，而NFA中的F是多值函数。2. NFA确定化为DFA同一个字符串可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。下面介绍一种NFA的确定化算法，这种算法称为子集法：（1）若NFA的全部初态为S1，S2，Sn，则令DFA的初态为：S
