Finite Automata

令 $q_0,q_1$ 分别表示目前 $b$ 的数量为偶数、奇数。初态和唯一终态都是 $q_0$；读 $a$ 保持原状态，读 $b$ 在两状态间切换。

输入 aabba 的运行是

读完后在终态 $q_0$，所以接受。空串也被接受，因为其中有零个 $b$。 读完任意前缀 $u$ 后，所在状态为 $q_{\#_b(u)\bmod 2}$。

对前缀长度归纳即可证明：读 $a$ 不改变奇偶性，读 $b$ 恰好翻转奇偶性。

设 $q_0,q_1,q_2$ 分别表示：尚未出现 bbb，且当前末尾连续 $b$ 的数量为 $0,1,2$。$q_3$ 表示已经出现 bbb，此后无法补救。

尚未出错时，读 $a$ 会结束末尾连续的 $b$，因此返回 $q_0$；读 $b$ 则把末尾计数加一。第三个连续的 $b$ 使机器进入拒绝的陷阱状态 $q_3$，此后对 $a,b$ 都自环。

例如 bbabb 被接受，abbba 被拒绝。不能让 $q_3$ 读到 $a$ 后回到 $q_0$：后面出现 $a$ 不会消除前面已经出现过的 bbb。

与第一章的表达式对应：

自动机识别与正则表达式生成从两个方向描述了同一个语言。

若要识别“含有 bbb”，保持所有转移不变，把终态集改为 $\{q_3\}$ 即可。这正是完整 DFA 的补集构造。

可以由三个状态描述：初态 $q_0$ 也是唯一终态，转移为

读到块中的 $b$ 时，机器可以选择结束 ab，也可以继续读取一个 $a$ 来结束 aba。

对于 aba，路径 $q_0\to q_1\to q_2\to q_0$ 接受，而 $q_0\to q_1\to q_0\to q_1$ 不接受。存在第一条路径已经足够。

对于 abb，读完 ab 后的各分支都无法再读一个 $b$ 并接受，所以拒绝。

另一种 NFA 构造：

也可使用 $q_0\xrightarrow{a}q_1\xrightarrow{b}q_2$，再令 $q_2\xrightarrow{a}q_0$ 和 $q_2\xrightarrow{e}q_0$。

DFA 构造：

这五个状态分别可由 $e,a,ab,aba,b$ 到达，并且不能继续合并：

• 接受与非接受状态用空串区分；
• 接受状态中 $q_0,q_2$ 可用后缀 $a$ 区分，$q_0,q_3$ 及 $q_2,q_3$ 可用 $b$ 区分；
• 非接受状态 $q_1,q_4$ 也可用 $b$ 区分。
• 因此至少需要五个 DFA 状态。

唯一终态 $q_4$ 对 $a,b$ 自环，吸收匹配后的任意后缀。

举例说明：

bababab 的一个接受分支为

一直留在 $q_0$ 的分支则不接受。这不构成矛盾：NFA 的接受是“至少存在一个分支”。

对应表达式是 $(a\cup b)^*(bb\cup bab)(a\cup b)^*$。

NFA 只需 $n+1$ 个状态：初态 $s$ 通过 $e$ 边进入任意 $q_i$；$q_i$ 对所有 $a_j\ne a_i$ 自环，但没有读取 $a_i$ 的转移。所有状态均为终态。

n = 3 的 diagram：

机器先猜“缺少的是 $a_i$”，再检查整个串确实没有 $a_i$。至少有一个猜测成立便接受。

等价 DFA 可以用“已经出现过哪些符号”的集合为状态，需要 $2^n$ 个状态；

$\boxed{ \begin{array}{c|c} \text{DFA} & \text{每个状态对每个输入都必须有下一状态}\\ \text{NFA} & \text{可以没有下一状态，此时该路径直接失败} \end{array}}$

初态 $q_0$ 对 $a,b$ 自环；读到 $a$ 时，还可以转移到 $q_1$，猜测它就是倒数第六位。随后必须再读取恰好五个符号：

唯一终态 $q_6$ 没有出边。进入 $q_6$ 时若恰好读完输入，该分支接受；剩余输入太多或太少都会失败。

例如 abbbbb 接受，babbbb 拒绝，长度小于 $6$ 的串全部拒绝。推广到倒数第 $k$ 位为 $a$，同样只需 $k+1$ 个 NFA 状态。

设 DFA 读完 $w$ 后处于集合 $S_w$。证明不变式

对 $|w|$ 归纳。$w=e$ 时，右边恰好是 $E(s)$，即 DFA 初态。

假设结论对 $w$ 成立。读完 $wa$ 的 NFA 路径可以分成：读取 $w$，读取最后一个符号 $a$，再走零条或多条 $e$ 边。因此所有可能终点恰好组成 $\delta'(S_w,a)$，结论成立。

最终，NFA 存在接受路径，当且仅当 $S_w\cap F\ne\varnothing$，也就当且仅当 DFA 接受。所以 $L(M)=L(M')$。

图中的 $e$ 边是 $q_0\to q_1$、$q_1\to q_2$、$q_1\to q_3$、$q_4\to q_3$。因此

其余边为 $q_1\xrightarrow{a}q_0$、$q_1\xrightarrow{a}q_4$、$q_3\xrightarrow{a}q_4$、$q_0\xrightarrow{b}q_2$、$q_2\xrightarrow{b}q_4$。

将出现的集合命名为

初态是 $A$；$B,C,D$ 含有 $q_4$，因此是终态。

例如，从 $A$ 读 $a$ 的一步终点只有 $q_0,q_4$，但还要补上它们的闭包：

原来的 $5$ 个状态理论上对应 $32$ 个子集，实际只有上面 $5$ 个可达。构造可达 DFA 后仍可能需要最小化；“可达”与“不可合并”是两个条件。

abb 对应 $A\xrightarrow{a}B\xrightarrow{b}C\xrightarrow{b}D$。由于 $D$ 是终态，输入被接受。

为什么 NFA 不能直接交换终态与非终态求补？ 取一个初态 $s$，对 $a$ 同时转移到终态 $f$ 和非终态 $r$。原机器接受 a；交换终态后，通向 $r$ 的分支又接受 a。这没有得到补语言。“存在接受分支”的否定是“所有分支都不接受”，不是“存在拒绝分支”。

为什么不完整 DFA 要先补陷阱状态？ 缺失转移的输入原本拒绝；只交换已有状态的终态标记，并不能把这些输入变成接受。

星闭包为什么增加新初态？ 不能一般地把旧初态直接改成终态，否则到达旧初态但尚未完成一个合法块的串也会被接受。例如识别 $b^*a$ 的机器可在初态读 $b$ 自环；把它直接改成终态便接受 b，但 $b\notin(b^*a)^*$。

1. 分别为单个 $a,b$ 构造一条边的自动机。
2. 用连接构造得到 ab 和 aab 两条分支。
3. 增加初态，用 $e$ 边选择其中一条分支，得到 $ab\cup aab$。
4. 按星闭包构造加入可接受空串的新初态，并让完成一块后可以重新开始。

最后也可以整理成三个状态：$q_0$ 为初态兼唯一终态，转移为

其余转移不设置。这是允许缺失转移的 NFA；若要求 DFA，需要补拒绝陷阱状态。

e、ab、aab、abaabab 对应零个或多个合法块；a、abb 不被接受。这里 e 指空串，不是输入字母。

一条允许经过前 $k$ 个中间状态的路径，分为两类：

• 不把 $q_k$ 当作中间状态：属于第一项。
• 经过 $q_k$：先到 $q_k$，在 $q_k$ 之间往返零次或多次，再离开到达 $q_j$；各小段内部只经过编号小于 $k$ 的状态，对应第二项。

基础语言都是有限语言，因而正则。递推只使用并、连接、星闭包，所以对 $k$ 归纳可知所有 $R(i,j,k)$ 都正则。最后

是有限个正则语言的并，因此正则。这也证明了自动机到正则表达式方向的等价性。

原图有三个计数状态，读 $a$ 自环，读 $b$ 沿三状态环前进；余数为 $1$ 的状态接受。

加入新初态、终态后，消去余数为 $0$ 和 $2$ 的两个旧状态，留下余数为 $1$ 的状态。到达它的标签是 $a^*b$；在它上面的自环标签是

最后消去该状态，得到

先读一个 $b$，此后每个循环要么添加一个 $a$，要么添加三个 $b$ 并允许它们之间有任意多个 $a$。因此 $b$ 的数量始终为 $1\pmod 3$。

按计数块直接写，也可以得到等价表达式

消状态顺序不同，得到的表达式形式可以不同；需要相同的是所表示的语言。

令 $\Sigma=\{0,1,\ldots,9\}$。先用正则语言限制合法格式：

能被 $2$ 整除恰好要求末位为偶数：

能被 $3$ 整除恰好要求数位和是 $3$ 的倍数。用状态 $q_0,q_1,q_2$ 保存已读数值模 $3$ 的余数，读数字 $d$ 时

初态和唯一终态均为 $q_0$。记这台机器为 $M_3$，则

由交封闭性，$L$ 正则。比如 0、6、24 被接受，3、4、06 被拒绝。也可以直接使用模 $6$ 的 DFA，再与 $L_1$ 取交。

取识别 $L$ 的 DFA，设它有 $p$ 个状态。令 $w=a_1\cdots a_m\in L$，$m\ge p$。读取前 $p$ 个符号时，包含初态在内共经过 $p+1$ 次状态：

由抽屉原理，存在 $0\le r<t\le p$，使 $q_r=q_t$。令

于是 $|y|=t-r>0$，$|xy|=t\le p$。读取 $y$ 恰好从 $q_r$ 绕回 $q_r$，所以无论绕零次还是任意多次，再读取 $z$，都会到达原来的接受状态。因此所有 $xy^iz$ 都在 $L$ 中。

假设 $L$ 正则，泵长度为 $p$，取 $w=a^pb^p$。

对任意满足 $w=xyz$、$|xy|\le p$、$|y|\ge1$ 的分解，前 $p$ 个符号全是 $a$，所以必有 $y=a^t$，其中 $1\le t\le p$。

取 $i=0$，得到

这与泵引理矛盾，因此 $L$ 非正则。

重点是 $|xy|\le p$ 将所有可能的泵段都限制在第一段 $a$ 中，而不是我们自行把 $y$ 选成一个 $a$。

假设 $L$ 正则，泵长度为 $p$。取一个素数 $m\ge p$，并令 $w=a^m$。

任意合法分解的泵段都形如 $y=a^d$，$d\ge1$。取 $i=m+1$，则

两个因子都至少为 $2$，新长度是合数，故 $xy^{m+1}z\notin L$，矛盾。

这里不需要猜测“附近是否还有素数”，只需选择一定会产生合数的泵次数。

若 $L$ 正则，由于 $a^*b^*$ 正则，其交集也应正则。然而

右侧已经证明非正则，矛盾。

方法是：假设目标语言正则，再用正则语言过滤，得到一个已知非正则语言。 不能反过来声称“非正则语言与任何语言相交都非正则”，例如与空集相交总是正则。

把左、右括号暂记为 $a,b$，令 $B$ 为所有正确配对的括号串。若 $B$ 正则，则

也应正则，矛盾。这把“需要无限记忆”的直觉落实成了封闭性反证。

1. 有限语言一定正则。 每个单串都能写成表达式，有限语言就是有限个单串的并；空语言也正则。
2. 有限个正则语言的并一定正则。 反复使用二元并封闭性即可。
3. 可数个正则语言的并不一定正则。 每个 $\{a^nb^n\}$ 都是有限语言，但 $$\bigcup_{n\ge0}\{a^nb^n\}=\{a^nb^n:n\ge0\}$$ 非正则。
4. 可数个正则语言的交不一定正则。 在固定字母表 $\Sigma=\{a,b\}$ 上，令 $L_n=\Sigma^*-\{a^nb^n\}$，每个 $L_n$ 正则，但 $$\bigcap_{n\ge0}L_n=\Sigma^*-\{a^nb^n:n\ge0\}$$ 非正则，否则再取补便会使 $\{a^nb^n:n\ge0\}$ 正则。
5. 两个正则语言的差一定正则。 $L_1-L_2=L_1\cap\overline{L_2}$。
6. 正则语言的任意子集不一定正则。 $\{a^nb^n:n\ge0\}\subseteq a^*b^*$ 是反例。

“对并、交封闭”默认指二元运算及其有限次重复，不能直接推广到无限次运算。

如果 $\approx_L$ 有限，就把其等价类作为状态：

右不变性保证转移与代表元的选择无关；取后缀 $z=e$，可知同一类内的串同时属于或不属于 $L$，故终态也定义良好。

对输入长度归纳可得 $\widehat\delta([e],w)=[w]$，因此这台 DFA 恰好识别 $L$，且每个状态均可达。

反过来，若 $L$ 有一个有限状态 DFA，“到达同一状态”的分类比 $\approx_L$ 更细，所以 $\approx_L$ 的类数有限，且不超过 DFA 的状态数。

上述构造恰好达到这个下界，因而最小。任何同样大小的可达 DFA 都必须让每个类恰好对应一个状态；转移、初态和终态均由这些类确定，所以只可能在命名上不同。

令 $p\equiv_k q$ 表示长度不超过 $k$ 的任何后缀都不能区分 $p,q$。$\equiv_0$ 只比较空串，对应初始终态／非终态划分。

递推关系为

每次真拆分都会增加块数，而块数不超过 $|K|$，所以必定终止。若相邻两轮相同，由递推式可知之后也不会再变，此时所有长度的后缀都不能区分同块状态，恰好得到真正的状态等价关系。

合并后定义 $\delta'([q],a)=[\delta(q,a)]$，初态为 $[s]$，含终态的块为新终态。因为稳定划分中同块后继仍在同块，转移定义良好。

将输入从左到右每两个符号配成一组，会出现四种必要情况：

• $A=[e]=L$：已读部分恰好由合法块组成；可以结束，因此接受。
• $B=[a]=La$：完整块后多出一个 $a$，下一符号必须是 $b$。
• $C=[b]=Lb$：完整块后多出一个 $b$，下一符号必须是 $a$。
• $D=[aa]=L(aa\cup bb)\Sigma^*$：出现错误的两字符块，后续无法补救。

由此得到：

四类两两可区分：$A$ 与其余三类用空串；$B$ 与 $C,D$ 用 $b$；$C$ 与 $D$ 用 $a$。所以四状态既足够，也必需。

也可以从一台八状态 DFA 出发，先删除不可达的 $q_7,q_8$，剩六个可达状态。划分过程是

第二块中，$q_2$ 读 $b$ 到接受块；$q_4,q_6$ 读 $a$ 到接受块；$q_5$ 无论读 $a,b$ 都到非接受块。因此它分裂为三个块，最终分别对应 $B,C,D$。

令状态记录已经出现的符号集合 $A\subseteq\Sigma$，初态是空集；读 $a$ 后变为 $A\cup\{a\}$，当且仅当 $A\ne\Sigma$ 时接受。这给出一个 $2^n$ 状态 DFA，每个集合都可达。

再证明不同集合不能合并。设 $A\ne B$，不妨存在 $c\in B-A$。选一个后缀 $z$，让它恰好包含 $\Sigma-B$ 中的所有符号。

对于已见集合为 $B$ 的前缀，接上 $z$ 后已见全部符号，拒绝；对于已见集合为 $A$ 的前缀，接上 $z$ 后仍缺少 $c$，接受。因此 $A,B$ 可区分。

所有 $2^n$ 个集合对应不同等价类，故最小 DFA 恰有 $2^n$ 个状态。确定化的指数增长在最坏情况下确实无法避免。

这台 NFA 的转移为：$q_0\xrightarrow{a}q_0$，$q_0\xrightarrow{b,e}q_1$，$q_0\xrightarrow{b}q_3$；$q_1\xrightarrow{a}q_2$，$q_1\xrightarrow{b}q_4$；$q_2\xrightarrow{a,b}q_2$；$q_3\xrightarrow{a}q_4$；$q_4\xrightarrow{e}q_3$，$q_4\xrightarrow{a,b}q_2$。

依次取“读一个符号后的终点集合”的 $e$ 闭包，得到