这门课又被称为形式语言和自动机理论。采用的教材是 Michael Sipser 的 Introduction to the Theory of Computation, 即 计算理论导引 。

# 概述

初识这样一门不明所以的课程，首先要解决这是一门关于什么的课程的问题。简单说，这门课是关于计算的课程，包括可计算性、计算复杂性和自动机三个方面。而课程中所讲授的主要内容，是自动机的相关理论。因此，本篇笔记也会以自动机理论作为主要的内容。

可计算性指的是问题能否被计算出来，而计算复杂性指的是问题能否在一定的规模内被计算出来 (这样的规模通常是相对于输入长度 $l$ 或输入的某一数值大小 $n$ 的)，两者研究的都是在当前计算机求解问题背景下，该问题的性质。因此，我们需要构建当前计算机的抽象模型，或计算模型 (computational model)，就是我们所需要研究的自动机。

在这之前，我们需要先构建一些基本的概念。

# 字符串和语言

字符串和语言用来描述的是计算机或计算模型的输入和输出形式。因此，如何规范输入和输出的形式，输入和输出的信息能被进行怎样的操作 (运算)，是这里要解决的重点。

# 字符集

字符集 (alphabet) 是一个非空有穷集，常用 $\mathit{\Sigma}$ 表示，其中的元素称为符号 (symbol).

# 字符串

# 定义

字符串 (string) 是字符集中符号的有穷序列，常用 $w$ 表示。例如 $0101$ 是字符集 $\mathit{\Sigma}_1 = \{0,1\}$ 上的一个字符串。字符串 $w$ 的长度 (length) 是 $w$ 所包含的符号数，用 $|w|$ 表示。长度为 $0$ 的字符串称为空串 (empty string)，用 $\varepsilon$ 表示。

# 运算

若字符串 $w = w_1w_2\dots w_n$ , 则称 $w$ 的反转 (reverse) 为 $w^\mathbf{R}=w_nw_{n-1}\dots w_1$ . 若存在 $1 \leq i < j \leq n$ 使得 $z = w_iw_{i+1}\dots w_j$ , 则称 $z$ 是 $w$ 的子串 (substring).

对于两个字符串 $x = x_1x_2\dots x_m$ 及 $y = y_1y_2 \dots y_n$ , $x$ 与 $y$ 的连接 (connection)

# 语言

字符串的集合称为语言 (language). 对于一个字符集 $\mathit{\Sigma}$ , 我们称符号全部来自 $\mathit{\Sigma}$ 的所有字符串组成的集合为 $\mathit{\Sigma}$ 上的语言，记作 $\mathit{\Sigma}^*$ . $\mathit{\Sigma}^*$ 中排除空串 $\varepsilon$ 得到的语言记作 $\mathit{\Sigma}^+$ . 此外，长度为 $k$ , 且符号全部来自 $\mathit{\Sigma}$ 的全部字符串组成的语言记作 $\mathit{\Sigma}^k$ . 这些是关于语言的常见记号。

# 正则语言和有穷自动机

# 有穷自动机

# 确定性有穷自动机

有穷自动机 (finite automaton) 又称有穷状态机 (finite state machine)，是用来描述具有有限的算力和资源的计算机。为简化描述，我们将计算机的计算过程抽象成不同状态之间的转化，采用状态图 (state diagram) 进行描述。例如。下图是一个状态图：
Fig

# 正则性的判断

我们希望判断正则语言，于是期望找到一个正则语言的性质。泵引理 (pumping lemma) 就是这样一个性质：

若 $A$ 是一个正则语言，那么存在泵长度 (pumping length) $p$ ，使得对 $A$ 中长度超过 $p$ 的串 $s$ ，一定可以表示成 $s=xyz$ ，满足以下三个条件：

对任意 $i \geq 0$ ， $xy^iz \in A$
$|y|>0$
$|xy|\leq p$ .

可以感受到，该定理描述的是正则语言中长字符串的循环性质，而循环性质是来源于 DFA 状态的有限性，因此我们可以借助有限自动机的状态有限，借助抽屉原理证明。