首页 > NFA确定化

NFA确定化

发布时间：1714280536 来源：文档文库

小中大

字号：

手机查看

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/f336b97768dc5022aaea998fcc22bcd127ff42c2.html

《NFA确定化.doc》

将本文的Word文档下载到电脑，方便收藏和打印

推荐度：

点击下载文档

文档为doc格式

相

关

案

例

NFA确定化

相关推荐

推荐内容