非确定有限自动机(NFA)

非确定有限自动机(Nondeterministic Finite Automaton,NFA)是形式语言与自动机理论中的一种计算模型。它在读入一个输入符号时,当前状态可以转移到零个、一个或多个状态,还允许在不消耗输入符号的情况下进行空转移。只要存在一条从初始状态出发、读完整个输入并停在接受状态的路径,该输入就被接受。

概述

NFA 由五元组构成:有限状态集合、输入字母表、转移函数、初始状态和接受状态集合。与确定有限自动机(DFA)不同,NFA 的转移函数返回的是一个状态的集合而非单一状态,因此对同一输入可能存在多条并行的计算路径。这里的非确定性并不意味着随机,而是指模型可以同时探索所有可能的路径,只要有一条成功即算接受。

核心特点

• 多路转移:同一状态对同一符号可以有多个后继,便于直接翻译正则表达式。
• 空转移:允许不读入符号就改变状态,常记作 ε 转移。
• 与 DFA 等价:通过子集构造法,任何 NFA 都能转换为一个识别相同语言的 DFA。
• 状态可能爆炸:一个 n 状态的 NFA 转成 DFA 后,状态数最坏可达 2 的 n 次方。

应用场景

NFA 是正则表达式引擎的理论基础。在词法分析器生成工具中,正则表达式先被转换为 NFA,再确定化为 DFA 以便高效匹配。它也用于文本搜索、模式匹配和协议状态建模。由于从正则表达式到 NFA 的构造直观清晰,NFA 常作为教学与理论推导中的中间表示。

常见问题

问:NFA 比 DFA 更强大吗?答:不是。二者识别的语言类完全相同,都是正则语言。NFA 的优势在于描述更简洁,而非表达能力更强。

问:为什么还要引入 NFA?答:因为从正则表达式直接构造 NFA 非常自然,状态数也更少,便于分析和转换;需要执行时再确定化即可。