mem.academic
5 min read

Ch2 Finite Automata & Regular Languages

memset0
memset0
Jul 14, 2026

Deterministic Finite Automata

Definition

(Deterministic Finite Automata, DFA) 用五元组 (K,Σ,δ,s,F)(K,\Sigma,\delta,s,F) 表示：

  • KK 是由状态构成的有限集合。
  • Σ\Sigma 是字母表／字符集。
  • s∈Ks\in K 是起始状态。
  • F⊆KF\subseteq K 是接受状态的集合。
  • δ:K×Σ→K\delta:K\times\Sigma\to K 为状态转移函数。
Note

转移函数可以通过表格的形式给出。

(State Diagram of FA)

【占位：FA 状态图示例】

Configuration

Tip

为了描述机器处理字符串的动态过程，我们需要引入格局 (Configuration) 的概念。

(DFA Configuration) 一个属于 K×Σ∗K\times\Sigma^* 的元素 (q,w)(q,w)，这里 qq 是 DFA 的当前状态 (current state)，ww 是剩余未读的字符串 (remaining unread string)。

Derivation

(DFA One-Step Derivation) 定义一种格局间的二元关系 ⊢M\vdash_M 来描述消耗一个字符进行转移的过程，用英文说是 (q,w)(q,w) yields/derives (q′,w′)(q',w') in one step。需要满足：

(q,w)⊢M(q′,w′)⟺∃a∈Σ, w=aw′，并且 δ(q,a)=q′(q,w)\vdash_M(q',w')\Longleftrightarrow\exists a\in\Sigma,\ w=aw'\text{，并且 }\delta(q,a)=q'
Note

这里 ww 和 w′w' 只能相差开头的一个字符，即我们进行这一步推导所消耗的字符。

在此基础之上定义 ⊢M∗\vdash_M^* 描述消耗 0 个或任意 nn 个字符进行转移的过程，⊢M∗\vdash_M^* 是 ⊢M\vdash_M 的自反传递闭包 (reflexive, transitive closure)。若 (q,w)⊢M∗(q′,w′)(q,w)\vdash_M^*(q',w')，则可以说 (q,w)(q,w) yields/derives (q′,w′)(q',w')。

(DFA Acceptance) 字符串 w∈Σ∗w\in\Sigma^* 能被有限自动机 MM 接受 (accepted)，当且仅当存在状态 q∈Fq\in F 满足 (s,w)⊢M∗(q,ε)(s,w)\vdash_M^*(q,\varepsilon)。被 MM 接受的语言（字符串构成的集合）称为 L(M)L(M)。

Warning

注意：空串 ε\varepsilon 能被接受，当且仅当起始状态 (start state) 是接受状态 (accepting state)。

Example

设计一个接受语言 L1={w∈{a,b}∗:w does not contain three consecutive b’s}L_1=\{w\in\{a,b\}^*:w\text{ does not contain three consecutive }b\text{'s}\} 的 DFA。

【占位：不包含连续三个 b 的 DFA 示例】

Example

设计一个接受语言 L2={w∈{a,b}∗:w contains three consecutive b’s}L_2=\{w\in\{a,b\}^*:w\text{ contains three consecutive }b\text{'s}\} 的 DFA。

【占位：包含连续三个 b 的 DFA 示例】

Warning

这里的两种语言 L1,L2L_1,L_2 可以记为 L2=Σ∗−L1L_2=\Sigma^*-L_1。

Nondeterministic Finite Automata

Definition

Tip

DFA 要求每一步都转移到确定的状态，这在设计复杂语言的自动机时很麻烦，因此我们引入转移有多种路径可选的 NFA，并会证明 DFA 和 NFA 是等价的。

(Nondeterministic Finite Automata, NFA) 用五元组 (K,Σ,Δ,s,F)(K,\Sigma,\Delta,s,F) 表示：

  • KK 是由状态构成的有限集合。
  • Σ\Sigma 是字母表／字符集。
  • s∈Ks\in K 是起始状态。
  • F⊆KF\subseteq K 是接受状态的集合。
  • Δ⊆K×(\Delta\subseteq K\times( Σ∪{ε}\Sigma\cup\{\varepsilon\} )×K)\times K 为状态转移关系。
Note

在 DFA 中，状态转移 δ\delta 是一个函数 (function)，但在 NFA 中，状态转移 Δ\Delta 是一个关系 (relation)。

特别地，在 NFA 的状态转移关系中，我们允许空移动 (e-move)，即不消耗字符从一个状态转移到另一个状态 (q,ε,p)(q,\varepsilon,p)。

为以下语言设计 NFA

【占位：NFA 设计示例】

DFA/NFA Equivalence

(DFA/NFA Equivalence) 任给一个 DFA，都存在与其等价的 NFA，反之亦然。

Proof

⟹\Longrightarrow：DFA 显然是 NFA，只需要将 (k,a)↦s′∈δ(k,a)\mapsto s'\in\delta 改写为 (k,a,s′)∈Δ(k,a,s')\in\Delta 即可。

⟸\Longleftarrow：为了构造等价的 DFA，我们引入等价状态的概念：从某一状态 qq 出发，只通过 e-move（不消耗字符的转移）能够到达的状态集合

E(q)={p∈K:(q,ε)⊢M∗(p,ε)}E(q)=\{p\in K:(q,\varepsilon)\vdash_M^*(p,\varepsilon)\}

是这一状态的等价状态。先不给出证明，构造等价 DFA M′M' 的方法如下——通过将状态集拓展为原先的幂集，使转移变成从一组等价状态到另一组等价状态：

  1. K′=2KK'=2^K，即原来状态的幂集。
  2. Σ′=Σ\Sigma'=\Sigma，字母表不变。
  3. s′=E(s)s'=E(s)，即原始状态的等价集合。
  4. F′={Q∣Q⊆K,Q∩F≠∅}F'=\{Q\mid Q\subseteq K,Q\cap F\ne\varnothing\}，即所有与原来的终止状态有交集的集合。
  5. 对于任意集合 Q⊆KQ\subseteq K 和 a∈Σa\in\Sigma，令
δ(Q,a)=⋃{E(p)∣q∈Q,(q,a,p)∈Δ}\delta(Q,a)=\bigcup\{E(p)\mid q\in Q,(q,a,p)\in\Delta\}

为了证明构造的 DFA 与给定的 NFA 等价，需要证明 w∈L(M)⟺w∈L(M′)w\in L(M)\Longleftrightarrow w\in L(M')。为此，先给出一个更强的断言：

(q,w)⊢M∗(p,ε)⟺(E(q),w)⊢M′∗(P,ε),p∈P(q,w)\vdash_M^*(p,\varepsilon) \Longleftrightarrow (E(q),w)\vdash_{M'}^*(P,\varepsilon),\quad p\in P

也就是说，如果在 NFA 中状态 qq 可以通过消耗字符串 ww 转移到状态 pp，那么在等价 DFA 中，qq 的等价状态 E(q)E(q) 可以通过字符串 ww 转移到一个包含 pp 的状态 PP。这是因为在 NFA 中，别的转移可能到达更多的可能状态。

在这个断言的基础上，可以证明：

w∈L(M)⟺(s,w)⊢M∗(f,ε), f∈F⟺(E(s),w)⊢M′∗(Q,ε), f∈Q⟺(s′,w)⊢M′∗(Q,ε), Q∈F′⟺w∈L(M′).\begin{aligned} w\in L(M) &\Longleftrightarrow(s,w)\vdash_M^*(f,\varepsilon),\ f\in F\\ &\Longleftrightarrow(E(s),w)\vdash_{M'}^*(Q,\varepsilon),\ f\in Q\\ &\Longleftrightarrow(s',w)\vdash_{M'}^*(Q,\varepsilon),\ Q\in F'\\ &\Longleftrightarrow w\in L(M'). \end{aligned}

只需证明上面的强断言。因为不知道字符串 ww 的长度，可以使用数学归纳法：

Basis Step：若 w=εw=\varepsilon 是空串（∣w∣=0|w|=0），则 qq 能转移到的 pp 都包含在其等价状态 E(q)E(q) 中；对应到 DFA 中，就是 E(q)E(q) 经过 0 步推导到自身，即 p∈P=E(q)p\in P=E(q)。

Induction Step：设 ∣w∣=k+1|w|=k+1，w=vaw=va，其中 a∈Σa\in\Sigma、v∈Σ∗v\in\Sigma^*。分别证明两个方向。

⟹\Longrightarrow：在 NFA 的转移过程中，存在两个中间状态 r1,r2r_1,r_2，使得

(q,va)⊢M∗(r1,a)⊢M(r2,ε)⊢M∗(p,ε).(q,va)\vdash_M^*(r_1,a)\vdash_M(r_2,\varepsilon)\vdash_M^*(p,\varepsilon).

【占位：DFA/NFA 等价证明的归纳步骤（正向）】

⟸\Longleftarrow：

【占位：DFA/NFA 等价证明的归纳步骤（反向）】

给定 NFA，构造等价 DFA

先通过 e-move 把等价状态构建出来。

【占位：由 NFA 构造等价 DFA 的示例】

Regular Language

Tip

正则表达式是一种描述性的语言，可以方便我们定义什么串是合法的。稍后我们会证明正则表达式和 DFA/NFA 等价。

Regular Expression

(Regular Expression) 在字母表 Σ\Sigma 下，可以通过以下方式构造正则表达式：

  1. ∅\varnothing 和 a∈Σa\in\Sigma 是正则表达式。
  2. 若 α\alpha 和 β\beta 是正则表达式，则 (αβ)(\alpha\beta) 也是正则表达式。
  3. 若 α\alpha 和 β\beta 是正则表达式，则 (α∪β)(\alpha\cup\beta) 也是正则表达式。
  4. 若 α\alpha 是正则表达式，则 α∗\alpha^* 也是正则表达式。
Note
  • 三种积木：空集 ∅\varnothing、空串 ε\varepsilon 和单字符 a∈Σa\in\Sigma；
  • 三种胶水：并 ∪/+\cup/+ 、连接、Kleene Star ∗*。

正则表达式的性质

  • S∪R=R∪SS\cup R=R\cup S
  • R(ST)=(RS)TR(ST)=(RS)T
  • R(S∪T)=RS∪RTR(S\cup T)=RS\cup RT，(R∪S)T=RT∪ST(R\cup S)T=RT\cup ST
  • ∅∗={ε}\varnothing^*=\{\varepsilon\}
  • (R∗S∗)∗=(R∪S)∗(R^*S^*)^*=(R\cup S)^*

Regular Language

(Regular Language) 能被正则表达式 r∈Rr\in\mathcal R 表示的语言 LL 是正则语言。

FA/RL Equivalence

(FA/RL Equivalence) 正则语言和自动机能识别的语言是等价的。一个语言是正则语言，当且仅当它可以被一个有限自动机 MM 识别，记为 L=L(M)L=L(M)。

Note

为了证明这一点，我们将给出：

  1. 给定任意正则表达式，将其递归地转化为 FA 的方法。
  2. 给出任意 FA，将其递归地转化为正则表达式的方法——先将其转化为 GFA，再缩到只有两个点，这时所剩唯一边上的正则表达式就是该 FA 所识别的正则表达式。

RL Closure Properties

Tip

在考试中，我们经常需要判断“一个语言是不是正则的”。通过正则语言的封闭性，我们可以构造一些显然是正则语言的语言，然后通过运算得到需要判断的语言。

(正则语言的封闭性) 自动机能接受的语言在并、连接、Kleene Star、补、交运算下封闭。

通过证明这一定理，我们实际上得到了把正则表达式转换为 DFA 的方法。

Proof
  • 并 (union)：构造一个新初始状态 s′s'，这个状态可以通过 e-move 到两个 NFA 的初始状态。
  • 连接 (concatenation)：只需要把前一个 NFA 的所有终止状态通过 e-move 连到后一个 NFA 的起始状态即可。
  • Kleene Star：本质上只需要增加一条从终止状态到起始状态的回路，但由于还可能识别 0 次，所以还需要增加一个新的初始状态。

【占位：并运算的 NFA 构造】

  • 补 (complementation)：只需要反转 DFA 的终止状态集合，即令 F′=K′∖FF'=K'\setminus F。这一步需要在 DFA 而不能在 NFA 上操作，因为 NFA 的拒绝条件是所有路径都到不了终止状态。
  • 交 (intersection)：由 De Morgan’s Law 可以得出在补集和并集下封闭蕴含了在交集下封闭：
L(M1)∩L(M2)=Σ∗∖((Σ∗∖L(M1))∪(Σ∗∖L(M2))).L(M_1)\cap L(M_2) =\Sigma^*\setminus\left((\Sigma^*\setminus L(M_1))\cup(\Sigma^*\setminus L(M_2))\right).
Example

判断给定语言是否为正则语言。

【占位：正则与非正则语言示例】

Example

证明 L={w∈{a,b}∗:w 中 a,b 的数量相等}L=\{w\in\{a,b\}^*:w\text{ 中 }a,b\text{ 的数量相等}\} 不是正则语言。

Proof

已知 LknownL_{\mathrm{known}} 是正则语言。如果 LtargetL_{\mathrm{target}} 也是正则语言，那么 Ltarget∩LknownL_{\mathrm{target}}\cap L_{\mathrm{known}} 也必须是正则语言。如果交集是一个已知的非正则语言，则假设不成立，LtargetL_{\mathrm{target}} 一定是非正则语言。

直接用 Pumping Lemma 证明比较麻烦，因为 a,ba,b 可以按任意顺序穿插。取正则语言 R=a∗b∗R=a^*b^*，则

L∩R={anbn∣n≥0}.L\cap R=\{a^nb^n\mid n\ge 0\}.

但 {anbn∣n≥0}\{a^nb^n\mid n\ge 0\} 是已知的非正则语言，因此 LL 一定不是正则语言。

Generalized Finite Automaton

(广义有限自动机, Generalized Finite Automaton, GFA) MG=(KG,ΣG,ΔG,sG,FG)M_G=(K_G,\Sigma_G,\Delta_G,s_G,F_G) 是从 NFA M=(K,Σ,Δ,s,F)M=(K,\Sigma,\Delta,s,F) 拓展得到的：

  1. GMG_M 只有一个终止状态。
  2. ΣG=Σ∪R0\Sigma_G=\Sigma\cup R_0，其中 R0R_0 是一个有限的正则表达式集合。即边不仅可以是单个字符，也可以是一个正则表达式。
  3. ΔG⊆K×(Σ∪{ε}∪R)×K\Delta_G\subseteq K\times(\Sigma\cup\{\varepsilon\}\cup R)\times K：GMG_M 的转移可以通过空串、字母或者正则表达式来表示。
  4. 规范化约束：没有进入初始状态或者离开终止状态的转移。

(DFA/NFA to GFA) 为满足 GFA 中新增的规范化约束，需要添加新的起始状态与终止状态，并在它们和原来的起始状态、终止状态之间添加 e-move，中间的边不需要改动。

【占位：DFA/NFA 转换为 GFA】

因为 MM 和 MGM_G 的语言没有变化，L(M)=L(MG)L(M)=L(M_G)，因此称两者等价，记为 M≈MGM\approx M_G。

(FA/GFA to Regular Expression) 若一个语言能被某个自动机接受，那么它能被一个正则表达式识别。

Proof

给定 DFA 或 NFA，都可以转化为等价的 GFA。逐步消除 GFA 的中间状态，直到只剩下两个节点和一条边；此时唯一边上的正则表达式 rr 就是这个 GFA 所识别的正则语言，记为 L(M)=rL(M)=r。

简流版：依次删除 GFA 中的节点。入边和出边通过连接 (concatenation) 合并，然后把对应起点、终点之间已有的表达式通过并 (union) 与新构造的表达式合并。如果删除的节点有自环，则对应 Kleene Star 运算。

形式化版：给定 FA MM，把 MM 的所有状态排成序列 K:q1,q2,…,qnK:q_1,q_2,\ldots,q_n。

定义

R(i,j,k)={w∈Σ∗:(qi,w)⊢M,k∗(qj,ε)},R(i,j,k)=\{w\in\Sigma^*:(q_i,w)\vdash_{M,k}^*(q_j,\varepsilon)\},

表示所有从 qiq_i 到 qjq_j 的路径所构成的字符串，其中路径经过编号小于等于 kk 的点 q1,…,qkq_1,\ldots,q_k。注意 R(i,j,0)R(i,j,0) 表示不经过任意中间状态，只能直接相连。

因为

L(M)=⋃{R(1,j,n):qj∈F,q1=s},L(M)=\bigcup\{R(1,j,n):q_j\in F,q_1=s\},

所以只需证明所有 R(i,j,k)R(i,j,k) 都是正则语言，就能证明 L(M)L(M) 是正则语言。接下来使用归纳法构造正则表达式。

【占位：GFA 消除状态的归纳构造】

所有添加了第 kk 个点后新增的路径，肯定都经过了 kk 这个点至少一次；由于也可能经过多次，因此需要 Kleene Star。

Nonregular Languages

Tip

前面我们讨论了有限自动机能做什么（正则语言），但还有很多有限自动机不能做的语言，即不是正则语言的语言。这是学习计算理论课程中非常关键的一步——划定计算模型的边界。

正则语言的数量是可数无穷 (countably infinite) 的，而语言的数量是不可数的。

一些不是正则语言的例子（zq 说都需要记忆）

【占位：非正则语言示例列表】

Pumping Lemma

(Pumping Theorem) 设 LL 是正则语言，则存在整数 n≥1n\ge 1，使得对于任意字符串 w∈Lw\in L，若 ∣w∣≥n|w|\ge n，则可以将其写成 w=xyzw=xyz，并满足：

  1. y≠εy\ne\varepsilon；
  2. ∣xy∣≤n|xy|\le n；
  3. 对于所有 i≥0i\ge 0，均有 xyiz∈Lxy^iz\in L。

可以利用 Pumping Lemma 和反证法来证明一个语言不是正则的。 具体来说，对于任意的 nn，都需要给出串 ww 的构造，使得无论怎样将 ww 切分为 w=xyzw=xyz，都能找到一个 w′=xyizw'=xy^iz 不在 LL 里。

Note

AI 把使用这个反证的过程比喻为一个游戏过程：

  1. 假设 (Assumption)：假设 LL 是正则语言（为了反证）。
  2. 对手出招 (nn)：因为假设正则，根据泵引理，对手给出一个泵长度 nn。
    • 注意：你不知道 nn 是多少，只能把它当成一个符号处理。
  3. 你出招 (ww)：选择一个属于 LL 且长度至少为 nn 的字符串 ww。
    • 策略：选择一个“即使有环，一旦重复就会破坏结构”的特殊字符串。通常选包含 nn 的串。
  4. 对手出招 (xyzxyz)：对手把 ww 切成三段 xyzxyz。
    • 限制：对手必须遵守 ∣xy∣≤n|xy|\le n 和 y≠εy\ne\varepsilon，但具体 x,y,zx,y,z 是什么由对手决定。
    • 策略：因为不知道对手怎么切，后续证明必须对所有可能的切分都成立。
  5. 你出绝招 (ii)：选择重复次数 ii，构造新串 w′=xyizw'=xy^iz。
  6. 判定 (Contradiction)：如果能证明新串 w′∉Lw'\notin L，就产生了矛盾，说明原假设错误，LL 不是正则语言。
Example

证明 L={aibi∣i≥0}L=\{a^ib^i\mid i\ge 0\} 不是正则语言。

【占位：使用 Pumping Lemma 证明 aibia^ib^i 非正则】

通过在前面放连续 nn 个 aa，使得 y=aiy=a^i。

Comments