输入与输出
输入：一个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的转换算法
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论