从给定NFA构造DFA的疑问：为何生成该状态集合？

算力阿峰

2026-8-26

NFA转DFA的推导疑问

问题背景

该NFA的所有箭头均为ε箭头，定义如下：

1,{2, 3}
2,empty
3,{4}
4,empty

已算出各状态的ε闭包：

E(1) = {1,2,3,4}
E(2) = {2}
E(3) = {3,4}
E(4) = {4}

但无法理解为何有人给出的DFA状态集合是：

DFA = {empty, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2,
3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}

我认为应结合如下ε转换表和E函数构造DFA：

epsilon   
1  2, 3
2  -
3  4
4  -

我的推导过程如下：

Start state = 1 => the Result = {E(1)} = {{1, 2, 3, 4}}

T({1, 2, 3, 4}) = E(transitionTable({1, 2, 3, 4})) = E({2, 3, 4}) = {2, 3, 4}

Result = {{1, 2, 3, 4}, {2, 3, 4}}

T({2, 3, 4}) = E({4}) = {4}

Result = {{1, 2, 3, 4}, {2, 3, 4}, {4}}

T({4}) = E({}) = {}

Result = {{1, 2, 3, 4}, {2, 3, 4}, {4}, {}}

请问我的推导哪里出错了？

问题分析与解答

你的推导是正确的，给出的包含所有子集的DFA集合是错误的——它混淆了「所有可能的状态子集」和「实际可达的DFA状态子集」。

核心错误点

那个错误的DFA集合把状态集的所有幂集列了出来，但DFA的状态仅包含从初始状态出发，通过ε转换可达的状态子集。在你的NFA中：

初始状态是1，其ε闭包是{1,2,3,4}，这是第一个DFA状态
从{1,2,3,4}出发，经过ε转换得到的状态是2、3、4的ε转换结果合并：2无ε转换，3的ε转换是4，4无ε转换，合并后是{2,3,4}，取ε闭包仍为{2,3,4}，这是第二个DFA状态
从{2,3,4}出发，ε转换仅能得到4，取ε闭包为{4}，这是第三个DFA状态
从{4}出发，无ε转换，取ε闭包为空集，这是第四个DFA状态
空集的ε转换还是空集，不会产生新状态

整个过程中，根本无法到达{1}、{1,2}这类子集——因为只要状态子集包含1，它的ε闭包必然包含2、3、4，所以{1}这种子集不可能作为DFA的状态存在。