Subset Construction

释义 Definition

子集构造法：形式语言与自动机理论中的一种标准方法，用来把非确定有限自动机（NFA）转换为等价的确定有限自动机（DFA）。其核心思想是：把DFA的每个状态看作NFA状态集合的一个“子集”（通常还包含ε-闭包）。

发音 Pronunciation (IPA)

/sbst knstrkn/

例句 Examples

The subset construction converts an NFA into a DFA.
子集构造法把NFA转换成DFA。

Using subset construction, we compute ε-closures and build DFA states that represent sets of reachable NFA states under each input symbol.
使用子集构造法时，我们先计算ε-闭包，并在每个输入符号下构建代表“可达NFA状态集合”的DFA状态。

词源 Etymology

该术语由 subset（子集） 与 construction（构造/构建方法） 组成，直观表达了算法要点：通过“用状态子集来构造新自动机状态”，将非确定性行为系统化为确定性的状态转移结构。它是自动机理论课程与编译原理中常见的经典命名。

文学与经典出处 Literary Works

Introduction to Automata Theory, Languages, and Computation（Hopcroft, Motwani, Ullman）
Introduction to the Theory of Computation（Michael Sipser）
Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman，“龙书”）