首页 > NFA确定化

NFA确定化

发布时间：2023-02-25 15:00:41 来源：文档文库

小中大

字号：

手机查看

1．实验目的
设计并实现将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 假如s∈I，如此s∈ε_Closure(I；
(b 假如s∈ε_Closure(I且δ(s, ε=s’而s’∉ε_Closure(I ，如此s’∈ε_Closure(I 根据上面的规如此，下面给出了一个计算I的ε闭包的算法ε_Closure(I。
SET S; SETε_Closure(input

SET *input; { S=input; /* 初始化
*/ push(; /* 把输入状态集中的全部状态压入栈中while(栈非空{ Nfa_state i; pop(; /* 把栈顶元素弹出并送入i
*/ if(存在δ(i, ε=j if(j不在S中 { 把i加到S中; 把j压入栈中; }
} */

本文来源：https://www.2haoxitong.net/k/doc/2e1180ddf51fb7360b4c2e3f5727a5e9856a27ae.html