实验五：有穷自动机的确定化
一：要求
1.输入： 非确定有限（穷）状态自动机。
2.输出： 确定化的有限（穷）状态自动
二：实验目的
1. 熟练掌握 DFA 及 NFA 的定义及有关概念。
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＝[S1，S2，…，Sn]，
其中方括号用来表示若干个状态构成的某一状态。
（2） 设 DFA 的状态集 K 中有一状态为[Si，Si+1，…，Sj]，若对某符号 a∈∑，
在 NFA 中有 F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }
则令 F（{ Si，Si+1，…，Sj }，a）={ Si’，Si+1’，…，Sk’ }为 DFA 的一个转换函数。
若[ Si’，Si+1’，…，Sk‘ ]不在 K 中，则将其作为新的状态加入到 K 中。
（3） 重复第 2 步，直到 K 中不再有新的状态加入为止。
（4） 上面得到的所有状态构成 DFA 的状态集 K，转换函数构成 DFA 的 F，DFA
的字母表仍然是 NFA 的字母表∑。
（5） DFA 中凡是含有 NFA 终态的状态都是 DFA 的终态。
3. NFA 确定化的实质是以原有状态集上的子集作为 DFA 上的一个状态，将原状
态间的转换为该子集间的转换，从而把不确定有限自动机确定化。经过确定化
后，状态数可能增加，而且可能出现一些等价状态，这时就需要简化。
