[形式语言] 03 Regular Expression and Regular Language

为了证明这个问题，只需要证明对于任意正则表达式，存在一个 $\varepsilon$-NFA 与之等价；且对于任意 DFA，存在一个正则表达式与之等价。

• 对于任意正则表达式，存在一个 $\varepsilon$-NFA 与之等价

  只要根据正则表达式的构建树，按照下面的规则进行转换即可。

• 对于任意 DFA 存在一个正则表达式与之等价

  首先对 DFA $M = (Q, \Sigma, \delta, q_0, F)$ 上的结点进行标号：$1, 2, \dots, n$。

  定义一条 $k$-路径为 DFA 上的一条路径，其中路径上的点（不包括起点和终点）的标号不超过 $k$。因此所有路径都是 $n$-路径。路径上的边构成了一个句子。

  记 $R^k_{ij}$ 为点 $i$ 到点 $j$ 的所有 $k$-路径组成的语言，下面开始构造 $R^k_{ij}$。

  • 当 $k=0$ 时

    • 如果 $i = j$，则 $R^0_{ii} = \varepsilon + a_1 + a_2 + \dots + a_n (\delta(i, a_l) = i)$
    • 如果 $i \ne j$，且不存在从 $i$ 到 $j$ 的路径，则 $R^0_{ij} = \emptyset$
    • 如果 $i \ne j$，且存在从 $i$ 到 $j$ 的路径，则 $R^0_{ij} = a_1 + a_2 + \dots + a_n (\delta(i, a_l) = j)$

  • 当 $k > 0$ 时，假设所有 $k-1$-路径都可以转换成正则表达式

    • 则从 $i$ 到 $j$ 的路径有两种选择：不经过 $k$ 或至少经过 $k$ 一次
    • 因此 $R^k_{ij} = R^{k-1}_{ij} + R^{k-1}_{ik} (R^k_{kk})^{*} R^{k-1}_{kj}$

    根据这个方法可以构造出 $R^n_{q_0 q_f} (q_f \in F)$，此时 $R^n_{q_0q_{f1}} + R^n_{q_0q_{f2}} + \dots + R^n_{q_0q_{fm}} (f_i \in F)$ 即是答案。

设 RL $L$，DFA $M = (Q, \Sigma, \delta, q_0, F)$ 满足 $L(M) = L, |Q| = N$。为方便起见，不妨设 $M$ 中不含不可达状态。

取 $z = a_1 a_2 \dots a_m \in L (m \ge N)$，记 $z$ 在 $M$ 上经过的状态为 $q_h = \delta(q_0, a_1 a_2 \dots a_h) (1 \le h \le m)$。

由于 $m \ge N$，因此存在 $q_i, q_j \in Q (1 < i < j < m = N)$ 使得 $q_i = q_j$。即

$$\delta(q_0, a_1 a_2 \dots a_i) = q_i$$ $$\delta(q_0, a_1 a_2 \dots a_j) = q_j = q_i$$

因此 $\forall k \ge 0, \delta(q_i, (a_{i+1} a_{i+2} \dots a_j)^k = q_j = q_i)$

因此，

$$\forall k \ge 0, \delta(q_0, a_1 a_2 \dots a_i (a_{i+1} a_{i+2} \dots a_j)^k a_{j + 1} \dots a_m) = a_m$$

取 $u = a_1 a_2 \dots a_i, v = a_{i+1} a_{i+2} \dots a_j, w = a_{j+1} a_{j+2} \dots a_m$

则 $\forall i \ge 0$ 有

• $|uv| \le N$
• $|v| \ge 1$

设 $L$ 是 RL，则 $L$ 满足 pumping lemma。

设 $n$ 是仅依赖于 $L$ 的正整数，取 $z = 0^{n + p} \in L$，其中 $n + p$ 是素数。由 pumping lemma 知存在 $z = uvw$ 满足条件。由于 $|v| \ge 1$，不妨设 $v = 0^k$，$u = 0^{n - k}$。且 $\forall i \ge 0, uv^iw = 0^{n - k + ik + p} = 0^{n + p + (i - 1)k}$。

当 $i = n + p + 1$ 时，$uv^iw = 0^{(n + p)(k + 1)}$ 非素数，矛盾，因此原命题不成立。

下面通过证明 $(1) \rightarrow (2) \rightarrow (3) \rightarrow(1)$ 来证明。

• $(1) \rightarrow (2)$

  设 $L \subseteq \Sigma^*$ 是 RL，则存在 DFA $M(Q, \Sigma, \delta, q_0, F)$ 使得 $L(M) = L$。令关系 $R = R_M$。

  • 由前面的定义知 $R_M$ 是 $\Sigma^*$ 上的右不变等价关系
  • 由 $|\Sigma^* / R_M| \le |Q|$，所以 $R_M$ 具有有穷指数
  • 如果 $x \in L$，那么 $\delta(q_0, x) = t \in F$。因此 $\forall x \in L, x \in \mathrm{set}(t) (t \in F)$，所以 $L = \cup_{t \in F}(\mathrm{set}(t))$ 即 $L$ 是 $R$ 的某些等价类的并

• $(2) \rightarrow (3)$，因此需要证明 $R$ 是 $R_L$ 的加细，即需要证明 $\forall x, y \in \Sigma^*. x R y \rightarrow x R_L y$

  由于 $R$ 是右不变的，所以 $\forall z \in \Sigma^*. xz R yz$。

  又由于 $L$ 是 $R$ 的部分等价类的并，因此 $xz \in L \Leftrightarrow yz \in L$。

  所以 $x R_L y$。

• $(3) \rightarrow (1)$ 设 $R_L$ 具有有穷指数，下证存在 DFA $M$ 使得 $L(M) = L$。

  令 $M = (\Sigma^* / R_L, \Sigma, \delta, [\varepsilon], \{[x] | x \in L\})$，其中 $[x]$ 表示 $x$ 所在的等价类。

  其中对于任意的 $([x], a) \in (\Sigma^* / R_L) \times \Sigma$，有

  $$\delta([x], a) = [xa]$$

  下面证明 $\delta$ 的相容性（是一个函数），即 $\forall [x], [y] \in (\Sigma*/R_L). [x] = [y] \rightarrow (\forall a \in \Sigma. \delta([x], a) = \delta([y], a))$。

  由于 $[x] = [y]$，则 $x R_L y$，又由于 $R_L$ 具有右不变形，所以 $\forall a \in \Sigma. [xa] = [ya]$，成立。因此 $M$ 是一个合法的 DFA。

  根据 $R_L$ 的定义，$\forall x \in L. \delta(q_0, x) \in \{[x] | x \in L\}$。

设 $L$ 是 RL，其最小 DFA $M = (Q, \Sigma, \delta, q_0, F)$ 满足 $L(M) = L$，显然 $M$ 中不含不可达状态。根据前面的证明，有

$$|\Sigma^* / R_M| \ge |\Sigma^* / R_L|$$

下证 $M$ 与 Myhill-Nerode 定理证明中的 $M’ = (\Sigma^* / R_L, \Sigma, \delta’, [\varepsilon], \{[x] | x \in L\})$ 同构，其中

$$\delta’([x], a) = [xa]$$

定义映射 $f : Q \rightarrow \Sigma^* / R_L$，那么 $\forall q \in Q. \exists x \in \Sigma^*. \delta(q_0, x) = q_x$。令

$$f(q_x) = f(\delta(q_0, x)) = f(\delta’([\epsilon], x)) = [x]$$

这样就建立起来从 $M$ 到 $M’$ 的映射。现在证明 $f$ 是同构映射。

• 首先证明这是合法的函数，即 $q_x = q_y \Rightarrow \delta’([\varepsilon], x) = \delta’([\varepsilon], y)$
  • $q_x = q_y \Leftrightarrow \delta(q_0, x) = \delta(q_0, y) \Leftrightarrow x R_M y \Rightarrow x R_L y \Leftrightarrow [{x}] = [y] \Leftrightarrow \delta’([\varepsilon], x) = \delta’([\varepsilon], y)$
• 证明单射，即 $q_x \ne q_y \Rightarrow \delta’([\varepsilon], x) \ne \delta’([\varepsilon], y)$
  • $q_x \ne q_y \Leftrightarrow \delta(q_0, x) \ne \delta(q_0, y)$，即 $x$ 和 $y$ 在 $\Sigma^*/R_M$ 的不同等价类中
  • 如果此时 $[{x}] = [y]$，那么 $|\Sigma^* / R_M| > |\Sigma^* / R_L|$，这与 $M$ 是最小 DFA 矛盾
  • 因此 $[{x}] \ne [y]$，即 $\delta’([\varepsilon], x) \ne \delta’([\varepsilon], y)$
• 证明满射，即 $\forall [{x}]. \exists q_x \in Q. f(q_x) = [{x}]$
  • $\forall x \in L. [{x}] = \delta’([\varepsilon], x) \Leftrightarrow \exists x \in L. \delta(q_0, x) = q_x$
• 证明同态映射。在自动机中，两个状态 $q \rightarrow p$ 表示为 $\delta(q, a) = p$，因此即需要证明 $\delta(f(q), a) = f(p)$
  • 设 $\delta(q_0, x) = q$
  • $f(p) = f(\delta(q, a)) = f(\delta(\delta(q_0, x), a)) = f(\delta(q_0, xa)) = [xa]$，成立

综上，最小 DFA 都与唯一的 DFA 同构。

可以转换成正则表达式，然后直接用正则表达式表达出来。

利用乘积自动机

• 交集：构建乘积自动机，其中终止状态 $F_3 = \{[x, y] | x \in F_1 \wedge y \in F_2\}$
• 差集：构建乘积自动机，其中终止状态 $F_3 = \{[x, y] | x \in F_1 \wedge y \notin F_2\}$
• 补集：正则语言 $L$ 的补集为 $\Sigma^* - L$，由于 $\Sigma^*$ 是正则语言，因此 $L$ 的补集也是正则语言

利用正则表达式证明。设 RL $L$ 的正则表达式为 $E$，下面构建它的逆 $E^R$：

• 如果 $E$ 是字符 $a \in \Sigma$ 或 $\varepsilon$ 或 $\emptyset$，那么 $E^R = E$
• 如果 $E = F + G$，那么 $E^R = F^R + G^R$
• 如果 $E = FG$，那么 $E^R = (FG)^R = G^R F^R$
• 如果 $E = F^*$，那么 $E^R = (F^R)^*$

根据上面的规则构建的 $E^R$ 依然是正则表达式，因此 $E^R$ 仍然是 RL。

令 $L_2 = \{0^n 1^n | n \ge 0\}$，由泵引理知 $L_2$ 不是正则语言。

令 $L_3 = \{0^*1^*\}$，显然 $L_3$ 也是正则语言

假如 $L_1$ 是正则语言，那么 $L_2 = L_1 \cap L_3$ 也是正则语言，矛盾。因此原命题成立。

使用归纳法，对 $L$ 对应的正则表达式 $r$ 进行归纳易证。

由于同态映射是正则代换的特例，因此这个显然成立。

设同态映射 $f : \Sigma^* \rightarrow \Delta^*$。DFA $M(Q, \Delta, \delta, q_0, F)$，$L(M) = L$。

则 DFA $M’(Q, \Sigma, \delta’, q_0, F)$，其中

$$\delta’(q, a) = \delta(q, f(a))$$

要证明 $L(M) = L(M’)$，即证明 $\delta’(q_0, x) \in F \Leftrightarrow \delta(q_0, f(x)) \in F$。

下面先证明 $\delta(q_0, f(x)) = \delta’(q_0, x)$，对 $|x|$ 进行归纳：

• $|x| = 0$，显然成立

• 设 $|x| = |y| = k$ 的时候成立，那么当 $|x| = |ya| = k + 1$ 时，

  $$\delta(q_0, x) = \delta’(q_0, ya) = \delta’(\delta’(q_0, y), a) = \delta(\delta(q_0, f(y)), f(a)) = \delta(q_0, f(y)f(a)) = \delta(q_0, f(x))$$

由归纳知原命题成立，因此 $\delta’(q_0, x) \in F \Leftrightarrow \delta(q_0, f(x)) \in F$，即原命题成立。

设 $L_1$ 对应的 DFA 为 $M(Q, \Sigma, \delta, q_0, F)$。定义 \(M_2(Q, Σ, δ, q_0, F’)，其中

$$F’ = \{q | \exists y \in L_2, \delta(q, y) \in F\}$$

显然 $L(M’) = L_1 / L_2$