2DFA和DFA的等价性

本文转自我原来的洛谷博客

这是大一下学期某次计科导的思考题把这个问题拿来给大一学生思考真是很难想象开课老师的精神状态

首先吐槽一句资料真的难找。网上有关这方面的资料少之又少，顶多介绍了$\text{2DFA}$的定义和结论，但是没有给出$\text{2DFA}$和$\text{DFA}$的等价性证明的。为了填补国内对于这一问题的资料的空白，我决定写这么一篇文章把这个问题讲清楚。

根据目前资料来看，这个成果最早见于上古时期1959年的一篇论文$\text{《Finite Automata and Their Decision Problems》}$中，作者是$\text{M.Rabin}$和$\text{Dana Scott}$。两位因此获得了1976年的图灵奖。当然我刚开始去找的时候发现这篇论文没地方白嫖，购买要33刀太贵了。

现在的计算理论教材介绍这个内容的貌似很少了，主要原因可能是原始论文中的构造过于复杂。但是这里要感谢神通广大的计算理论老师给我提供了一份1979年的 “计算理论早期的一本标准参考书” Introduction to Automata Theory 的第一版（第二版，第三版太简单了） 的英文原版（中译本有，但是很难找到了） 的 djvu影印版本（pdf版没找到），作者是$\text{John.E.Hopcroft}$和$\text{Jeffrey.D.Ullman}$，算是本上古奇书。这篇文章的内容基本全部翻译自原书的2.6节。

感谢vfk给了一份原始论文虽然我不知道他是怎么找到的，也还没怎么看

$\text{1.前置}$

$\text{2DFA}$的定义网上都能找到，这里不多说，符号基本上也是全世界通用的。$\text{2DFA}$的五元组定义中与$\text{DFA}$唯一的不同是$\text{2DFA}$的$\delta$定义为$Q\times \Sigma \to Q\times\{L,R\}$。

在描述$\text{DFA}$的行为的时候，我们将$\delta$函数的定义域扩展至了$Q\times \Sigma^\ast$，用以描述$\text{DFA}$从某个状态出发接受一个字符串以后到达的状态。但是对于$\text{2DFA}$这种技巧不再奏效，因为是可以向左移动的。

我们定义$\text{2DFA}$的格局$\text{I}\in \Sigma^\ast Q \Sigma^\ast$，$\text{I}$可写作$wqx$，$w,x\in \Sigma^\ast, q\in Q$。代表含义如下：

1. $wx$是输入串

2. $ q $是当前状态

3. $\text{2DFA}$的读入端正在读取$x$的第一个字符

特别的，$x=\epsilon$表示$\text{2DFA}$的读入端已经移出了输入串的右边界。

我们定义二元关系 $\vdash_M$，$I_1 \vdash_M I_2$当且仅当通过读入端的一次移动可以格局$I_1$转移至格局$I_2$

我们由此可以对$\vdash_M$(以下简记作$\vdash$)给出形式化的定义：

1. $a_1a_2...a_{i-1}qa_i...a_n\vdash a_1a_2...a_{i-1}a_ipa_{i+1}...a_n,\text{whenever } \delta(q,a_i)=(p,R)$

2. $a_1a_2...a_{i-2}a_{i-1}qa_i...a_n \vdash a_1a_2...a_{i-2}pa_{i-1}a_i...a_n,\text{whenever } \delta(q,a_i)=(p,L)$

$i>1$防止移出左端，而$i=n+1$时没有可用的移动。

我们定义 $\vdash^\ast $为$\vdash$的传递闭包。利用上面的记号我们就可以写出 $\text{2DFA}$ $M$接受的语言$L(M)$的形式化定义: $L(M)=\{w|q_0w \vdash^\ast wp,p\in F\}$

$\text{2.crossing sequence}$

对于$\text{2DFA}$的行为的一个有用的描述是读取输入时读入端移动的路径，以及每一次读入端穿过两个字符的边界时的状态（也就相当于每一次移动的起始状态）。对于我们每一次穿过的边界，都对该边界记录下穿过该边界时的状态，那么对于每个边界我们都将得到一个状态序列，被称作$\text{crossing sequence}$（我也不知道中文是什么）。

需要注意的是，如果$\text{2DFA}$接受了输入串，那么产生的所有$\text{crossing sequence}$中都不会存在移动方向相同的重复状态。容易知道这样必定会在同一个边界处左右横跳产生死循环。

另一个重要的观察结果是，当一个边界第一次被穿过的时候，读入端一定在向右移动。而且后续再次穿过该边界的时候的移动方向一定是与前一次访问时的移动方向相反。因此在一个$\text{crossing sequence}$中，下标为奇数的元素一定代表着向右移动，而下标为偶数的元素一定代表着向左移动。如果输入串被接受，那么产生的所有$\text{crossing sequence}$一定长为奇数。由此，如果一个$\text{crossing sequence}$ $q_1,q_2,...,q_k$长度为奇数，我们称这个$\text{crossing sequence}$是有效的。

老师的提示：“每个这种序列本质上是从状态集$Q$到状态集$Q$的函数$f:Q\to Q$，输入是向右移动时的状态，输出是向左回来时的状态，这两个状态就是该序列中相邻的两项。构造的$\text{DFA}$本质上用这种$f$作为状态。”

原书中构造的是$\text{NFA}$，当然也是等价的，用的也是$\text{crossing sequence}$作为状态。为此，我们首先需要分析相邻的$\text{crossing sequence}$的性质。

$\text{3.左右匹配crossing sequence对}$

考虑输入字符串上的一个字符$a$，设在$a$的左边界和右边界处分别给出有效的$\text{crossing sequence}$ $q_1,q_2,...q_k$和$p_1,p_2,...,p_l$。我们可以用如下方法检测这两个$\text{crossing sequence}$是否是相容的（一致的），或者说，我们在计算过程中能否在$a$的左右边界上分别产生这两个$\text{crossing sequence}$。

如果读入端以状态$q_i$从$a$字符处向左移动，那么我们以$q_{i+1}$为起始状态，从$a$处开始，重新启动自动机，这样相当于我们从$\text{crossing sequence}$中的下一个状态开始继续运行来检测后续序列的相容性。类似的，如果读入端以状态$p_i$从$a$字符处向右移动，那么我们以$p_{i+1}$为起始状态，从$a$处开始，重新启动自动机，来检测后续序列的相容性。这样的想法给出了下面的两个定义。

定义：我们以如下$5$个条件递归地给出左匹配和右匹配$\text{crossing sequence}$对的概念。假设我们初始时以状态$q_1$向右移动到达$a$，若$q_1,q_2,...q_k$和$p_1,p_2,...,p_l$是相容的，称$q_1,q_2,...,q_k$于$a$处右匹配$p_1,p_2,...,p_l$。假定我们初始时以状态$p_1$向左移动到达$a$以状态$p_1$向左移动到达$a$，若$q_1,q_2,...q_k$和$p_1,p_2,...,p_l$是相容的，则称$q_1,q_2,...,q_k$于a处左匹配$p_1,p_2,...,p_l$。这里$q_1,q_2,...q_k$和$p_1,p_2,...,p_l$分别是我们在$a$的左右边界处取的$\text{crossing sequence}$ 。

注意，因为第一次进入$a$时肯定是向右移动，因此理论上说只有右匹配对我们是有意义的，但是为了递归地考虑右匹配我们需要对应地给出左匹配的概念。

接下来给出左右匹配的递归判定条件。

1. 空序列与空序列左右匹配。也就是说，如果我们根本无法到达$a$，那么$a$的左右两侧都是空序列。

2. 如果$q_3,...,q_k$右匹配$p_1,...,p_l$，并且$\delta(q_1,a)=(q_2,L)$，那么$q_1,...,q_k$右匹配$p_1,...,p_l$。亦即，第一次穿过左边界时以状态$q_1$进入状态$q_2$，并且读入端立刻以状态$q_2$左移进入状态$q_3$。如果我们从$q_3$出发得到了一对匹配的$\text{crossing sequence}$，那么说明我们从$q_1$出发得到的一对$\text{crossing sequence}$也是相容的。

3. 如果$q_2,...,q_k$左匹配$p_2,...,p_l$并且$\delta(q_1,a)=(p_1,R)$，那么$q_1,...,q_k$右匹配$p_1,...,p_l$。亦即，第一次穿过左边界时以状态$q_1$进入状态$p_1$，并且立即以状态$p_1$右移穿过右边界。

   这里需要注意的是，我们下一次回到$a$时，肯定是以$p_2$左移到达$a$的，以此为起点考虑接下来的计算过程，这可以看作是原计算过程的一个子过程。在子过程中，我们在左右边界记录下的序列分别是$q_2,...,q_k$和$p_2,...,p_l$（开头是$q_2$，是因为$q_1$是我们第一次到达$a$时记下的，不在接下来的计算过程中）。因为这个子过程是以$q_2$向左进入$a$开始的，因此如果$q_2,...,q_k$左匹配$p_2,...,p_l$我们就能得到$q_1,...,q_k$右匹配$p_1,...,p_l$。

4. 如果$q_1,...,q_k$左匹配$p_3,...,p_l$并且$\delta(p_1,a)=(p_2,R)$，那么$q_1,...,q_k$左匹配$p_1,...,p_l$。这个的解释和第$2$条类似。

5. 如果$q_2,...,q_k$右匹配$p_2,...,p_l$并且$\delta(p_1,a)=(q_1,L)$，那么$q_1,...,q_k$左匹配$p_1,...,p_l$。这个的解释和第$3$条类似。

$\text{4.等价性证明}$

定理：如果语言$\text{L}$被一个$\text{2DFA}$接受，那么$\text{L}$是正则语言

$\text{Proof:}$

我们设$ M=(Q,\Sigma,\delta,q_0,F)$是一个$\text{2DFA}$。下面构造一个 $\text{NFA }M'=(Q',\Sigma,\delta',q_0',F')$ 使得 $M'$接受$L(M)$，这里$(Q',\Sigma,\delta',q_0',F')$满足如下条件:

1. $Q'$由$M$产生的所有有效的$\text{crossing sequence}$组成。

   我们说过，$\text{crossing sequence}$长度是有限的，因此所有有效的$\text{crossing sequence}$集合的大小也是有限的。

2. $q_0'$是仅包含$q_0$的$\text{crossing sequence}$

3. $F'$是所有仅包含$F$中的状态的长度为$1$的$\text{crossing sequence}$组成的集合

   形式化的说，$F'=\{[q_f]|q_f\in F\}$

4. $\delta'(c,a)=\{d|d\text{是于a处右匹配c的有效crossing sequence}\}$

   这里的$d$既然是有效的，肯定长度为奇数。注意由于我们构造的是一个$\text{NFA}$，转移函数的像是状态的集合。

因为下面马上会用方括号来表示序列，所以这里$F'$的形式化定义我也用了方括号表示序列。

我们的想法是让$M'$把$M$的计算拼在一起。这是通过猜测接下来的$\text{crossing sequence}$来实现的。如果$M'$猜测$c$是在某个边界上产生的$\text{crossing sequence}$，并且$a$是下一个输入字符,所有于$a$处被$c$右匹配的$\text{crossing sequence}$都是可能的下一步，如果我们运气好跑出了输入串的右边界，那$M'$就接受了这个字符串。

我们下面来证明$L(M')=L(M)$。先证$L(M)\subset L(M')$。

$\forall w\in L(M)$，考虑$M$在$w$上的一次接受计算产生的所有$\text{crossing sequence}$。每个$\text{crossing sequence}$都右匹配下一个边界处的$\text{crossing sequence}$，所以我们顺着这些$\text{crossing sequence}$猜就能一路转移到接受状态。

反过来，我们再证明$L(M')\subset L(M)$。

$\forall w\in L(M')$，考虑$M'$计算$w=a_1a_2...a_n$时产生的$\text{crossing sequence}$序列$c_0,c_1,...,c_n$。那么根据$\delta'$的定义，对于每个$i\in [0,n-1]$，$c_i$右匹配$c_{i+1}$于$a_{i+1}$。我们可以通过决定读入端转向的时机来构造$M$在$w$上的合法的计算。具体而言，假设$M'$在读取$a_1a_2...a_i$，我们对$i$用归纳法，来证明如下结论。

若$M'$能进入状态$c_i=[q_1,...,q_k]$，则：

$(1)$ $M$以$q_0$启动计算$a_1a_2...a_i$时在$i$处会首先以$q_1$状态右移，并且

$(2)$ 对于$j=2,4,...$，若$M$在$i$处以状态$q_j$启动，$M$最终会以状态$q_{j+1}$向右移出第$i$位。这也说明$k$必须为奇数。

原书在此处用$[q_1,...,q_k]$表达$\text{crossing sequence}$。这里的符号和原书保持一致。

归纳基础$(i=0)$：

$c_0=[q_0]$时$(1)$自动满足，因为$M$在$0$处（相当于字符串还没读入）可以看成是“向右移动”读取了$a_1$。$(2)$也显然满足。

归纳证明：

假设结论对$i-1$成立。假定$M'$会在读取$a_1a_2...a_i$后从$c_{i-1}=[q_1,...,q_k]$进入状态$c_i=[p_1,...,p_l]$。

因为$k$和$l$都是奇数，并且$c_{i-1}$于$a_i$处右匹配$c_i$，必定存在一个奇数$j$使得在状态$q_j$读取$a_i$后$M$向右移动（如果这样的$j$全部是偶数，那么只可能是让读写头在$a_i$的左边界处反复横跳，那显然是不可能的）。让$j_1$是最小的这样的$j$（这样我们先去掉了没有作用的反复横跳的情况）。于是根据右匹配的定义，$\delta(q_{j_1},a_1)=(p_1,R)$。

这一结论无需使用前面给出的递归判定条件，但也不是很显然。由于$j_1$是奇数（注意，奇数的条件控制的是在读取$a_i$之前读入端右移穿过左边界的行为），从$q_{j_1}$读取$a_i$向右的转移一定是穿过$a_i$的左边界到达一个新状态，根据我们对$j$和$j_1$的约定，读写头这时一定会向右移动穿出$a_i$的右边界（注意，这是由$j$的约定控制的读入端读取$a_i$以后向右移动穿过右边界的行为，这和上面那一次右移的原因不一样），由$j_1$的最小性，以新状态向右移动一定是第一次穿出$a_i$的右边界，那么$c_i$的第一个元素$p_1$一定是这时产生的。于是我们有$\delta(q_{j_1},a_1)=(p_1,R)$。

这就证明了$(1)$。

由前面右匹配定义的第$3$条，我们有$[q_{j_1+1},...,q_k]$左匹配$[p_2,...,p_l]$。

如果对于所有偶数$j$都有$\delta(p_j,a_i)=(p_{j+1},R)$那么$(2)$显然成立。否则，我们取最小的偶数$j_2$使得$\delta(p_{j_2},a_i)=(q_{x},L)$。目前$q_{x}$不确定，但可以肯定的是，$q_{x}$是$a_i$左边界的$\text{crossing sequence}$中的的元素，因为我们在读取$a_i$之后立刻向左移动穿出了左边界。

这样，根据前面左匹配的定义的第$5$条，$q_{x}$一定是$q_{j_1+1}$并且$[q_{j_1+2},...,q_k]$右匹配$[p_{j_2+1},...,p_l]$。

这一结论又不是很显然。$j_2$为偶数控制了这一步的移动是穿过$a_i$右边界向左移动，到达了新状态$q_x$。$q_x$又向左移动穿出了左边界。根据前面对于$j_1$的定义，$q_{j_1}$的移动是在状态转移至$c_i$中的状态之前最后一次穿越左边界（在这之后，读入端马上向右移动穿出右边界了）。由于$j_2$的最小性，这一次移动一定是第一次从$c_i$中的状态转移到了$c_{i-1}$中的状态，并且穿出了左边界。因此，可以知道我们在$p_{j_2}$转移后，一定是转移到了$q_{j_1+1}$。那么$q_{x}$就是$q_{j_1+1}$。在此基础上直接使用左匹配的定义的第$5$条就可以得到$[q_{j_1+2},...,q_k]$右匹配$[p_{j_2+1},...,p_l]$。

因此我们肯定会从$p_{j_2+1}$穿出右边界移出$i$。$(2)$得证。虽然我们也有可能在穿出去之后再左移回来，但是我们只要重复这个过程，不断消去$c_i$和$c_{i-1}$中的元素，对于$M$来说它会在这样的$p_{j}$和$q_{j}$之间来回移动直到最终剩下所有偶数$j$都有$\delta(p_j,a_i)=(p_{j+1},R)$，这是肯定能达成的，最终否则如果读取了$a_i$都是向左移动那么就不会穿出$a_i$的右边界，$w$也就不会被接受了。这时$M$会继续转移到下一个$\text{crossing sequence}$中的状态。换言之我们不会停在第$i$位之前走不出去。

由于$c_n$非空，最后一定能走到$c_n=[p]$，这里$p\in F$。于是$M$接受$a_1a_2...a_n$，有$L(M)\subset L(M')$。

于是$L(M)=L(M')$。定理得证。

$\text{5.总结}$

总结个寂寞，累死了。