输入与输出
输入:一个NFA N;
输出:一个接受同样语言的DFA D;
算法
三大函数:(s表示N的单个状态,T表示N的一个状态集)
操作 |
描述 |
epsilon-closure(s) | 能够从NFA状态s开始只通过epsilon转换到达的NFA状态集合 |
epsilon-closure(T) |
能够从T中某个NFA状态s开始只通过epsilon转换到达的NFA状态集合 |
move(T,a) |
能够从T中某个状态s触发通过标号为a的转换到达的NFA状态的集合 |
分析:
-
构造一个转换表Dtran;
-
D的每一个状态是一个NFA集合;
-
构造Dtran使得D"并行"模拟N在遇到一个给定输入串时可能执行的所有动作;
-
找出当N读入了某个输入串后可能位于的所有状态集合:
-
在读入第一个符号之前,N可以位于epsilon-closure(s_0)的任何状态上;
-
假定N在读入字符串s后可以位于集合T的状态上;
-
如果下一个输入符号为a,那么N可以立即移动到集合move(T,a)中的任何状态;
-
N可以在读入a后再执行几个epsilon转换,因此N在读入xa后可位于epsilon-closure(move(T,a))中的任何状态上;
算法:
# 一开始, epsilon-closure(s_0)时D_states中的唯一状态且未标记
while(在D_states中有一个未标记的T){
给T打上标记
for(每个输入符号a){
U = epsilon-closure(move(T,a))
if(U不在D_states中){
将U加入到D_states中,且不做标记
D_tran[T, a] = U;
}
}
}
原文始发于微信公众号(赛博安全狗):【编译原理】NFA到DFA的转换算法
免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论