c语言编程NFA确定化(共8页).doc

精选优质文档-倾情为你奉上NFA确定化为DFA1实验目的设计并实现将NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。2实验要求设计并实现计算状态集合I的闭包的算法_Closure(I)和转换函数Move(I,a)，并在此基础上实现子集构造算法Subset_Construction。利用该从NFA到DFA的转换程序Subset_Construction，任意输入一个NFA N=（S,s0,F），输出一个接收同一语言的DFA M=（S,s0,F）。3实验内容(1) 令I是NFA N的状态集S的一个子集，I的闭包的_Closure(I)构造规则如下：(a) 若sI，则s_Closure(I)；(b) 若s_Closure(I)且(s, )=s而s _Closure(I) ，则s_Closure(I)根据上面的规则，下面给出了一个计算I的闭包的算法_