Finite Automata⚓︎

对教材 \(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)=\{p\in K:(q,e)\vdash_{M}^{*}(p,e)\}\)\)

换句话说，\(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- 转移）所能到达的所有状态的集合。

剩下的任务是要证明 \(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\)。

    • • 对于“仅当”方向，假设 \((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)\)。

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

      • 为了证明另一个方向，假设 \((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)\)。

证毕。