自动机理论、语言和计算导论

这是《自动机理论、语言和计算导论》的学习笔记。

第一章 自动机：方法与体验 | 第二章 有穷自动机

字母表、串、语言和问题

字母表

字母表 是符号的有穷非空集合，记为 $\Sigma$。

串

串（单词） 是从某个字母表中选择的符号组成的有穷序列。

• 串的长度

  选择出来的符号个数被称为串的长度。

• 空串 $\varepsilon$

  它的长度为 $0$，是可以从任何字母表中选择的串。但它不属于任何字母表。$\varepsilon \not\in \Sigma$。

• 字母表的幂

  如果 $\Sigma$ 是一个字母表，则 $\Sigma^k$ 表示这个字母表长度为 $k$ 的所有串所组成的集合。

$$\begin{aligned} \Sigma^0 &= \{\varepsilon\} \\ \Sigma^{+} &= \Sigma^1\cup\Sigma^2\cup\Sigma^3\cdots \\ \Sigma^{*} &= \Sigma^{+} \cup \{\varepsilon\} \end{aligned}$$

语言

设 $\Sigma$ 为一个字母表，$L \subseteq \Sigma^{*}$ 被称为 $\Sigma$ 上的 语言。

• 空语言 $\varnothing$ 与只包含空串的语言 $\{\varepsilon\}$

  $\varnothing$ 和 $\{\varepsilon\}$ 都是任意字母表上的语言，但 $\varnothing \neq \{\varepsilon\}$，前者没有串，后者有一个串。

• 若 $L$ 是 $\Sigma$ 上的语言，则 $L$ 是任何是 $\Sigma$ 的超集的字母表上的语言。

问题

在自动机理论中，一个 问题 就是 “判定一个给定的串是否属于某个具体语言” 这一行为。

问题和语言是可以相互等价的。如果 $\Sigma$ 是字母表，$L$ 是 $\Sigma$ 上的语言，则问题 $L$ 就是“给定 $\Sigma^{*}$ 中的一个串 $w$，判断 $w$ 是否属于 $L$。这说明 $L$ 是一个语言，也可以被看成是一个问题。

有穷自动机的形式化定义

确定性有穷自动机（DFA）

通常使用一个五元组 $A = (Q, \Sigma, \delta, q_0, F)$ 来表示一个 DFA。其中 $A$ 是 DFA 的名称，$Q$ 是状态集合，$\Sigma$ 是输入符号，$\delta$ 是转移函数，$q_0$ 是初始状态，$F$ 是接受状态集合。

DFA 的表示方法

• 转移图

  graph LR
  
  
  style Start fill:none,stroke-width:0px
  
  
  Start --> A(($q_0$))
  
  A --> |$0$| C(($q_2$))
  
  A --> |$1$| A
  
  C --> |$0$| C
  
  C --> |$1$| B((($q_1$)))
  
  B --> |$0, 1$| B
  

  初始状态用 Start 指示，接受状态用双圆圈标记（例如 $q_1$）。

• 转移表

  我们也可以使用转移表来直观地表示一个 DFA，着重强调它的转移函数 $\delta$。

  	$0$	$1$
  $\to q_0$	$q_2$	$q_0$
  $*q_1$	$q_1$	$q_1$
  $q_2$	$q_2$	$q_1$

  初始状态用箭头标记，接受状态用星号标记。

转移函数 $\delta$

本质上就是转移图上的有向边，边权为字母表中的字符。

• 扩展转移函数 $\hat\delta$

  感性地说，就是 让转移函数的自变量不再限于单个字符，而是可以给定一个串，它能在自动机上从给定状态开始，沿着转移图的边走，一直走到它最终对应的状态。

  形式化的定义如下：

  基础：$\hat\delta(q, \varepsilon) = q$。

  归纳：$\hat\delta(q, w) = \delta(\hat\delta(q, x), a)$，其中 $w = xa$。

DFA 的语言

定义 DFA $A = (Q, \Sigma, \delta, q_0, F)$ 的语言 $L(A)$ 如下：

$$L(A) = \{w | \hat\delta(q_0, w) \in F\}$$

$L(A)$ 是 $A$ 的 所有可接受的串 所组成的集合。如果对于某个 DFA $A$ 来说 $L$ 是 $L(A)$，则我们称 $L$ 是一个 正则语言。

非确定性有穷自动机（NFA）

NFA 就是多线程 DFA（确信）

在读入每个串的时候，NFA 可以向多个方向同时转移，最后只取可接受状态组成的状态集合。

NFA 的表示方法

转移表既可以表示 NFA 的转移函数，也可以用来规定 DFA 的转移函数，区别在于，NFA 转移表中的 每一项都是集合，即使是单元素集合；如果在某个状态上不存在向其他状态的转移时，应该填入 $\varnothing$。

转移函数 $\delta$

• 扩展转移函数 $\hat\delta(q, w)$

  形式化的表述如下：

  基础：$\hat\delta(q, \varepsilon) = \{q\}$。

  归纳：$\hat\delta(q, w) = \bigcup\limits_{p \in \hat\delta(q, x)}\delta(p, a)$，其中 $w = xa$。

NFA 的语言

相应地，由于 NFA 可以同时向多个方向转移，所以对于一个串来说，只要存在一个状态使得 NFA 能接受该串，那么这个串就属于这个 NFA 对应的语言。

$$L(A) = \{w | \hat\delta(q_0, w) \cap F \neq \varnothing\}$$

DFA 和 NFA 的区别与联系

DFA 和 NFA 之间的唯一区别在于，$\delta$ 在 DFA 的情况下，返回的是 单个状态；而在 NFA 的情况下，返回的是一个 状态集合。

DFA 和 NFA 的等价性

显然一个 DFA 可以转化成一个 NFA，只需要把状态中的每个元素写成其对应的单元素集合即可。重点在于怎么通过一个 NFA $N = (Q_N, \Sigma, \delta_N, \{q_0\}, F_N)$ 开始，描述一个 DFA $D = (Q_D, \Sigma, \delta_D, q_0, F_D)$ 使得 $L(N) = L(D)$。可以采用 子集构造 的方式来解决此问题。

• $Q_D = P(Q_N)$，即 $Q_D$ 是 $Q_N$ 的幂集合。但值得注意的一点是，虽然它们是“集合”，但它们是单个状态，而不是状态的集合。换句话说，构造出来的 $D$ 中，每个状态本身都是集合。
• $F_D = \{S \subseteq Q_N | S \cap F_N \neq \varnothing\}$。也就是说，$F_D$ 是所有至少含有一个 $N$ 的接受状态的 $N$ 的状态集合的集合。
• 对于每个集合 $S \subseteq Q_N$ 以及 $a \in \Sigma$，构造转移函数如下： $$\delta_D(S, a) = \bigcup_{p \in S}\delta_N(p, a)$$ 也就是说，对于 $S$ 中所有状态 $p$，在 $N$ 中从 $p$ 上通过输入 $a$ 进入的状态，这些状态的并集，就是 $\delta_D(S, a)$。

定理：如果 $D = (Q_D, \Sigma, \delta_D, \{q_0\}, F_D)$ 是用子集构造从 NFA $N = (Q_N, \Sigma, \delta_N, q_0, F_N)$ 构造出来的 DFA，那么 $L(D) = L(N)$。

证明：只需证明 $\hat\delta_D(\{q_0\}, w) = \hat\delta_N(q_0, w)$。

基础：设 $|w| = 0$，则 $w = \varepsilon$，显然有 $\hat\delta_D(\{q_0\}, \varepsilon) = \hat\delta_N(q_0, \varepsilon)$。

归纳：设 $|w| = n + 1$，且命题对 $|v| = n$ 的所有 $v$ 均成立。记 $w = xa$，假设 $\hat\delta_D(\{q_0\}, x) = \hat\delta_N(q_0, x) = \{p_1, p_2, \cdots, p_k\}$。

由 NFA 的 $\hat\delta$ 的定义的归纳部分说明 $\hat\delta(q_0, w) = \cup_{i = 1}^k\delta_N(p_i, a)$。另一方面，子集构造说明 $\delta_D(\{p_1, p_2, \cdots, p_k\}, a) = \cup_{i = 1}^k\delta_N(p_i, a)$。因此

$$\hat\delta_D(\{q_0\}, w) = \delta_D(\hat\delta_D(\{q_0\}, x), a) = \delta_D(\{p_1, p_2, \cdots, p_k\}, a) = \bigcup_{i = 1}^k\delta_N(p_i, a) = \hat\delta(q_0, w)$$

所以对于某个串 $w$ 而言，它在 $D$ 和 $N$ 中的可达性是相同的。

因此 $\hat\delta_D(\{q_0\}, w)q_{n - 1} = \hat\delta_N(q_0, w) \iff L(D) = L(N)$。命题得证。

graph LR

style Start fill:none,stroke-width:0px

Start --> A(($q_0$))
A --> |$0, 1$| A
A --> |$0$| B(($q_1$))
B --> |$1$| C((($q_2$)))

这是一个接受所有以 01 结尾的 01 串的 NFA。它所对应的 DFA 为

graph LR

style Start fill:none,stroke-width:0px

Start --> A(("$\{q_0\}$"))
A --> |$1$| A
A --> |$0$| B(("$\{q_0, q_1\}$"))
B --> |$0$| B
B --> |$1$| C((("$\{q_0, q_2\}$")))
C --> |$0$| B
C --> |$1$| A

转移表如下：

子集构造的最劣情形

考虑 $L(N)$ 是所有使得倒数第 $n$ 位是 $1$ 的 01 串集合。

graph LR

style Start fill:none,stroke-width:0px
style ... fill:none,stroke-width:0px

Start --> A(($q_0$))
A --> |$0, 1$| A
A --> |$1$| B(($q_1$))
B --> |$0, 1$| C(($q_2$))
C --> |$0, 1$| ...
... --> |$0, 1$| D(("$q_{n-1}$"))
D --> |$0, 1$| E((($q_n$)))

这个 NFA 没有少于 $2^n$ 个状态的等价 DFA。这很好理解，因为你最少要存下来每个 01 串的最后 $n - 1$ 位，所以会导致 DFA 的状态数指数型增长。

$\varepsilon$ 转移

$\varepsilon$ 转移可以理解成边权为空串 $\varepsilon$ 的边。

$\varepsilon$ - NFA 的形式化定义

只有转移函数 $\delta$ 与 NFA 不同。在 $\varepsilon$ - NFA 中，$\delta$ 的定义域被拓展为 $Q \times \left(\Sigma \cup \{\varepsilon\}\right)$，它需要包含所有通过 $\varepsilon$ 边转移的信息。

$\varepsilon$ 闭包

这就有点类似于在有向图中缩点了。$\varepsilon$ 闭包就是能被缩成一个点的块儿，消除 $\varepsilon$ 转移就是缩点的过程。

递归地定义 $q$ 的 $\varepsilon$ 闭包如下：

基础：$q \in \text{ECLOSE}(q)$

归纳：若 $p \in \text{ECLOSE}(q)$，且存在 $p$ 到 $r$ 的 $\varepsilon$ 转移，则 $r \in \text{ECLOSE}(q)$。

• 扩展转移函数 $\hat\delta(q, w)$ 形式化的定义如下：

  基础：$\hat\delta(q, \varepsilon) = \text{ECLOSE}(q)$。

  归纳：$\hat\delta(q, w) = \bigcup\limits_{p \in \hat\delta(q, x)}\text{ECLOSE}(\delta(p, a))$，其中 $w = xa$。

用通俗的话说，通过 $\varepsilon$ 的边将状态 $q$ 和它周围的状态联系起来，它们本质上是“同一个状态”，“同一个状态”对应的就是 $\text{ECLOSE}(q)$。

消除 $\varepsilon$ 转移

给定一个 $\varepsilon$ - NFA $E = (Q_E, \Sigma, \delta_E, q_0, F_E)$，求满足 $L(E) = L(D)$ 的 DFA $D = (Q_D, \Sigma, \delta_D, q_D, F_D)$。

• $Q_D = \{S \subseteq Q_E | S = \text{ECLOSE}(S)\}$
• $q_D = \text{ECLOSE}(q_0)$
• $F_D = \{S \subseteq Q_D | S \cap F_E \neq \varnothing\}$
• $\delta_D$ 满足 $$\delta_D(S, a) = \bigcup_{p \in S}\text{ECLOSE}(\delta(p, a))$$

对于 $E$ 和其对应的 $D$，也有

定理：$L$ 被 $\varepsilon$ - NFA $E$ 接受，当且仅当 $L$ 被 DFA $D$ 接受。

定理的证明与 NFA 和 DFA 的等价性处的证明类似。

练习题

习题 1

注意，要按照 $bac$ 和 $acb$ 重叠部分的长度分成三类。

习题 2 给出接受下列在字母表 $\{0, 1\}$ 上的语言的 DFA：所有 倒过来 解释成二进制整数时是 $5$ 的倍数的串的集合。例如 $010011, 1001100$ 和 $0101$。

先画出接受正方向串的 DFA $D$。这是容易的，按照除以 $5$ 得到的余数分类设计 $5$ 个状态即可。接着，接受倒过来串的 DFA 就是将 $D$ 中所有边全部反向得到的 DFA。

习题 3 给出接受下列在字母表 $\{0, 1\}$ 上的语言的 DFA：所有倒数第 $10$ 个符号是 $1$ 的串的集合。

设计 $2^{10}$ 个状态，表示已输入的串除以 $2^{10}$ 得到的余数，余数 $ \in [2^{9}, 2^{10} - 1]$ 为接受状态。

第三章 正则表达式与正则语言

正则表达式的运算符

并与连接

• 并 $$L \cup M = \{w | w \in L \lor w \in M\}$$

• 连接 $$LM = \{w = uv | u \in L \land v \in M\}$$

闭包

语言 $L$ 的闭包记作 $L^*$。形式化的定义是：

$$L^* = \bigcup_{i \ge 0}L^i$$

其中 $L^0 = \{\varepsilon\}, L^1 = L$，$L^i(i \ge 2)$ 表示 $i$ 个 $L$ 的连接。

对于绝大多数语言 $L$ 而言，$L^*$ 通常是无穷的。仅有两个 特殊的语言，它们的闭包是有限的。

• $\varnothing^*$

  注意到对于 $i \ge 1$，$\varnothing^i$ 是空集，而 $\varnothing^0 = \{\varepsilon\}$。故 $\varnothing^* = \{\varepsilon\}$。

• $\{\varepsilon\}^*$

  注意到 $\{\varepsilon\}$ 无论连接多少次都不会改变它是 $\{\varepsilon\}$ 的事实，所以 $\{\varepsilon\}^* = \{\varepsilon\}$。

正则表达式的定义

正则表达式仍然采用递归的定义方法：

基础：

1. $\varepsilon$ 和 $\varnothing$ 是正则表达式，分别表示语言 $\{\varepsilon\}$ 和 $\varnothing$。也就是说，$L(\varepsilon) = \{\varepsilon\}, L(\varnothing) = \varnothing$。
2. 若 $a$ 是任意 符号，则 $\textbf{a}$ 是正则表达式。这个表达式表示语言 $\{a\}$。也就是说，$L(\textbf{a}) = \{a\}$。

归纳：

1. 如果 $E$ 和 $F$ 都是正则表达式，则 $E + F$ 是正则表达式，表示 $L(E)$ 和 $L(F)$ 的并。也就是说，$L(E + F) = L(E) \cup L(F)$。
2. 如果 $E$ 和 $F$ 都是正则表达式，则 $EF$ 是正则表达式，表示 $L(E)$ 和 $L(F)$ 的连接。也就是说，$L(EF) = L(E)L(F)$。
3. 如果 $E$ 是正则表达式，则 $E^*$ 是正则表达式，表示 $E$ 的闭包。也就是说，$L(E^*) = (L(E))^*$。
4. 如果 $E$ 是正则表达式，则 $(E)$ 是正则表达式，表示和 $E$ 相同的语言。也就是说 $(L(E)) = L(E)$。

自动机与正则表达式间的关系

DFA、NFA、$\varepsilon$ - NFA 和正则表达式之间是等价的，它们都能表示相同的正则语言。

graph LR
A(NFA) --> |1| B(DFA)
B --> |2| C($\varepsilon$ - NFA)
C --> |3| B
B --> |4| D(RE)
D --> |5| C

其中 1、2、3 都已经被证明了。现在只需要证明 4 和 5。

由 DFA 构建正则表达式

我们想要解决的问题是：给定一个 DFA $A$，记 $L = L(A)$，求一个正则表达式 $R$，使得 $L = L(R)$。

重新编号 $A$ 的状态为 $\{1, 2, \cdots, n\}$，使得 $1$ 为初始状态。设 $R_{ij}^{(k)}$ 表示满足以下条件的串 $w$ 所组成的集合：$w$ 是 $A$ 中从状态 $i$ 到状态 $j$ 的路径的标记，而且这条路径没有编号大于 $k$ 的 中间顶点。因此 $i$ 和 $j$ 没有必要不大于 $k$。

最终的 $R$，是所有 $R_{1j}^{(n)}$ 的并，使得状态 $j$ 为一个接受状态。

仍然考虑使用递归的思路来推导 $R_{ij}^{(k)}$。

基础：当 $k = 0$ 时，这条路径中不能包含除了 $i, j$ 以外的其他状态。也就是说，这条路径上最多只会包含两个状态。

• 如果 $i = j$，则 $R_{ii}^{(0)} = \varepsilon + \textbf{a}_1 + \textbf{a}_2 + \cdots + \textbf{a}_r$，其中状态 $i$ 有自环 $\textbf{a}_1, \textbf{a}_2, \cdots, \textbf{a}_r$ 的弧。
• 如果 $i \neq j$，则 $R_{ij}^{(0)} = \textbf{a}_1 + \cdots + \textbf{a}_r$，其中状态 $i$ 到状态 $j$ 有 $\textbf{a}_1, \textbf{a}_2, \cdots, \textbf{a}_r$ 的弧。

归纳：假设有 $R_{ij}^{(k)}$，那么这条路径有两种情况：

1. 这条路径根本不经过状态 $k$。 这种情况下 $R_{ij}^{(k)} \gets R_{ij}^{(k-1)}$。

2. 这条路径经过状态 $k$ 至少一次。 于是我们可以把整个路径分成几段：

graph LR


style ... fill:none,stroke-width:0px


A((i)) --> |"属于 $R_{ik}^{(k-1)}$"| B((k))

subgraph "属于 $R_{kk}^{(k-1)}$ 的零个或多个串"

B((k)) --> C((k))

C((k)) --> ...

... --> E((k))

end

E((k)) -->|"属于 $R_{kj}^{(k-1)}$"| F((j))

那么这种路径可以表示成正则表达式 $R_{ik}^{(k - 1)}(R_{kk}^{(k - 1)})^*R_{kj}^{(k - 1)}$。

结合起来就有 $R_{ij}^{(k)} = R_{ij}^{(k - 1)} + R_{ik}^{(k - 1)}(R_{kk}^{(k - 1)})^*R_{kj}^{(k - 1)}$。这是一个递推式，所以我们可以从基础已知递推到所有的 $R_{1j}^{(n)}$。

比如考虑下图表示的 DFA：

graph LR

style Start fill:none,stroke-width:0px

Start --> A(($1$))
A --> |$1$| A
A --> |$0$| B((($2$)))
B --> |$0, 1$| B

由 基础 部分可得：

然后通过 归纳 部分递推得出 $R_{ij}^{(1)}$：

$$R_{ij}^{(1)} = R_{ij}^{(0)} + R_{i1}^{(0)}(R_{11}^{(0)})^*R_{1j}^{(0)}$$

因此可以得到：

又有

$$R_{ij}^{(2)} = R_{ij}^{(1)} + R_{i2}^{(1)}(R_{22}^{(1)})^*R_{2j}^{(1)}$$

因此可以得到：

在此例中，$1$ 是初始状态，$2$ 是唯一一个接收状态，则整体的正则表达式为 $R_{12}^{(2)} = \mathbf{1}^*\mathbf{0}(\mathbf{0} + \mathbf{1})^*$。

它表示的是“至少含有一个 0 的 01 串”组成的集合。

消除状态法

上述方法的复杂度太高，我们可以使用 消除状态 的方式来化简自动机。考虑下图中即将被消除的状态 $s$：

graph LR

A(($q_1$)) --> |"$R_{11}$"| B(($p_1$))
A --> |"$R_{1m}$"| E
A --> |$Q_1$| C(($s$))
C --> |$P_1$| B
C --> |$S$| C
C --> |$P_m$| E
D --> |$Q_k$| C
D --> |"$R_{k1}$"| B
D(($q_k$)) --> |"$R_{km}$"| E(($p_m$))

消除状态 $s$ 时需要清除掉所有与状态 $s$ 相关的转移边。消除状态 $s$ 后如下：

graph LR

A(($q_1$)) --> |"$R_{11} + Q_1S^*P_1$"| B(($p_1$))
A --> |"$R_{1m} + Q_1S^*P_m$"| E
D --> |"$R_{k1} + Q_kS^*P_1$"| B
D(($q_k$)) --> |"$R_{km} + Q_kS^*P_m$"| E(($p_m$))

从有穷自动构造正则表达式的策略如下：

1. 对于每个接受状态 $q$，应用上面的消除过程，消除除了 $q$ 和初始状态 $q_0$ 之外的所有其余状态，产生一个等价的自动机，转移边上带有正则表达式标记。

2. 如果 $q \neq q_0$，则剩下一个两状态自动机。可以用多种方法来描述所接受的串的正则表达式。一种方式是 $(R + SU^*T)^*SU^*$。

graph LR

style Start fill:none,stroke-width:0px


Start --> A((" "))

A --> |$R$| A

A --> |$S$| B(((" ")))

B --> |$T$| A

B --> |$U$| B

3. 如果初始状态也是接受状态，则必须去掉除了初始状态意外的所有其余状态。这样做了之后，只剩下一个单状态自动机，表示所接受的串的正则表达式是 $R^*$。

graph LR

style Start fill:none,stroke-width:0px


Start --> A(((" ")))

A --> |$R$| A

4. 所求的正则表达式是对每个接受状态进行步骤 2 和步骤 3 所得出的所有表达式之和（并）。

由正则表达式构造 $\varepsilon$ - NFA

构造出来的自动机都是 具有单个接受状态 的 $\varepsilon$ - NFA。

基础：先构造 $\{\varepsilon\}, \varnothing, \mathbf{a}$ 对应的三个自动机：

graph LR

style Start fill:none,stroke-width:0px

Start((" ")) --> A((" "))

subgraph "$\{\varepsilon\}$"
A --> | $\varepsilon$ | B(((" ")))
end

graph LR
style Start fill:none,stroke-width:0px

Start((" ")) --> A((" "))

subgraph $\varnothing$
A
B(((" ")))
end

graph LR
style Start fill:none,stroke-width:0px

Start((" ")) --> A((" "))

subgraph "$\mathbf{a}$"
A --> | $a$ | B(((" ")))
end

归纳：接着，我们构造 $R + S, RS, R^*$：

graph LR

style Start fill:none,stroke-width:0px

Start((" ")) --> A((" "))

A --> | $\varepsilon$ | B((" "))
A --> | $\varepsilon$ | D((" "))

subgraph $R$
B -.- C((" "))
end

subgraph $S$
D -.- E((" "))
end

C --> | $\varepsilon$ | F(((" ")))
E --> | $\varepsilon$ | F

graph LR
style Start fill:none,stroke-width:0px

Start((" ")) --> A((" "))

subgraph $R$
A -.- B((" "))
end

B --> | $\varepsilon$ | C((" "))

subgraph $S$
C -.- D(((" ")))
end

graph LR
style Start fill:none,stroke-width:0px

Start((" ")) --> A((" "))

A --> | $\varepsilon$ | B((" "))

subgraph $R$
C --> | $\varepsilon$ | B
B -.- C((" "))
end

C --> | $\varepsilon$ | D(((" ")))
A --> | $\varepsilon$ | D

通过自动机结构上的归纳法，我们可以得到与正则表达式表示相同语言的 $\varepsilon$ - NFA。

消除 $\varepsilon$ 转移时的注意事项

在上述构造中，有些地方可以化简：

1. 对于并运算符，不是构造新的初始状态和接收状态，而是把两个初始状态合并成一个具备两个初始状态的所有转移的状态。同样，合并两个接受状态，让所有的转移相应的地进入合并状态。

graph LR


style Start fill:none,stroke-width:0px


Start((" ")) --> A((" "))


subgraph " "

A -.- | $R$ | B(((" ")))

A -.- | $S$ | B

end

2. 对于连接运算符，把第一个自动机的接受状态与第二个自动机的初始状态合并。

graph LR

style Start fill:none,stroke-width:0px


Start((" ")) --> A((" "))


subgraph " "

A -.- | $R$ | B((" "))

B -.- | $S$ | C(((" ")))

end

3. 对于闭包运算符，只是增加从接受状态到初始状态的以及反方向的 $\varepsilon$ 转移。

graph LR

style Start fill:none,stroke-width:0px


Start((" ")) --> A((" "))


subgraph " "

B(((" "))) --> | $\varepsilon$ | A

A --> | $\varepsilon$ | B

A -.- | $R$ | B

end

每一个这种化简 本身 仍然产生正确的构造，但它们 组合在一起 有时会产生错误的构造（例如 $R + S^*$）。

正则表达式代数定律

定理：设 $E$ 是带变量 $L_1, L_2, \cdots, L_m$ 的正则表达式。对于 $i = 1, 2, \cdots, m$，通过把 $L_i$ 的每次出现都换成符号 $a_i$ 形成具体的正则表达式 $C$。则 $\forall w = w_1w_2\cdots w_k \in L(E)$，其中每个 $w_i$ 都属于任意的语言之一（如 $L_{j_i}$），都有 $w$ 对应的正则表达式 $a_{j_1}a_{j_2}\cdots a_{j_k}$ 属于语言 $L(C)$。

这个定理揭示了语言和正则表达式的内蕴的等价性。

附赠一个可能会有用的公式 $(R^*S^*)^* = (R + S)^*$

练习题

习题 1 求正则表达式 $E$，满足 $L(E) = \{w|w\text{ 的开头字符和结尾字符相同}\}$。

$0(0+1)^*0+1(0+1)^*1+0+1$。一定不要忘了 $|w|=1$ 的两种情况。

习题 2 求正则表达式 $E$，满足 $L(E)= \{w|w\text{ 的前 5 位至少包含 1 个 1} \land |w|\ge 1\}$。

巧妙使用空串 $\varepsilon$：$(0+1+\varepsilon)^41(0+1)^*$。

第四章 正则语言的性质

泵引理

定理：设 $L$ 是正则语言，则存在与 $L$ 相关的正整数 $n$ 满足：$\forall w \in L$ 满足 $\left|w\right| \ge n$，均 $\exists x, y, z$ 满足 $w = xyz$ 且：

1. $y \neq \varepsilon$
2. $\left|xy\right| \le n$
3. $\forall k \ge 0, xy^kz \in L$

证明：假设 $L$ 是正则语言，则存在 DFA $A$ 使得 $L = L(A)$。设 $A$ 有 $n$ 个状态，考虑 $w = a_1a_2\cdots a_m(m \ge n)$，其中 $a_i$ 为输入符号。

设 $p_i = \hat\delta(q_0, a_1a_2\cdots a_i)$，定义 $p_0 = q_0$ 为 $A$ 的初始状态。则 $p_0, p_1, \cdots, p_n$ 不可能两两不同，因此存在 $0 \le i < j \le n$ 使得 $p_i = p_j$。

所以可以画出如下的转移图：

graph LR

style Start fill:none,stroke-width:0px

Start --> A(($p_0$))
A -.-> |$x = a_1a_2\cdots a_i$| B(($p_i$))
B -.-> |"$y = a_{i+1} \cdots a_j$"| B
B -.-> |"$z = a_{j + 1}\cdots a_m$"| C(((" ")))

由 $i < j$ 得 $y \neq \varepsilon$，由 $j \le n$ 得到 $\left|xy\right| \le n$。$k \ge 0$ 就是可以绕着 $p_i$ 得自环多走几圈。

正则语言的封闭性

交运算的乘积构造法

已知正则语言 $L, M$，设 $A_L = \{Q_L, \Sigma, \delta_L, q_L, F_L\}$，$A_M = \{Q_M, \Sigma, \delta_M, q_M, F_M\}$，满足 $L = L(A_L), M = L(A_M)$。构造他们的乘积（笛卡尔积）：

$$A = (Q_L \times Q_M, \Sigma, \delta, q_L \times q_M, F_L \times F_M)$$

其中 $\delta$ 满足 $\delta((p, q), a) = (\delta_L(p, a), \delta_M(q, a))$，返回一个二元组。$A$ 接受 $w$ 当且仅当 $\hat\delta((q_L, q_M), w)$ 是一对接受状态。这等价于 $\hat\delta(q_L, w)$ 和 $\hat\delta(q_M, w)$ 均为接受状态。所以说 $A$ 只接受 $L\cap M$。

逆同态

定义 $L$ 对于 $h$ 的逆同态 $h^{-1}$ 如下：

$$h^{-1}(L) = \{w \in \Sigma^* | h(w) \in L\}$$

需要注意的是，$h(h^{-1}(L)) \subset L$，并不一定等于 $L$！

定理：已知 $h: \Sigma \to \Tau$，其中 $L$ 是 $\Tau$ 上的正则语言，求证 $h^{-1}(L)$ 是 $\Sigma$ 上的正则语言。

证明：设 $L$ 有一个 DFA $A = (Q, \Tau, \delta, q_0, F)$，现在的目标是用 $A$ 和 $h$ 构造 $h^{-1}(L)$ 的 DFA $B = (Q, \Sigma, \gamma, q_0, F)$。

定义 $\gamma(q, a) = \hat\delta(q, h(a))$，然后扩展 $\hat\gamma(q, w) = \hat(q, h(w))$。由于 $B$ 接受 $w$ 当且仅当 $A$ 接受 $h(w)$，故 $B$ 就是 $h^{-1}(L)$ 的 DFA。

注意 $\gamma(q, a)$ 是 $\hat\delta(q, h(a))$ 而非 $\delta(q, h(a))$，这是因为 $h(a)$ 有可能是一个串而非字符。

自动机的等价性和最小化

测试状态的等价性

我们称 DFA 中的两个状态 $p, q$ 是 等价的，如果 $\hat\delta(p, w)$ 是可接受当且仅当 $\hat\delta(q, w)$ 是可接受的。

注意到这个定义并不要求 $\hat\delta(p, w) = \hat\delta(q, w)$，它仅仅要求二者要么同时都是可接受的，要么同时都是不可接受的。

我们称 DFA 中的两个状态 $p, q$ 是 可区分的，如果它们不是等价的。

至此，我们可以构造 填表算法，来测试状态的等价性：

基础：如果 $p$ 和 $q$ 一个是可接受的，一个是不可接受的，那么 $p, q$ 是可区分的。

归纳：设 $p, q$ 满足 $\exists a$ 使得 $r = \delta(p, a)$ 与 $s = \delta(q, a)$ 是已知可区分的。假设 $w$ 可以区分 $r$ 和 $s$，那么 $aw$ 一定可以区分 $p, q$。按照归纳的步骤一步一步递推，则可得知所有状态两两间是否等价。

接下来，我们需要证明填表算法的正确性。

定理：如果通过填表算法不能区分两个状态，则这两个状态等价。

证明：使用反证法证明。我们称状态对 $\{p, q\}$ 为 坏对，如果 $\exists w \in L$，满足 $\hat\delta(p, w)$ 和 $\hat\delta(q, w)$ 本应可区分，但填表算法没有发现它们可区分。

设 $w = a_1a_2\cdots a_n$ 是所有可以区分坏对（无论区分的是哪一对坏对）的串中最短的那一个，且它区分的是 $\{p, q\}$。则 $\hat\delta(p, w)$ 和 $\hat\delta(q, w)$ 必恰有一个可接受。

注意到一个事实，$w \neq \varepsilon$，这是因为填表算法的基础部分对应的就是 $w = \varepsilon$ 的情况，可接受状态和不可接受的状态一定是可以区分的。接下来，考虑 $r = \delta(p, a_1), s = \delta(q, a_1)$，则串 $w' = a_2a_3 \cdots a_n$ 可区分 $r$ 和 $s$。

如果 $\{r, s\}$ 是坏对，则 $w'$ 比 $w$ 更短且能区分坏对，则产生矛盾。如果 $\{r, s\}$ 不是坏对，则 $\{r, s\}$ 一定是可区分的。此时算法已经发现 $\{r, s\}$ 是可区分的，那么一定会进行下去并计算出 $\{p, q\}$ 也是可区分的，这也产生矛盾。

所以填表算法是正确的。

测试正则语言的等价性

至此，我们已经能够测试同一个 DFA 中的两个状态是否等价。对于两个正则语言 $L$ 和 $M$ 而言，构造 DFA $A, B$ 使得 $L = L(A), M = L(B)$。

设 $A$ 的初始状态为 $p_0$，$B$ 的初始状态为 $q_0$。构造 DFA $A' = A \cup B$，只需要判断 $p_0$ 和 $q_0$ 是否等价即可。

DFA 的最小化

用以下流程可以最小化一个 DFA：

1. 排除所有不能从初始状态到达的状态
2. 将所有等价的状态划分到同一个连通块

需要注意一点的是，如果 $p, q$ 等价，$r, s$ 等价，且

graph LR
A(($p$)) --> |$1$| C(($r$))
B(($q$)) --> |$1$| C

即使此时无论是 $p$ 还是 $q$ 都不会通过 $1$ 转移到 $s$，我们仍然需要用上述算法划分等价类：

graph LR
A(("$\{p, q\}$")) --> |$1$| B(("$\{r, s\}$"))

练习题

习题 1 语言 $L$ 由所有满足如下条件的 $0$ 和 $1$ 组成的串构成：$0$ 的数量是 $1$ 的两倍。试用泵引理证明 $L$ 不是正则语言。

考虑 $w = xyz = 0^{2n}1^n$，则 $y$ 全部由 $0$ 构成，则 $xz \neq L$。这题的重点在于，虽然 $0^{2n}1^n$ 并非 $L$ 的全部，但只要找到一个反例即可。

习题 2 证明 $L = \{0^{n^2} | n \in \mathbb{N}\}$ 不是正则语言。

考虑 $w = xyz = 0^{n^2}$，则 $1 \le |y| \le n$，构造 $xy^2z$，它的长度 $|xy^2z| \in [n^2 + 1, n^2 + n]$，但这个区域内不应有完全平方数。$n^2$ 后的第一个完全平方数为 $(n+1)^2 = n^2+2n+1 > n^2+n$。

习题 3 证明 $L = \{0^n | n \text{ 是质数}\}$ 不是正则语言。

考虑 $w = xyz = 0^p$，其中 $p \ge n + 2$ 且为质数。不妨设 $|y| = m \ge 1$。考虑 $w' = xy^{p-m}z$，则 $|xy^{p-m}z| = (m+1)(p-m)$。而 $m+1 \neq 1, p-m \ge n+2-m \ge 2$。因此 $|w'|$ 不为质数。

习题 4 证明 $L = \{0^{2^n}|n \in \mathbb{N}\}$ 不是正则语言。

考虑 $w = xyz = 0^{2^n}$。与习题 2 的做法类似，我们可以得到 $|y| \in [1, n]$。我们只需要证明 $|xz| = 2^n - |y|$ 一定不是 $2$ 的幂即可。考虑 $|xz|$ 的取值范围 $[2^n-n, 2^n-1]$，则限制 $2^{n-1} < 2^n-n$ 即可，即 $n \ge 3$。所以在泵引理中取 $w = xyz = 0^{2^n}(n \ge 3)$ 即可导出 $xz \notin L$。

第五章 上下文无关文法及上下文无关语言

上下文无关文法

上下文无关文法的定义

一个上下文无关文法（CFG）由四个重要部分组成：

1. 一个有穷字母表 $T$，由 $T$ 中的字母构成了这个文法所定义的语言中的串，这个字母表称为 终结符（Terminal）。
2. 一个 非终结符 （Variable）的有穷集合 $V$。
3. 有一个非终结符 $S$ 称为 初始符号（Start Symbol），它代表语言开始被定义的地方。
4. 一个 产生式 （Production）的有穷集合 $P$，它用来表示语言的递归定义。每个产生式被定义为 <head> -> <body>，具体的构造过程是，保持终结符不变，把任何所有的 <head> 替换成 <body>。

一个上下文无关文法可以表示为 $G = (V, T, P, S)$。

以下是可以表示语言 $(\textbf{a} +\textbf{b})(\textbf{a} + \textbf{b} + \textbf{0} + \textbf{1})^*$ 的一个上下文无关文法。 $$\begin{aligned} E & \to I \\ E & \to E + E \\ E & \to E * E \\ E & \to (E) \\ I & \to a \\ I & \to b \\ I & \to Ia \\ I & \to Ib \\ I & \to I0 \\ I & \to I1 \end{aligned}$$ 产生式可以使用简捷表示法，比如上面的产生式可以化简为： $$\begin{aligned} E & \to I | E + E | E * E | (E) \\ I & \to a | b | Ia | Ib | I0 | I1 \end{aligned}$$

推导与递归推理

推导 的过程通过符号 $\implies$ 表示。设 $G = (V, T, P, S)$ 为一个 CFG，$\alpha A \beta$ 是一个包含终结符和非终结符的串，其中 $A$ 是一个非终结符，而 $\alpha, \beta \in (V \cup T)^*$。设 $A \to \gamma$ 是一个产生式，则我们称 $\alpha A \beta \underset{G}{\implies} \alpha\gamma\beta$。通常省略掉 $G$，而仅仅记作 $\alpha A \beta \implies \alpha\gamma\beta$。 多步推导则使用 $\overset{*}{\implies}$ 来表示。

递归推理 的过程类似于推导的逆过程，是从具体的 产生式的体 递归到抽象的 产生式的头 的过程。

最左与最右推导

在每一步推导中，如果要求只讲最左边的非终结符替换成该非终结符的某个产生式的体，那么这种方式的推导称为 最左推导。类似地可以定义 最右推导。最左推导和最右推导分别用 $\underset{lm}{\implies}, \underset{lm}{\overset{*}{\implies}}$ 和 $\underset{rm}{\implies}, \underset{rm}{\overset{*}{\implies}}$ 表示。

个人认为，如果每次推导的时候按照随机的顺序来替换，那么整个推导的逻辑就会变得杂乱无章。最左推导和最右推导就限制了替换产生式的头的顺序：前者是从左往右，后者是从右往左。

文法的语言

对于 CFG $G = (V, T, P, S)$，它的语言 $L(G)$ 被定义为所有终结符串的集合： $$L(G) = \{w \in T^* | S \underset{G}{\overset{*}{\implies}}w\}$$ 如果我们要证明某个文法 $G$ 确实定义了某个已经非形式化定义好的语言 $L$，通常需要分两步：

1. 充分性：如果一个串 $w \in L$ 满足这个非形式化定义的性质，那么 $S \overset{*}{\implies}w$，来说明 $w \in L(G)$。通常，我们通过 对 $w$ 的长度 进行归纳证明。
2. 必要性：如果 $S \overset{*}{\implies}w$，那么 $w$ 应该满足这个非形式化定义的性质，来说明 $w \in L$。通常，我们需要 对推导的步数 进行归纳证明。

句型

由初始符号推导出来的串称为 句型（Sentence）。$G = (V, T, P, S)$ 的所有句型 $\alpha$ 组成的集合是 $$\{\alpha \in (V \cup T)^* | S \overset{*}{\implies}\alpha\}$$ 另外，如果 $S \underset{lm}{\overset{*}{\implies}} \alpha$ 则 $\alpha$ 是左句型，如果 $S \underset{rm}{\overset{*}{\implies}} \alpha$ 则 $\alpha$ 是右句型。句型可以包含非终结符。语言 $L(G)$ 是由所有属于 $T^*$ 的句型组成的。

语法分析树

语法分析树的构造

对于 CFG $G = (V, T, P, S)$，$G$ 的 语法分析树 是满足下列条件的树：