跳转至

语言、自动机与正则表达式

约 3850 个字 预计阅读时间 13 分钟

Abstract

理论计算机科学导引第一至第四周课程内容

前言

  • 问题分类
    • 优化问题（Optimization Problem）如最小生成树
    • 搜索问题（Search Problem）如找一棵权重最大为 k 的生成树
    • 决策问题（Decision Problem）如判断是否存在一棵权重最大为 k 的生成树
    • 计数问题（Counting Problem）
  • 决策问题最简单
    • 对于一个问题有 yes-instance 和 no-instance
    • 问题可以转化为 Given a string ww, whether w∈{encoding of yes-instance}w\in \{\text{encoding of yes-instance}\}
    • {encoding of yes-instance}\{\text{encoding of yes-instance}\} 就是一个语言（Language）

语言定义

  • 字母表 Alphabet: finite set of symbols
    • Σ={a,b,c}\Sigma = \{a, b, c\}、Σ={0,1}\Sigma = \{0, 1\}、Σ={ }\Sigma = \{\ \}
  • 字符串 String over Σ\Sigma: finite sequence of symbols from Σ\Sigma
    • w=010101w = 010101，w=ew = e（或 ϵ\epsilon）是空串
    • ∣w∣|w| 表示字符串长度，∣e∣=0|e| = 0
    • Σi\Sigma^i: set of all strings of length ii over Σ\Sigma
    • Σ∗=⋃i≥0Σi\Sigma^* = \bigcup_{i\geq 0} \Sigma^i（Σ\Sigma 上所有字符串），Σ+=⋃i≥1Σi\Sigma^+ = \bigcup_{i\geq 1} \Sigma^i
    • 字符串操作
      • 拼接（concatenation）：w1w2w_1w_2，∣w1w2∣=∣w1∣+∣w2∣|w_1w_2| = |w_1| + |w_2|
      • 反转（reversal）：wRw^R，∣wR∣=∣w∣|w^R| = |w|
      • 重复（exponentiation）：wi=ww⋯w⏟i timesw^i = \underbrace{ww\cdots w}_{i\ times}，∣wi∣=i∣w∣|w^i| = i|w|
  • 语言 Language over Σ\Sigma: any subset of Σ∗\Sigma^*

自动机

自动机（finite automata）有两种：

  • Deterministic Finite Automata (DFA)：确定性有限自动机，每一步的转移都是确定的
  • Non-deterministic Finite Automata (NFA)：非确定性有限自动机，每一步的转移可以有多种选择

DFA

  • 如上图就是一个 DFA，q0q_0 是初始状态，双圈 q1q_1 是接受状态，箭头上的字母是转移条件
  • 一个 NFA 定义为一个五元组 M=(K,Σ,δ,s,F)M = (K, \Sigma, \delta, s, F)
    • KK：状态集合
    • Σ\Sigma：字母表
    • δ\delta：转移函数，δ ⁣:K×Σ→K\delta\colon K\times \Sigma \to K
    • ss：初始状态
    • FF：接受状态集合
  • 执行逻辑：输入一个字符串，从初始状态，每次取出第一个字符，根据当前状态和字符查找转移函数，得到下一个状态，直到字符串为空
  • configuation：C=(q,w)C = (q, w)，表示当前状态 qq 和剩余字符串 ww
  • yields
    • yields in one step：可一步转移到
      • 记为 (q,w)⊢M(q′,w′)(q, w)\vdash_M (q', w')，if w=aw′w=aw' for some a∈Σa\in\Sigma and δ(q,a)=q′\delta(q, a) = q'
    • yields：可转移到
      • 记为 (q,w)⊢M∗(q′,w′)(q, w)\vdash_M^* (q', w')，if (q,w)⊢M(q1,w1)⊢M⋯⊢M(q′,w′)(q, w)\vdash_M (q_1, w_1)\vdash_M \cdots \vdash_M (q', w')
  • 自动机接受字符串
    • MM accepts w∈Σ∗w\in\Sigma^*, if (s,w)⊢M∗(q,e)(s, w)\vdash_M^* (q, e) for some q∈Fq\in F
    • 即可以从初始状态 ss 通过一系列转移得到接受状态 qq，且剩余字符串为空
  • 自动机对应的语言（Language of MM）
    • L(M)={w∈Σ∗:M accepts w}L(M) = \{w\in\Sigma^*: M\text{ accepts }w\}
    • 即所有能被自动机接受的字符串
  • 自动机接受的语言
    • MM accepts LL if MM accepts every string in LL and rejects every string not in LL
    • MM accepts L(M)L(M)

NFA

  • 如上图是一个 NFA，和 DFA 有以下两个区别：
    • 一个状态同一条件可以有多个转移方案
    • 可以有 ee-transition，即不消耗字符的转移
  • 同样定义为五元组 M=(K,Σ,Δ,s,F)M = (K, \Sigma, \Delta, s, F)
    • 和 DFA 区别只在 Δ\Delta，是一个比函数更一般的关系（relation）
    • Δ\Delta：转移关系，Δ⊆K×(Σ∪{e})×K\Delta\subseteq K\times (\Sigma\cup\{e\})\times K
  • 对于一个输入，NFA 可以有多种路线，但只要有一种路线能够接受，就认为 NFA 接受该输入
    • 一种理解方式：NFA 可以猜测该往哪里转移，且总能猜对
Ex. 构造 NFA 接受 L={w∈{a,b}∗:the second symbol from the end is b}L=\{w\in\{a, b\}^*: \text{the second symbol from the end is }b\}

NFA 与 DFA

  • NFA 虽然看起来比 DFA 强大，但其二者实际上是等价的
    • ∀\forall NFA MM，∃\exists DFA M′M'，s.t. L(M)=L(M′)L(M) = L(M')
    • ∀\forall DFA MM，∃\exists NFA M′M'，s.t. L(M)=L(M′)L(M) = L(M')
  • NFA 转 DFA 主要思路
    • NFA 接收一个字符，会有多个转移方案，所有可达的下一状态合在一起的集合构成 DFA 的一个状态
    • 即 DFA 的状态是 NFA 的状态的幂集，结束状态是包含 NFA 的结束状态的 DFA 状态
    • ee-transition 也要考虑，且不算在字符数里
  • NFA M=(K,Σ,Δ,s,F)M=(K, \Sigma, \Delta, s, F) 转为 DFA M′=(K′,Σ,δ,s′,F′)M'=(K', \Sigma, \delta, s', F')
    • K′=2K={Q:Q⊆K}K' = 2^K = \{Q: Q\subseteq K\}
    • F′={Q∈K′:Q∩F≠∅}F' = \{Q\in K': Q\cap F\neq \emptyset\}
    • s′=E(s)s' = E(s)
      • 定义 ∀q∈K,E(q)={p∈K:(q,e)⊢M∗(p,e)}\forall q\in K, E(q) = \{p\in K: (q, e)\vdash_M^* (p, e)\}
      • 即 E(q)E(q) 是 qq 可以通过 ee-transition 到达的状态集合
    • δ\delta: ∀Q∈K′,∀a∈Σ\forall Q\in K', \forall a\in\Sigma
δ(Q,a)=⋃q∈Q ⋃p:(q,a,p)∈ΔE(p) \delta(Q, a) = \bigcup_{q\in Q}\ \bigcup_{p: (q, a, p)\in\Delta}E(p)
一个 NFA 转 DFA 的具体例子

右侧 DFA 的下边部分是冗余的，可以删掉。

正则语言

  • A language is regular if it is accepted by some FA
    • 有自动机可以接受的语言是正则的
  • Regular Operations
    • Union: A∪B={w:w∈A or w∈B}A\cup B = \{w: w\in A\text{ or }w\in B\}
    • Concatenation: A∘B={ab:a∈A and b∈B}A\circ B = \{ab: a\in A\text{ and }b\in B\}
    • Star: A∗={w1w2⋯wk:k≥0 and each wi∈A}A^* = \{w_1w_2\cdots w_k: k\geq 0\text{ and each }w_i\in A\}
  • 定理：
    • 如果 AA 和 BB 是正则语言，则 A∪BA\cup B、A∘BA\circ B、A∗A^* 也是正则语言
  • claim：如果 NFA MM accepts ww，则转为的 DFA M′M' accepts ww，反之也成立
    • Corollary：a language is regular   ⟺  \iff it is accepted by some DFA
Proof. if AA and BB are regular, so is A∪BA\cup B

思路：合并两个接收 AA 和 BB 的 DFA

∃MA=(KA,Σ,δA,sA,FA) accepts A\exists M_A=(K_A, \Sigma, \delta_A, s_A, F_A)\text{ accepts }A，∃MB=(KB,Σ,δB,sB,FB) accepts B\exists M_B=(K_B, \Sigma, \delta_B, s_B, F_B)\text{ accepts }B

let M=(K,Σ,δ,s,F)\text{let }M=(K, \Sigma, \delta, s, F)，where:

  • K=KA×KBK = K_A\times K_B
  • s=(sA,sB)s = (s_A, s_B)
  • F={(qA,qB):qA∈FA or qB∈FB}F = \{(q_A, q_B): q_A\in F_A\text{ or }q_B\in F_B\}
  • δ\delta: ∀qA∈KA,∀qB∈KB,∀a∈Σ, δ((qA,qB),a)=(δA(qA,a),δB(qB,a))\forall q_A\in K_A, \forall q_B\in K_B, \forall a\in\Sigma,\ \delta\big((q_A, q_B), a\big) = \big(\delta_A(q_A, a), \delta_B(q_B, a)\big)

then M accepts A∪B\text{then }M\text{ accepts }A\cup B

Proof. if AA and BB are regular, so is A∘BA\circ B

思路：连接两个接收 AA 和 BB 的 NFA

∃MA=(KA,Σ,ΔA,sA,FA) accepts A\exists M_A=(K_A, \Sigma, \Delta_A, s_A, F_A)\text{ accepts }A，∃MB=(KB,Σ,ΔB,sB,FB) accepts B\exists M_B=(K_B, \Sigma, \Delta_B, s_B, F_B)\text{ accepts }B

let M=(K,Σ,Δ,s,F)\text{let }M=(K, \Sigma, \Delta, s, F)，where:
  • K=KA∪KBK = K_A\cup K_B
  • s=sAs = s_A
  • F=FBF = F_B
  • Δ=ΔA∪ΔB∪{(qA,e,sB):qA∈FA}\Delta = \Delta_A\cup \Delta_B\cup \{(q_A, e, s_B): q_A\in F_A\}

then M accepts A∘B\text{then }M\text{ accepts }A\circ B

Proof. if AA and BB are regular, so is A∗A^*

思路：让一个接收 AA 的 NFA 自己进行循环

∃MA=(KA,Σ,ΔA,sA,FA) accepts A\exists M_A=(K_A, \Sigma, \Delta_A, s_A, F_A)\text{ accepts }A

注意

A∗A^* 包括空串，所以要保证初始状态也是接受状态。但同时又不能让 MAM_A 的初始状态变为接受状态，也不能让其初始状态通过 ee-transition 到达接受状态，否则如果 MAM_A 途中返回初始状态，就可能导致接受了其他不该接受的字符串。所以要新建一个初始状态 ss，通过 ee-transition 到达 sAs_A，且 ss 也是接受状态。

let M=(K,Σ,Δ,s,F)\text{let }M=(K, \Sigma, \Delta, s, F)，where:

  • K=KA∪{s}K = K_A\cup \{s\}
  • s=ss = s（即新建的一个初始状态）
  • F=FA∪{s}F = F_A\cup \{s\}
  • Δ=ΔA∪{(s,e,sA)}∪{(qA,e,sA):qA∈FA}\Delta = \Delta_A\cup \{(s, e, s_A)\}\cup \{(q_A, e, s_A): q_A\in F_A\}

then M accepts A∗\text{then }M\text{ accepts }A^*

Pumping Theorem

可以用来证明一个语言不是正则语言的一个定理。其内容如下：

  • 令 LL 为一个正则语言
  • 则存在一个整数 p≥1p\geq 1（称为 pumping length）
  • 使得对于所有长度不小于 pp 的字符串 w∈Lw\in L
  • 都可以将 ww 分解为三部分 w=xyzw=xyz，满足：
    1. 对于任意 k≥0k\geq 0，有 xykz∈Lxy^kz\in L
    2. ∣y∣≥1|y|\geq 1
    3. ∣xy∣≤p|xy|\leq p
Proof

如果 LL 是有限的，那么令 p=max⁡w∈L∣w∣+1p=\displaystyle\max_{w\in L}|w|+1 即可满足所有要求。

如果 LL 是无限的，因为其是正则语言，所以存在一个 DFA MM 接受 LL。令 pp 为 MM 的状态数，即 p=∣K∣p=|K|。

令 w∈Lw\in L 且 ∣w∣≥p|w|\geq p，现假设 w=a1a2⋯anw=a_1a_2\cdots a_n，则该自动机一定包含如下一条路径：

因为自动机只有 pp 个状态，但 nn 又不小于 pp，所以一定存在 0≤i<j≤p0\leq i < j\leq p，使得 qiq_i 和 qjq_j 是同一状态。这样这条路径就可以转化为：

因此 xykz∈Lxy^kz\in L、∣y∣=j−1≥1|y|=j-1\geq 1、∣xy∣=j≤p|xy|=j\leq p 都满足。

证明 L={0n1n:n≥0}L = \{0^n1^n:n\geq 0\} 不是正则语言

反证法，假设 LL 是正则的，令 pp 为其 pumping length。

根据 pumping theorem，0p1p∈L0^p1^p\in L 可以被写成 0p1p=xyz0^p1^p=xyz，满足：

  • xykz∈L,∀k≥0xy^kz\in L, \forall k\geq 0
  • ∣y∣≥1|y|\geq 1
  • ∣xy∣≤p|xy|\leq p

由后两条可以推出 y=0ty=0^t（其中 t≥1t\geq 1），那么令 k=0k=0，有 xykz=xy0z=xz=0p−t1pxy^kz=xy^0z=xz=0^{p-t}1^p，但这个字符串不在 LL 中，不符合第一条，产生矛盾，所以 LL 一定不是正则语言。

正则表达式

一个正则表达式由以下规则定义：

  • Atomic：对于 ∅\emptyset 对应语言 L(∅)=∅L(\emptyset)=\emptyset，对于 a∈Σa\in\Sigma 有 L(a)={a}L(a)=\{a\}
  • Composite：
    • R1∪R2R_1\cup R_2 对应语言 L(R1∪R2)=L(R1)∪L(R2)L(R_1\cup R_2) = L(R_1)\cup L(R_2)
    • R1R2R_1R_2 对应语言 L(R1R2)=L(R1)∘L(R2)L(R_1R_2) = L(R_1)\circ L(R_2)
    • R1∗R_1^* 对应语言 L(R1∗)=L(R1)∗L(R_1^*) = L(R_1)^*
    • 优先级：∗>∘>∪^* > \circ > \cup
      • Ex. ab∗∪b∗a=(a(b∗))∪((b∗)a)ab^*\cup b^*a=\big(a(b^*)\big)\cup\big((b^*)a\big)

其实就类似于各编程语言中使用的正则表达式，不过那些正则表达式一般都加了不属于这里规定的正则表达式的更多功能（比如记录捕获组并在 \1 时引用捕获内容）。

例子
  • ∅∗\emptyset^* 对应语言 {e}\{e\}
  • a(a∪b)∗ba(a\cup b)^*b 对应语言 {w∈{a,b}∗:w starts with a and ends with b}\{w\in\{a, b\}^*: w\text{ starts with }a\text{ and ends with }b\}
  • (a∪b)∗a(a∪b)∗a(a∪b)∗(a\cup b)^*a(a\cup b)^*a(a\cup b)^* 对应语言 {w∈{a,b}∗:w contains at least two a’s}\{w\in\{a, b\}^*: w\text{ contains at least two }a\text{'s}\}

一般用 RR 表示正则表达式，用 L(R)L(R) 表示正则表达式对应的语言（匹配的字符串集合）。

  • 给定一个 NFA MM，要找一个正则表达式 RR 使得 L(R)=L(M)L(R) = L(M)
  • 考虑化简 MM，且需要满足要求：
    • 初始状态没有入边
    • 只有一个没有出边的接受状态
  • 化简思路：加一个初始状态和接受状态，用 ee-transition 连接到原来的初始状态和接受状态，然后删除原来的初始状态和接受状态，再逐一删除中间状态
一个化简的示例

要化简的自动机如下（已经修改了初始状态和接受状态，原来 q1q_1 初始 q3q_3 接受）：

删掉状态 q1q_1（影响到 q4→q3q_4\to q_3 和 q2→q3q_2\to q_3 两条路径）：

删掉状态 q2q_2（影响到 q3→q3q_3\to q_3 路径）：

删掉状态 q3q_3：

所以该自动机对应的正则表达式为 R=a∗b(a∪ba∗ba∗b)∗R = a^*b(a\cup ba^*ba^*b)^*

形式化描述

设 NFA M=(K,Σ,Δ,s,F)M=(K, \Sigma, \Delta, s, F)，其中：

  • K={q1,q2,⋯ ,qn}K = \{q_1, q_2, \cdots, q_n\}，s=qn−1s = q_{n-1}，F={qn}F = \{q_n\}
  • (p,a,qn−1)∉Δ(p, a, q_{n-1})\notin\Delta，∀p∈K,∀a∈Σ\forall p\in K, \forall a\in\Sigma
  • (qn,a,p)∉Δ(q_n, a, p)\notin\Delta，∀p∈K,∀a∈Σ\forall p\in K, \forall a\in\Sigma

求 RR 使得 L(R)=L(M)L(R) = L(M)。

采用动态规划思想，划分子问题：对于 i,j∈[1,n]i, j\in[1, n] 以及 k∈[0,n]k\in[0, n] 定义 Lijk={w∈Σ∗:w drive M from qi to qj with no intermediate state having index >k}L_{ij}^k=\{w\in\Sigma^*: w\text{ drive M from }q_i\text{ to }q_j\text{ with no intermediate state having index }>k\}

  • 即 LijkL_{ij}^k 表示从 qiq_i 到 qjq_j 的路径表示的语言，且中间状态的下标不大于 kk
    • 注意中间状态不包含首尾
  • 记 LijkL_{ij}^k 对应的正则表达式为 RijkR_{ij}^k
使用前面的自动机的例子

  • L110={e,a}L_{11}^0 = \{e, a\}，对应 R110=∅∗∪aR_{11}^0 = \emptyset^*\cup a
    • 注意 aaaa 不属于 L110L_{11}^0 因为有中间状态 q1q_1，其下标大于 0
  • L130={b}L_{13}^0 = \{b\}，对应 R120=bR_{12}^0 = b
  • L411={e,a,aa,⋯ }L_{41}^1 = \{e, a, aa, \cdots\}，对应 R411=∅∗∪aa∗R_{41}^1 = \emptyset^*\cup aa^*

动态规划过程部分：

  • 目标：R(n−1)nn−2R_{(n-1)n}^{n-2}
  • 起始已知：
    • k=0 and if i=jk=0\text{ and if }i=j，有 Lii0={e}∪{a:(qi,a,qi)∈Δ}L_{ii}^0 = \{e\}\cup\{a: (q_i, a, q_i)\in\Delta\}，可写出正则表达式 Rii0R_{ii}^0
    • k=0 and if i≠jk=0\text{ and if }i\neq j，有 Lij0={a:(qi,a,qj)∈Δ}L_{ij}^0 = \{a: (q_i, a, q_j)\in\Delta\}，可写出正则表达式 Rij0R_{ij}^0
  • 递推关系：Lijk=Lijk−1∪ ?L_{ij}^k = L_{ij}^{k-1}\cup\ ?
    • 中间过程有若干次会到达 qkq_k，依此来进行划分，有 Likk−1L_{ik}^{k-1}、Lkkk−1L_{kk}^{k-1}（若干次）、Lkjk−1L_{kj}^{k-1} 几个阶段
    • 连接起来有 Lijk=Lijk−1∪Likk−1∘(Lkkk−1)∗∘Lkjk−1L_{ij}^k = L_{ij}^{k-1}\cup L_{ik}^{k-1}\circ\big(L_{kk}^{k-1}\big)^*\circ L_{kj}^{k-1}
    • 因此对应正则表达式有 Rijk=Rijk−1∪Rikk−1(Rkkk−1)∗Rkjk−1R_{ij}^k = R_{ij}^{k-1}\cup R_{ik}^{k-1}\big(R_{kk}^{k-1}\big)^*R_{kj}^{k-1}

有以上这些关系，进行动态规划递推即可求解最终的正则表达式。

最后更新: 2023年10月18日 22:31:40
创建日期: 2023年9月29日 01:01:14
回到页面顶部