不确定有穷状态自动机的确定化实验报告(共9页).doc

精选优质文档-倾情为你奉上编译原理实验报告(二) E 鲁庆河1. 实验名称：不确定有穷状态自动机的确定化2. 实验目的：a) 输入：非确定有穷状态自动机NFA b) 输出：确定化的有穷状态自动机DFA3. 实验原理：a) NFA确定化为DFA同一个字符串可以由多条通路产生，而在实际应用中，作为描述控制过程的自动机，通常都是确定有限自动机DFA，因此这就需要将不确定有限自动机转换成等价的确定有限自动机，这个过程称为不确定有限自动机的确定化，即NFA确定化为DFA。b) NFA的确定化算法 - 子集法：l 若NFA的全部初态为S1，S2，Sn，则令DFA的初态为：SS1，S2，Sn， 其中方括号用来表示若干个状态构成的某一状态。l 设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 为DF