Finite Automata and Regular Expressions⚓︎

对教材 \(P_{69-72}\) 的翻译，略有删改。

设 \(M=(K,\Sigma,\Delta,s,F)\) 是一个 NFA，我们将构造一个与其等价的 DFA \(M^{\prime}=(K^{\prime},\Sigma,\delta^{\prime},s^{\prime},F^{\prime})\) 。关键思想是将 NFA 看作在任何时刻，不只占据一个状态，而是占据一个状态集合：即，通过到目前为止读取的输入，所有可以从初始状态到达的状态的集合。

以下构造将上述想法形式化：

• \(M^{\prime}\) 的状态集合 \(K^{\prime}\) 将是 \(2^{K}\)，即 \(M\) 的状态集合 \(K\) 的幂集
• \(M^{\prime}\) 的终态集合 \(F^{\prime}\) 将由 \(K\) 的所有包含至少一个 \(M\) 的终态的子集组成
• \(M^{\prime}\) 的转移函数 \(\delta^{\prime}\) 的定义会稍微复杂一些，基本思想是：\(M^{\prime}\) 在读取输入符号 \(a \in \Sigma\) 上的移动，模仿 \(M\) 在输入符号 \(a\) 上的移动，可能随后跟随 \(M\) 的任意数量的 e- 移动。

为了形式化这个想法，我们需要一个特殊的定义：对于任何状态 \(q \in K\)，令 \(E(q)\) 是 \(M\) 的所有可从状态 \(q\) 到达且无需读取任何输入的状态集合。也就是说：

换句话说，\(E(q)\) 是集合 \(\{q\}\) 在关系 \(\{(p,r):\text{there is a transition }(p,e,r)\in\Delta\}\) 下的闭包。因此，\(E(q)\) 可以通过以下算法计算：

Initially set E(q) := {q};
while there is a transition (p, e, r) in Delta with p in E(q) and r not in E(q) do:
    E(q) := E(q) union {r}

这个算法是我们用于闭包计算的一般算法的特化 (specialization)。它保证在最多 \(|K|\) 次迭代后终止，因为 while 循环的每次执行都会向 \(E(q)\) 中添加一个新状态，而最多只有 \(|K|\) 个状态可以被添加。

现在准备形式化地定义与 \(M\) 等价的确定性自动机 \(M^{\prime}=(K^{\prime},\Sigma,\delta^{\prime},s^{\prime},F^{\prime})\)。具体来说：

对于每个 \(Q\subseteq K\) 和每个符号 \(a\in\Sigma\)，定义： \(\(\delta^{\prime}(Q,a)=\bigcup\{E(p):p\in K\mathrm{~and~}(q,a,p)\in\Delta\text{ for some }q\in Q\}\)\)

也就是说，\(\delta^{\prime}(Q,a)\) 被视为 \(M\) 可以通过读取输入 \(a\)（并且可能随后跟着若干 e- 转移）所能到达的所有状态的集合。

上述构造法所需时间为 \(\mathcal{O}(m \cdot 2^n)\)，其中 \(m = |\Sigma|, n = |K|\)。

剩下的任务是要证明 \(M^{\prime}\) 是确定性的并且等价于 \(M\)。

• 证明 \(M^{\prime}\) 是确定性：注意到 \(\delta^{\prime}\) 是单值的，并且根据其构造方式，它在所有 \(Q\in K^{\prime}\) 和 \(a\in\Sigma\) 上都是良好定义的。（\(\delta^{\prime}(Q,a)=\emptyset\) 对于某些 \(Q\in K^{\prime}\) 和 \(a\in\Sigma\) 并不意味着 \(\delta^{\prime}\) 不是良好定义的；\(\emptyset\) 是 \(K^{\prime}\) 的一个成员。）

• 证明 \(M\) 和 \(M^{\prime}\) 是等价的

  • 我们现在声称：对于任何字符串 \(w\in\Sigma^{*}\) 和任何状态 \(p,q\in K\)，

    \[(q,w)\vdash_M^*(p,e)\text{ if and only if }(E(q),w)\vdash_{M^{\prime}}^*(P,e)\]

    对一些包含 \(p\) 的集合 \(P\) 成立。

  • 由此定理将很容易得出：考虑任意字符串 \(w\in\Sigma^{*}\)。那么 \(w\in L(M)\) 当且仅当 \((s,w)\vdash_{M}^{*}(f,e)\) 对于某个 \(f\in F\) （根据定义），当且仅当 \((E(s),w)\vdash_{M^{\prime}}^{*}(Q,e)\) 对于某个包含 \(f\) 的 \(Q\)（根据上述声称）；换句话说，当且仅当 \((s^{\prime},w)\vdash_{M^{\prime}}^{*}(Q,e)\) 对于某个 \(Q\in F^{\prime}\)。最后一个条件是 \(w\in L(M^{\prime})\) 的定义。

  • 我们通过对 \(w\) 进行归纳来证明这个声称：

    • 基础步骤：对于 \(|w|=0\)（即 \(w=e\)），我们必须证明 \((q,e)\vdash_{M}^{*}(p,e)\) 当且仅当 \((E(q),e)\vdash_{M^{\prime}}^{*}(P,e)\) 对于某个包含 \(p\) 的集合 \(P\)。第一个陈述等价于说 \(p\in E(q)\)。由于 \(M^{\prime}\) 是确定性的，第二个陈述等价于说 \(P=E(q)\) 且 \(P\) 包含 \(p\)；即 \(p\in E(q)\)。这就完成了基础步骤的证明。
    • 归纳假设：假设该声称对于所有长度为 \(k\) 或更短的字符串 \(w\) 成立，其中 \(k\ge0\)。

    • 归纳步骤：我们证明该声称对于任何长度为 \(k+1\) 的字符串 \(w\) 成立。设 \(w=va\)，其中 \(a\in\Sigma\)，且 \(v\in\Sigma^{*}\)。

      • 对于“仅当”方向，假设 \((q, w)\vdash_{M}^{*}(p,e)\)。那么存在状态 \(r_{1}\) 和 \(r_{2}\) 使得

        \[(q,w)\vdash_{M}^{*}(r_{1},a)\vdash_{M}(r_{2},e)\vdash_{M}^{*}(p,e)\]

        也就是说，\(M\) 从状态 \(q\) 到达状态 \(p\)，经过若干次移动（读取了输入 \(v\)），随后一次移动（读取了输入 \(a\)），随后若干次移动（未读取任何输入。现在 \((q,va)\vdash_{M}^{*}(r_{1},a)\) 等同于 \((q,v)\vdash_{M}^{*}(r_{1},e)\)，并且因为 \(|v|=k\)，根据归纳假设，\((E(q),v)\vdash_{M^{\prime}}^{*}(R_{1},e)\) 对于某个包含 \(r_{1}\) 的集合 \(R_{1}\) 成立。由于 \((r_{1},a)\vdash_{M}(r_{2},e)\)，存在一个三元组 \((r_{1},a,r_{2})\in\Delta\)，因此根据 \(M^{\prime}\) 的构造，\(E(r_{2})\subseteq\delta^{\prime}(R_{1},a)\)。又因为 \((r_{2},e)\vdash_{M}^{*}(p,e)\)，可以得出 \(p\in E(r_{2})\)，所以 \(p\in\delta^{\prime}(R_{1},a)\)。因此，\((R_{1},a)\vdash_{M^{\prime}}(P,e)\) 对于某个包含 \(p\) 的 \(P\) 成立，从而 \((E(q),va)\vdash_{M^{\prime}}^{*}(R_{1},a)\vdash_{M^{\prime}}(P,e)\)。

      • 为了证明另一个方向，假设 \((E(q),va)\vdash_{M^{\prime}}^{*}(R_{1},a)\vdash_{M^{\prime}}(P,e)\)，对于某个包含 \(p\) 的 \(P\) 和某个 \(R_{1}\) 使得 \(\delta^{\prime}(R_{1},a)=P\)。现在根据 \(\delta^{\prime}\) 的定义，\(\delta^{\prime}(R_{1},a)\) 是所有集合 \(E(r_{2})\) 的并集，其中对于某个状态 \(r_{1}\in R_{1}\)，\((r_{1},a,r_{2})\) 是 \(M\) 的一个转移。由于 \(p\in P=\delta^{\prime}(R_{1},a)\)，存在某个特定的 \(r_{2}\) 使得 \(p\in E(r_{2})\)，并且对于某个 \(r_{1}\in R_{1}\)，\((r_{1},a,r_{2})\) 是 \(M\) 的一个转移。那么根据 \(E(r_{2})\) 的定义，\((r_{2},e)\vdash_{M}^{*}(p,e)\)。同时，根据归纳假设，\((q,v)\vdash_{M}^{*}(r_{1},e)\)，因此 \((q, va)\vdash_{M}^{*}(r_{1},a)\vdash_{M}(r_{2},e)\vdash_{M}^{*}(p,e)\)。

证毕。

令 \(M_1 = (K_1, \Sigma, \Delta_1, s_1, F_1), M_2 = (K_2, \Sigma, \Delta_2, s_2, F_2)\)。

并拼接克莱尼星号补交

令 \(M_1, M_2\) 为 NFA，我们将构造一个 NFA \(M\)，满足 \(L(M) = L(M_1) \cup L(M_2)\)。\(M\) 的构造非常简单直观，如下所示：

\(M\) 利用不确定性猜测输入在 \(L(M_1)\) 中还是在 \(L(M_2)\) 中。下面给出形式化的证明：

• 不失一般性地，假设 \(K_1, K_2\) 是不相交集
• 那么 \(M\) 接受语言 \(L(M_1) \cup L(M_2)\) 的定义如下：\(M = (K, \Sigma, \Delta, s, F)\)，其中：
  • \(s\) 是不属于 \(K_1\) 或 \(K_2\) 的新状态
  • \(K = K_1 \cup K_2 \cup \{s\}\)
  • \(F = F_1 \cup F_2\)
  • \(\Delta = \Delta_1 \cup \Delta_2 \cup \{(s, e, s_1), (s, e, s_2)\}\)
• 也就是说 \(M\) 一开始会任意选取 \(M_1\) 或 \(M_2\) 的初始状态，随后模仿 \(M_1\) 或 \(M_2\) 的行为
• 形式上，若 \(w \in Sigma^*\)，那么 \((s, w) \vdash_M^* (q, e)\ (q \in F)\) 当且仅当 \((s_1, w) \vdash_{M_1}^* (q, e)\ (q \in F_1)\) 或 \((s_2, w) \vdash_{M_2}^* (q, e)\ (q \in F_2)\) 成立
• 因此当且仅当 \(M_1\) 或 \(M_2\) 接受 \(w\) 时，\(M\) 接受 \(w\)，于是 \(L(M) = L(M_1) \cup L(M_2)\)

令 \(M_1, M_2\) 为 NFA，我们将构造一个 NFA \(M\)，满足 \(L(M) = L(M_1) \circ L(M_2)\)。\(M\) 的构造如下所示：

可以看到，\(M\) 先模拟一段时间的 \(M_1\)，之后从 \(M_1\) 的最终状态“跳转”到 \(M_2\) 的初始状态，开始模仿 \(M_2\) 了。

这里省略了形式化的证明。

令 \(M_1\) 为 NFA，我们将构造一个 NFA \(M\)，满足 \(L(M) = L(M_1)^*\)。\(M\) 的构造如下所示：

• \(M\) 由 \(M_1\) 的状态和 \(M_1\) 的所有转移构成，且任何 \(M_1\) 的最终状态都是 \(M\) 的最终状态
• 此外 \(M\) 有新的初始状态 \(s\)，\(s\) 也是一种最终状态，这使得 \(e\) 也能为 \(M\) 所接受
• \(s\) 处存在到 \(M_1\) 的 \(s_1\) 的 e 转移，因此 \(M\) 可模仿 \(M_1\) 的行为
• \(M_1\) 的每个状态都存在一个到 \(s_1\) 的 e 转移，这样一旦读取好 \(L(M_1)\) 的一个字符串后，就能接着继续从初始状态 \(s_1\) 开始了

令 \(M\) 为 DFA。补语言 \(\overline{L} = \Sigma^* - L(M)\) 会被 DFA \(\overline{M} = (K, \Sigma, \delta, s, K - F)\) 接受，即 \(\overline{M}\) 与 \(M\) 相同，除了互换最终状态和非初始状态。

\[ L_1\cap L_2=\Sigma^*-((\Sigma^*-L_1)\cup(\Sigma^*-L_2)) \]

交的封闭性就转换为遵守并的封闭性和补的封闭性，而这些前面都证明过了。

由于 \(L\) 是正则的，因此它能被 DFA \(M\) 所接受。设 \(n\) 为 \(M\) 的状态数，\(w\) 是长度不低于 \(n\) 的字符串。考虑 \(M\) 在 \(w\) 上运算的前 \(n\) 步： $$ (q_0,w_1w_2\ldots w_n)\vdash_M(q_1,w_2\ldots w_n)\vdash_M\ldots\vdash_M(q_n,e) $$

• 其中 \(q_0\) 是初始状态，\(w_1, \dots w_n\) 是 \(w\) 前 \(n\) 个符号
• 因为 \(M\) 只有 \(n\) 个状态，所以上述计算中存在 \(n+1\) 种配置 \((q_i, w_{i+1}, \dots w_n)\)
• 根据鸽巢原理，存在 \(i, j, 0 \le i < j \le n\) 满足 \(q_i = q_j\)
• 也就是说存在非空字符串 \(y = w_i w_{i+1} \dots w_j\)，使得 \(M\) 的状态从 \(q_i\) 重新回到 \(q_i\)
• 因此可以从 \(w\) 中移除 \(y\)，或者在 \(w_j\) 之后重复插入多个 \(y\)，而 \(M\) 仍然会接受这些字符串，即对于每个 \(i \ge 0\)，\(M\) 都会接受 \(xy^iz \in L\) 的情况，其中 \(x = w_1 \dots w_i, z= w_{j+1} \dots w_m\)