NFA

Definition / 释义

NFA 是 nondeterministic finite automaton 的缩写，中文常译为非确定性有限自动机。它是一种用于描述与识别正则语言的计算模型：在同一输入符号下，可能从某个状态“同时”存在多条可选转移（也常允许 ε 转移，即不消耗输入字符的转移）。
（注：在其他语境里 NFA 也可能指别的缩写，如法律或行政用语，但计算机科学中最常见的是上述含义。）

Pronunciation / 发音

/ˌɛn ɛf ˈeɪ/

Examples / 例句

An NFA can have more than one possible next state for the same input.
NFA 在同一输入下可以有不止一个可能的下一状态。

To prove a language is regular, we can construct an NFA with ε-transitions and then convert it to an equivalent DFA.
为了证明某个语言是正则的，我们可以先构造带有 ε 转移的 NFA，然后将其转换为等价的 DFA。

Etymology / 词源

NFA 来自英文术语 nondeterministic finite automaton 的首字母缩写：**non-**（非）+ deterministic（确定性的）+ finite（有限的）+ automaton（自动机）。该概念在形式语言与自动机理论中用于刻画“非确定选择”的状态转移，并与 DFA（确定性有限自动机）形成对照。

Related Words / 相关词

• DFA
• Automaton
• Finite State Machine
• Regular Language
• Regular Expression
• Regex
• Epsilon Transition
• Transition Function

Literary Works / 文学与作品例证

• Introduction to Automata Theory, Languages, and Computation（Hopcroft, Motwani & Ullman）：以 NFA/DFA 为核心概念讲解正则语言与自动机。
• Introduction to the Theory of Computation（Michael Sipser）：用 NFA 解释正则语言、闭包性质与等价转换。
• Automata and Computability（Dexter C. Kozen）：在计算性与形式模型章节中系统使用 NFA。