本课程《形式语言与自动机》实际介绍的是一种理论，称为「自动机理论」。这种理论尝试用一种没有思考能力，只能按既定规则动作的「机器」去解读符合一定「文法」的「语言」，从而实现计算的自动化。显然，这套理论奠定了现代信息时代的基础。

本课程介绍了 3 种不同「级别」的文法、语言和它们对应的自动机，如下表所示：

其中「乔姆斯基层级」是一个用来衡量语言、文法的「自由」程度的指标。类型 1 的乔姆斯基层级对应的是「上下文有关语言」，在这门课中没有提及。

字母表与字符串

字母表、字符串是形式语言与自动机理论所研究的重要对象，因此有必要对这些看起来很直白的东西进行「数学化」的定义。

• 符号：一种抽象的实体，难以形式地定义。$0$ 可以是「符号」，$1$ 也可以是符号，$\xi$ 和 $\varkappa$ 还有 $\mathfrak{Y}$ 都可以是符号。
• 字母表：有穷的、非空的符号集合，一般记作 $\Sigma$。例如，$\Sigma=\{0, 1\}$ 表示包含 $0$ 和 $1$ 两种符号的字母表。
• 字符串：一个字母表中的符号构成的有穷序列，也称「字」。例如，对于字母表 $\Sigma = \{0, 1\}$，$01001$、$1110101010$ 都是这个字母表上的字符串。
• 字符串的长度：一个字符串中符号的个数。对于字符串 $w$，它的长度记作 $|w|$。
• 空串：长度为 0 的字符串，表示为 $\varepsilon$。
• 字符串的连接：$xy$ 表示将 $x$ 和 $y$ 两个字符串「拼接」在一起后的字符串。例如，$x = 011$，$y = 10010$，则 $xy=01110010$。
• 字符串的逆序：若 $w=a_1a_2\cdots a_n$，则 $w^R = a_na_{n-1}\cdots a_0$ 称为字符串 $w$ 的逆序。
• 集合的连接，又称乘积：$AB=\{ab|a\in A, b\in B\}$。
• 集合的幂：定义
  • $\Sigma^0=\{\varepsilon\}$
  • $\Sigma^n=\Sigma^{n-1}\Sigma,n>0$
• 正闭包：定义 $\Sigma^+=\Sigma\cup\Sigma^2\cup\Sigma^3\cup\cdots$。显然，$\Sigma^+$ 的现实意义是「字母表 $\Sigma$ 上所有非空字符串的集合」。
• 克林闭包：定义 $\Sigma^=\Sigma^0\cup\Sigma^+$。显然，$\Sigma^$ 的现实意义是「字母表 $\Sigma$ 上所有字符串的集合」。

语言与文法

若 $\Sigma$ 是字母表，则 $\forall L\sube\Sigma^*$，$L$ 称为字母表 $\Sigma$ 上的一个语言。例如：