正在进行安全检测...
发布时间：1714282780 来源：文档文库
小
中
大
字号：
- -- 编译原理实验报告(二 E01214055 鲁庆河
1. 实验名称：
不确定有穷状态自动机的确定化
2. 实验目的：
a 输入：非确定有穷状态自动机NFA b 输出：确定化的有穷状态自动机DFA
3. 实验原理：
a NFA确定化为DFA 同一个字符串α可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。
b NFA的确定化算法 ----- 子集法：
若NFA的全部初态为S1，S2，…，Sn，则令DFA的初态为：
S＝[S1，S2，…，Sn]， 其中方括号用来表示若干个状态构成的某一状态。
设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 