从NFA到DFA的转换
# 从NFA到DFA的转换
课件
# 转换原理
- DFA 的每个状态都是一个由 NFA 中的状态构成的集合, 即 NFA 状态集合的一个子集
例1: NFA 到 DFA 转换
- 正则表达式:
- NFA 的转换图
- NFA 的转换表
- DFA 的转换图
例2: 从带有 ε-边的NFA到DFA的转换
- 正则表达式:
- NFA 的转换图
- NFA 的转换表
- DFA 的转换图
# 子集构造法
此算法的作用是: 从 NFA 状态集合和转换表,转换得到 DFA 中的各状态集合和转换表
输入输出
- 输入
- NFA 的状态集合及其转换表
- 输出
- DFA 的状态集合及其转换表
参数说明
a
: 输入符号T
: 状态集合Dstates
: 表示 DFA 的状态集合Dtran[T, a]
- 表示从状态集合
T
出发,通过标号为a
的转换所能到的 DFA 状态集合- 相当于是 Hash 的数据结构
- 将此变量组合起来,即可得到 DFA 的状态转换表
- 表示从状态集合
算法实现
主程序
// 一开始,ε-closure(s0)是 Dstates 中的唯一状态,且它未加标记, s0 为开始状态; while(在Dstates中有一个未标记状态T ){ 给T加上标记; for(每个输入符号 a){ U = ε-closure(move(T, a)); // 对于不含 ε 边的 NFA, 相当于 U = move(T, a) if (U不在Dstates中) 将U加入到Dstates中,且不加标记; Dtran[T, a]=U ; } }
1
2
3
4
5
6
7
8
9
10函数的实现 // ε-closure 函数用来处理带有 ε 边的 NFA,如果没有 ε 边,则其输出等于输入 // 相当于求出状态集合 T 中的状态通过 ε 边能到达的状态集合 M, 最终输出为 M 和 T 并集 将 T 的所有状态压入 stack 中; 将 ε-closure(T) 初始化为 T ; while (stack 非空) { 将栈顶元素 t 给弹出栈中; for (每个满足如下条件的 u :从 t 出发有一个标号为 ε 的转换到达状态 u) if ( u 不在ε-closure (T) 中){ 将 u 加入到ε-closure (T)中; 将 u 压入栈中; // 压入栈中后实现逐层遍历 } }
1
2
3
4
5
6
7
8
9
10
11
12
各操作的含义
操作 | 描述 |
---|---|
ε-closure(s) | 能够从 NFA 的状态 s 开始只通过 ε 转换到达的 NFA 状态集合 |
ε-closure(T) | 能够从 T 的某个 NFA 状态 s 开始只通过 ε 转换到达的 NFA 状态集合,即 |
move(T, a) | 能够从 T 的某个状态 s 出发通过标号为 a 的转换到达的 NFA 状态的集合(注意是直接到达,不包含 ε 边) |
具体理解时,可结合例1,例2 的运行过程进行分析
- 算法的构造基于具体的数据结构,要从数据结构的层面去理解算法
编辑 (opens new window)