(7,while) (26,() (10,i) (27,)) (10,i) (21, =) (10,i) (23,-) (20,1) (34,;)
(31,})
设计并实现将 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’)。
(1)令 I 是 NFA N 的状态集 S 的一个子集,I 的ε 闭包的ε _Closure(I)构造规则如下:
(a)若 s∈I,则 s∈ε _Closure(I);
(b)若 s∈ε _Closure(I)且δ (s, ε )=s’而 s’ ε _Closure(I) ,则 s’∈ε
根据上面的规则,下面给出了一个计算 I 的ε 闭包的算法ε _Closure(I)。
if(存在δ (i, ε )=j)
if(j 不在 S 中) {
把 i 加到 S 中;
把 j 压入栈中;
}
/* 返回ε _Closure(input)集合 */
(2)令 I 是 NFA N 的状态集 S 的一个子集,a∈Σ , 转换函数 Move(I,a)定义为:
Move(I,a)= ε _Closure(J)
其中,J={s’|s∈I 且δ (s,a)=s’}
转换函数 Move(I,a)的设计通过调用ε _Closure(input)实现,完成该函数的设计。
(3)从 NFA N 构造一个与其等价的 DFA M 的子集构造算法,就是要为 DFA M 构造状态转
评论0
最新资源