自动机

前置概念

• 字母表：符号的集合，例如英文字母表、二进制字母表 $\{0,1\}$
• 字符串：符号构成的有限序列，空字符串用 $\epsilon$ 表示。字符串的长度用 $|a|$ 表示。
• ${\Sigma }^n$ 表示所有长度为 $n$ 的字符串组成的集合，${\Sigma }^{\ast }$ 表示所有字符串组成的集合。
• 来自相同字母表的字符串可以拼接。$x$ 和 $y$ 拼接用 $xy$ 表示。
• 次方：$01^2:=0101$。
• 反转：用 $a^R$ 表示。
• 语言：$L\subseteq {\Sigma }^{\ast }$
• $L^{\ast }$ 就是 $L$ 中任意多个字符串拼接得到的新字符串集合。

DFA

有限自动机是一个五元组 $(Q,\Sigma ,\delta ,q_0,F)$，其中

• $Q$ 是有限状态集
• $\Sigma$ 是字母表
• $\delta :Q\times \Sigma \to Q$ 是转移函数
• $q_0\in Q$ 是起始状态
• $F\subseteq Q$ 是接收状态

如果 $M$ 接收的字符串组成的集合为 $M$，则写 $L(M)$，表示 $M$ 识别 $L$。

IMPORTANT

判定和识别是不一样的。识别（recognize）只要求自动机接收满足要求的字符串，而对其他的没有要求；判定（decide）要求对于其他的停机并拒绝。

NFA

• 确定型有限自动机：DFA，一个状态 + 一个字母 唯一推出下一个状态
• 非确定型有限自动机：NFA，可能有多个下一个状态，只要有一种到达接收状态，就说它接收输入。

NFA 是一个五元组 $(Q,\Sigma ,\delta ,q_0,F)$

• $Q$ 是有限状态集
• $\Sigma$ 是字母表
• $\delta :Q\times (\Sigma \cup \{\epsilon \})\to \mathcal{P}(Q)$ 是转移函数，其中 $\mathcal{P}(Q)$ 是 $Q$ 的幂集
• $q_0\in Q$ 是起始状态
• $F\subseteq Q$ 是接收状态

每个 NFA 都可以转换为一个 DFA。定义这个 DFA：

• $Q^{\prime }:=\mathcal{P}(Q)$
• ${\delta }^{\prime }(R,a):={\bigcup }_{r\in R}E(\delta (r,a))$，其中 $E(q)$ 表示 $q$ 自己或者是 $q$ 经过 $\epsilon$ 转移得到的状态集合

GNFA

GNFA 在 DFA 的基础上，还要求：

• 初始状态没有入边
• 接收状态没有出边
• 其他状态都有到每个其他状态以及它自己的边

WARNING

虽然 GNFA 的名字，但是它跟 DFA 更像。

每个 DFA 都可以转换为一个 GNFA。转换方法：

• 加一个新状态作为初始状态，用 $\epsilon$ 连到旧的初始状态。
• 加一个新状态作为接收状态，用 $\epsilon$ 连到旧的接收状态。
• 补充连边。

正则语言

称一个语言是正则的当且仅当有一个有限自动机识别它。这可以是 $NFA$ 也可以是 $DFA$。

识别正则语言的时间复杂度是 $\mathrm{O}(n)$，空间复杂度是 $\mathrm{O}(1)$。

正则语言的并、连接、$\ast$ 和补操作保持正则语言。

一个语言是正则语言当且仅当它可以被正则表达式表达。

泵引理

若 $L$ 是一个正则语言，则存在 $p$ 使得对任意长度至少为 $p$ 的字符串 $s\in L$，$s$ 可以拆成三部分的拼接形式 $xyz$ 并且

• $x{y}^{i}z\in L\forall i⩾0$
• $|y|>0$
• $|xy|⩽p$

TIP

可以用来反证 $L$ 不是正则语言。