非确定有限自动机

官官方信息技术老师·20 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ 非确定有限自动机信息技术非确定有限自动机e转移
形式化定义子集构造DFA等价计算理论

非确定有限自动机

彻底理解NFA的形式定义、子集构造证明与DFA等价的全部细节

按 空格/→ 演示下一步

1 / 20 页

全部页面点击任意一页，跳回舞台从这页播放

形式化定义子集构造DFA等价计算理论

非确定有限自动机

彻底理解NFA的形式定义、子集构造证明与DFA等价的全部细节

1第 1 页 · 非确定有限自动机

什么是「非确定」

上一页我们给非确定有限自动机下了定义，但它名字里的「非确定」到底什么意思？先放下术语——想象你走进一个迷宫，每到岔路口都可以分身，同时走所有方向。

转移不唯一
同一状态读入同一字符，可以跳到多个后继状态
并行探索
计算模型上，多条岔路同时被试，不会撞墙才回头
∃ 语义
只要存在一条路径走到接受态，输入串就被接受
结果仍确定
「非确定」指路径多，不指接受或拒绝的结果摇摆
迷宫岔路口分身探路对应 →NFA 的状态转移

每个岔路同时派分身，任何一条通到出口就算成功

δNFA:Q×Σ→P(Q)vsδDFA:Q×Σ→Q\delta_{NFA}: Q \times \Sigma \to \mathcal{P}(Q) \quad\text{vs}\quad \delta_{DFA}: Q \times \Sigma \to Q
2第 2 页 · 什么是「非确定」

NFA vs DFA 对比

NFA 与 DFA 等价但本质不同——一个并行探索,一个线性推进。

NFA 非确定
  • 同一输入可触发多条转移
  • 并行维护多个活跃状态
  • 可用 ε-转移不读字符跳转
  • 同一字符可对应多个目标
DFA 确定
  • 同一输入只能选一条转移
  • 任意时刻只有一个当前状态
  • 必须消耗字符才能转移
  • 每个字符对应唯一目标
描述语言用 NFA(直观),实现识别用 DFA(高效)。
3第 3 页 · NFA vs DFA 对比

NFA的形式化定义

前面我们看清 NFA 比 DFA 「松」在哪里：同一输入可去多个状态、某些转移可以不写。这份「松」落到纸面，就是五元组 M=(Q,Σ,δ,q0,F)。下面逐个拆开分量。

Q：状态的有穷集
机器运行中可能停留的所有状态；约定为非空有限集，是自动机的「骨架」
Σ：输入字母表
机器可读入的合法符号集合，有限；含 ε 转移时扩展为 Σ_ε = Σ∪{ε}
δ：转移函数
δ: Q×Σ → 2^Q，返回状态子集而非单值；允许部分 (q,a) 无定义
q0：唯一初始状态
机器启动时所在的状态，q0 ∈ Q；唯一指定，不能省略也不能多个
F：接受状态集合
读完输入串后停留于其中任一即被接受；F ⊆ Q，可以为空
导航地图系统对应 →NFA 五元组

Q 是全部路口、Σ 是合法转向、δ 给出路口读信号后可能的多个去处、q0 是出发路口、F 是目的路口集合

M=(Q, Σ, δ, q0, F);δ:Q×Σ→2QM = (Q,\ \Sigma,\ \delta,\ q_0,\ F);\quad \delta: Q \times \Sigma \to 2^Q
4第 4 页 · NFA的形式化定义

NFA的状态转移图表示

看图先找三要素：无源箭头（起点）、双圈（接收）、带符号的箭头（转移）。

图解渲染中…
s1：无来源的箭头指向起始状态，整个NFA只有一个a4：双圈=接收状态，串处理完能走到这里就算被接受a1：q0读a有两条出边——这就是非确定性在图上的特征
5第 5 页 · NFA的状态转移图表示

ε转移的概念

看 NFA 转移图时，每条边上都标着输入字符。但 NFA 还有种特殊箭头——上面什么都不标。这不是漏写，而叫 ε 转移：不用读任何字符就能切换状态。

ε = 空串
ε 是长度严格为 0 的字符串，不对应任何实际字符
不消耗输入
沿 ε 边切换状态时，输入指针原地不动，下一个字符仍是同一个
与字符转移共存
一个 NFA 可同时存在字符转移边和 ε 转移边，两者语义独立
ε 闭包
从状态 q 出发，沿任意多条 ε 边可达的全部状态的集合
酒店相邻两间房的连通门对应 →ε 转移

推开连通门就到隔壁房，不走走廊、不花体力——对应「不读字符、状态已切换」

$$\delta(q, \epsilon) \subseteq Q$$
6第 6 页 · ε转移的概念

带ε转移的NFA示例

圆点标亮 NFA 当前所处的状态集合，按动画步序逐次点亮。

图解渲染中…
d1：椭圆形 q3 = 接受态，ε 可直达a1：q0 同时向两条分支打 ε，不消耗字符b1, c1：自环上 'a'/'b'，ε 出环即停在该分支
7第 7 页 · 带ε转移的NFA示例

ε闭包与状态可达

上页我们看到ε箭头不消耗字符。站在q时，其实可以沿ε箭头免费滑到所有能到的地方。这个「免费可达的全部去处」，就叫ε闭包。

定义
从状态q出发，仅沿ε边可达的全部状态（含q自身）的集合
自反性
q一定在ε-closure(q)中——ε可以不走，零步也算
传递性
q→ε p 且 p→ε r，则r也在q的闭包里
计算方法
BFS/DFS只沿ε边扩展，迭代到无新状态加入为止
用途
判定接收前用ε闭包扩展当前可达集，再调用move()
机场免费摆渡车对应 →ε闭包

在航站楼可免费换乘所有可达航站楼，不消耗登机次数（即输入字符）

ε-closure(q)={q}∪⋃q→εrε-closure(r)\varepsilon\text{-closure}(q) = \{q\} \cup \bigcup_{q \xrightarrow{\varepsilon} r} \varepsilon\text{-closure}(r)
8第 8 页 · ε闭包与状态可达

为什么要扩展转移函数

δ 一次只能处理一个字符，但判断「整个字符串是否被接受」需要读完整串。能不能把 δ「打包升级」，让它一次处理整串？

δ 的局限
只接受单个字符，无法直接描述读完一整串后的状态
扩展函数 δ̂
输入「状态 + 字符串」，返回读完后的所有可达状态
递推读串
空串是基础（取 ε-闭包）；非空串在上一步结果上再读一个字
翻书读章节对应 →扩展转移函数

一页一页翻，每翻一页页码可能跳；读完一章要记下所有可能停下的页

δ^(q,ε)=ε-closure(q)δ^(q,wa)=ε-closure(⋃p∈δ^(q,w)δ(p,a))\hat{\delta}(q, \varepsilon) = \varepsilon\text{-closure}(q) \\ \hat{\delta}(q, wa) = \varepsilon\text{-closure}\Big(\bigcup_{p \in \hat{\delta}(q, w)} \delta(p, a)\Big)
9第 9 页 · 为什么要扩展转移函数

δ*的递归定义

把 δ 从「读一个字符」升级到「读整条字符串」，靠两条递归规则搭出来。

1
基础情况：空串
δ*(q, ε)=q，空串不移动状态
2
衔接：单字符
δ*(q, a)=δ(q, a)，复用原 δ
3
递归：拆分字符串
δ*(q, wa)=δ*(δ(q,w), a)，先 w 再 a
4
终止：剥到 ε 为止
每次 w 变短，必然落到基础情况
10第 10 页 · δ*的递归定义

扩展转移函数的计算示例

python

用 Python 把 δ* 的递推定义直译成代码,在字符串 aab 上逐字符演示。

代码高亮加载中…

δ(q,a) 返回集合是 NFA 的非确定根源(L4);代码把 δ* 递推定义逐行落地:基础步(L16)给种子、归纳步(L20)做并集;最终在 aab 上逐字符输出 δ* 中间值(L28)。

11第 11 页 · 扩展转移函数的计算示例

NFA与DFA的等价性

我们能用扩展转移函数 δ* 跑通 NFA 了。但 NFA 多出的那份『非确定性』，真的能让它接受 DFA 接受不了的字符串吗？这一页给反转：不会。

等价判据
两种自动机等价 ⟺ 接受完全相同的语言；结构可以千差万别
子集构造
NFA→DFA 的核心：DFA 每个状态对应 NFA 状态集合的一个子集
构造三要素
起态 = q₀ 的 ε-闭包；终态 = 含原终态的子集；转移 = 逐态取并集
反向平凡
每个 DFA 直接就是 NFA 的特例，无需任何『反向构造』
代价警告
n 态 NFA 最坏可生成 2ⁿ 个 DFA 状态，是子集构造的主要代价
嫌疑人藏身点清单对应 →DFA 每态对应的 NFA 状态集合

每读一字符按 NFA 转移规则更新整张清单；只要清单里出现 NFA 终态，就算命中

δD(S,a)  =  ⋃q∈SδN(q,a)\delta_{D}(S, a) \;=\; \bigcup_{q \in S} \delta_{N}(q, a)
12第 12 页 · NFA与DFA的等价性

子集构造法步骤

把NFA的状态集合"折叠"成DFA状态——核心算法五步走。

1
起点取ε闭包
把NFA起点s₀的ε闭包作为DFA初始状态——一开始就是状态集合
2
计算move集
对T中每个NFA状态沿a跳一步，收集可达的NFA状态集合
3
再取ε闭包
move后的状态还可能经ε跳更远，必须再包一层ε闭包
4
去重+终态
新集合未出现则加入；含NFA终态的集合即为DFA终态
5
迭代到稳定
对未处理集合重复以上步骤，直到不再产生新集合为止
13第 13 页 · 子集构造法步骤

NFA转DFA实例

左：原NFA接受ab结尾；右：子集构造得到的等价DFA。

图解渲染中…
p：NFA起点r：NFA接受态D2：DFA接受态，含r
14第 14 页 · NFA转DFA实例

NFA与DFA优缺点对比

NFA看起来更灵活强大，但表达能力上两者完全等价。这一页只看工程取舍。

NFA · 非确定
  • 转移函数多值，同一输入可到多个状态
  • 支持 ε 转移，构造直观灵活
  • 状态数通常更少，描述更简洁
  • 模拟需回溯或并行追踪，效率较低
DFA · 确定
  • 转移函数单值，每输入唯一下一状态
  • 无 ε 转移，结构受正则语言约束
  • 最坏状态数指数膨胀（2^n）
  • 可单线程顺序扫描，无需回溯
表达能力等价（NFA可转DFA），但工程复杂度悬殊：描述选NFA，实现选DFA。
15第 15 页 · NFA与DFA优缺点对比

正则表达式与NFA的联系

前页我们把 NFA 翻成了 DFA。现在请出正则表达式——一串符号，像 a|b、(ab)*。它和 NFA 长得不一样，但有一个深刻结论：两者描述语言的能力完全等价，可以双向无损翻译。

Kleene 定理
正则语言、正则表达式、NFA 三者等价，描述能力刻画同一类语言
Thompson 构造
正则式 → NFA：拆解语法树，递归把每个子式变成带 ε 转移的 NFA 片段
状态消除法
NFA → 正则式：把中间状态一个个消掉，每消一个就在剩余边上记录一段正则式
四者等价链
正则语言 = 正则表达式 = NFA = DFA，可任选最顺手的形式来描述和实现
同一首曲子的三种载体对应 →同一正则语言的三种形式

乐谱、录音、MIDI 描述同一曲子，形态不同但可无损互转

16第 16 页 · 正则表达式与NFA的联系

Thompson构造法

Thompson 构造法按正则语法递归拆分，每类操作对应一条规则，最终拼出整个 NFA。

1
处理基本情形
单个符号或 ε，直接画出两状态的最小 NFA
2
并集规则
新起点用 ε 分叉到两条子 NFA，再合并终态
3
连接规则
把第一个 NFA 的终态用 ε 接到第二个的初态
4
闭包规则
新增起点支持绕行与重复的 ε 转移
5
递归组合
解析为语法树后自底向上逐层套用上述规则
17第 17 页 · Thompson构造法

文本搜索NFA应用示例

纵轴是模拟器一步：每读完一字符，把当前可达集R先做δ再做ε闭包，得到下一轮R。

图解渲染中…
a0：起手即ε闭包：s0所有ε可达状态一并并入Ra3：δ*一步的核心：先字符转移，后ε补全a4：每轮循环先判断文本指针是否走完a5：匹配判据：接受态出现在R中即命中
18第 18 页 · 文本搜索NFA应用示例

核心要点回顾

  • ✓NFA与DFA识别能力等价，非确定性不增表达能力
  • ✓子集构造最坏情况下指数膨胀，换取构造简洁
  • ✓ε转移不增表达力，但显著提升建模灵活性
  • ✓δ*以递归方式统一单步与多步的语义
  • ✓NFA是连接正则表达式与自动机的桥梁
延伸主题：DFA状态最小化Myhill-Nerode定理泵引理证明非正则性
19第 19 页 · 核心要点回顾

课后思考

先自己想，再看参考答案；问题没有标准答案，重点是思考路径。

1ε转移让NFA'不读输入就能换状态'。为什么这种'凭空跳转'没让NFA比DFA识别更多语言？

参考答案因为ε闭包只是把所有'无输入可达'的状态预先打包，并未给NFA增加任何DFA做不到的判定能力。

2为什么grep这类文本搜索工具内部用NFA而不是直接用DFA？

参考答案Thompson构造能把正则直接拼成NFA，编译期成本几乎为零；模拟时一次扫描并行尝试多条路径，避免子集构造的指数膨胀。

3子集构造法把NFA转DFA时状态数可能指数爆炸。什么样的语言会触发这种最坏情况？

参考答案关键是构造一个让'部分匹配的可能位置'指数增长的语言——比如(a|b)*a(a|b)^k匹配倒数第k位是a的串，DFA必须记住最近k位才能判定。

20第 20 页 · 课后思考
非确定有限自动机 · 知识图解