【编译原理】NFA到DFA的转换算法

输入与输出

输入：一个NFA N；

输出：一个接受同样语言的DFA D；

算法

三大函数:（s表示N的单个状态，T表示N的一个状态集）

分析：

1. 构造一个转换表Dtran；

2. D的每一个状态是一个NFA集合；

3. 构造Dtran使得D"并行"模拟N在遇到一个给定输入串时可能执行的所有动作；

4. 找出当N读入了某个输入串后可能位于的所有状态集合：

1. 在读入第一个符号之前，N可以位于epsilon-closure(s_0)的任何状态上；

2. 假定N在读入字符串s后可以位于集合T的状态上；

3. 如果下一个输入符号为a，那么N可以立即移动到集合move(T,a)中的任何状态；

4. 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的转换算法