计算理论基础：字母表、字符串与语言

在学习计算理论（Theory of Computation）时，自动机、上下文无关文法及图灵机等核心工具，本质上都是为了识别、转换或生成某种特定的“语言”。为了能够精确地讨论这些机器的行为，我们必须首先建立一套严密的数学基石。

本讲义将按照“字符 $\rightarrow$ 字符串 $\rightarrow$ 语言 $\rightarrow$ 判定系统”的逻辑顺序，带你彻底攻克计算理论的第一道关卡。

知识图谱与核心脉络

[ 字母表 (Alphabet) ]  ---> 允许使用的基本符号集合 (Σ)
         │
         ▼ (通过按顺序拼接)
[ 字符串 (String) ]    ---> 字符的有限序列 (w)，属于 Σ*
         │
         ▼ (通过设定筛选规则)
[ 语言 (Language) ]    ---> 满足特定规则的字符串集合 (L ⊆ Σ*)

第一部分：字母表 (Alphabet)

1. 概念引入

在日常生活中，我们有英文字母表、汉语拼音等。而在计算理论中，字母表（Alphabet）是所有允许使用的基本符号的有限非空集合。我们通常用希腊字母 $\Sigma$ (Sigma) 来表示。

2. 数学定义

字母表 $\Sigma$ 必须满足两个基本特征：

1. 有限性（Finite）：包含的符号数量是有限的。

2. 非空性（Non-empty）：至少要有一个符号。

3. 经典示例

• 二进制字母表：$\Sigma = \{0, 1\}$ （计算机最底层的字母表）

• 英文小写字母表：$\Sigma = \{a, b, c, \dots, z\}$

• 十进制字母表：$\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

• 自定义抽象符号表：$\Sigma = \{\text{猫}, \text{狗}\}$ 或 $\Sigma = \{a, b\}$

考试重点：字母表里的“符号”不一定局限于单字符，关键在于它们是组成更高级对象的“最小积木”。

第二部分：字符串 (String)

1. 概念引入

有了积木（符号），我们就可以把它们拼成更长的一串。字符串（String）就是由字母表 $\Sigma$ ****中的符号按顺序连接而成的有限序列。

2. 空字符串 (Empty String)

在计算理论中，有一个极为特殊的字符串——空字符串，记作 $\epsilon$（Epsilon，有些教材也写作 $\lambda$）。

• 定义：不包含任何符号的字符串。

• 理解：可以类比为数字中的“0”或集合中的空集 $\emptyset$，但注意它是一个字符串。

3. 补充考点：字符串的属性与运算

为了应对考试，我们需要补充笔记中未提及的几个高频考点：

(1) 字符串的长度 (Length)

字符串 $w$ 中所包含符号的个数，记作 $|w|$。

• 若 $w = 0110$，则 $|w| = 4$。

• 对于空字符串，恒有 $|\epsilon| = 0$。

(2) 字符串的连接 (Concatenation)

若 $u = ab$ 且 $v = ba$，则它们的连接记作 $uv = abba$。

• 性质：$\epsilon w = w\epsilon = w$ （任何字符串与空字符串连接，保持原样）。

(3) 字符串的幂运算 (Powers)

将同一个字符串连续连接若干次：

• $w^0 = \epsilon$

• $w^n = w^{n-1}w \quad (n \ge 1)$

• 例题：若 $w = ab$，则 $w^3 = ababab$。

第三部分：克莱尼星号与闭包 ($\Sigma^*$ 与 $\Sigma^+$)

1. 克莱尼星号 (Kleene Star) $\Sigma^*$

定义：由字母表 $\Sigma$ 能够拼出来的所有可能字符串（包括空字符串 $\epsilon$）*_构成的集合。 数学表达： $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \dots$ 其中 $\Sigma^0 = \{\epsilon\}$，$\Sigma^1 = \Sigma$，$\Sigma^2 = \{xx \mid x \in \Sigma\}$，依此类推。

示例

设 $\Sigma = \{a, b\}$，则：

$\Sigma^* = \{\epsilon, a, b, aa, ab, ba, bb, aaa, aab, \dots\}$

2. 正闭包 (Positive Closure) $\Sigma^+$

定义：由字母表 $\Sigma$ 能够拼出来的所有非空字符串构成的集合（即排除空字符串 $\epsilon$）。

$\Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \dots = \Sigma^* \setminus \{\epsilon\}$

🚨 易错点避坑指南：$abc$ 是否属于 $\{a, b\}^*$？

考试真题模拟： 设 $\Sigma = \{a, b\}$，请问字符串 $abc$ 是否属于 $\Sigma^*$？

• 错误解答：属于，因为它是由字符组成的。

• 正确解答：不属于 ($\notin \Sigma^*$)。

• 原因剖析： $\Sigma = \{a, b\}$ 的积木盒里只有 $a$ 和 $b$。而字符串 $abc$ 中出现了一个不在字母表中的符号 $c$。既然原料不足，我们就不可能用盒里的积木拼出 $abc$。 因此，$abc \notin \{a, b\}^*$。

• 记忆口诀：只要字符串里出现了一个不在当前字母表中的字符，该字符串就绝对不属于 $\Sigma^*$。

第四部分：语言 (Language)

1. 概念引入与数学定义

语言（Language） 其实就是字符串的集合。 在数学上，一个语言 $L$ 被定义为 $\Sigma^*$ 的一个子集：

$L \subseteq \Sigma^*$

• 语言可以包含有限个字符串，也可以包含无限个字符串。

• 空语言：不包含任何字符串的语言，记作 $\emptyset$（注意：$\emptyset \ne \{\epsilon\}$，前者不含任何元素，后者含有一个元素即空字符串）。

2. 集合描述符 $|$ 的考点透析

在考试中，语言通常采用集合构建器的形式给出：

$L = \{ w \in \Sigma^* \mid \text{条件} \}$

💡 学长提醒：不要与条件概率混淆 这里的竖线“$\mid$”（或冒号“$:$”）读作 “满足…的条件” (such that)，表示只有当字符串 $w$ 满足竖线后面的条件时，它才能进入集合 $L$。这与条件概率 $P(A \mid B)$ 中的“在…发生的条件下”有着完全不同的数学含义。

第五部分：核心实战——如何判断字符串是否属于语言？

考试中最经典的题型便是：给定一个语言定义 $L$ 和一个字符串 $w$，判断 $w \in L$ 是否成立？

我们将其拆解为一套四步判定法。

📋 判定标准四步法

1. 明确字母表 $\Sigma$：看清当前上下文允许使用哪些符号。

2. 前置合法性检查：判断待测字符串 $w$ 是否完全由 $\Sigma$ 中的字符组成（即 $w \in \Sigma^*$）。若否，直接判定 $w \notin L$。

3. 解读语言规则：仔细翻译集合定义中给出的限制条件（如：长度、首尾字符、特定字符数量等）。

4. 条件匹配验证：逐个检查 $w$ 是否完全符合这些规则。若全部满足，则 $w \in L$；否则 $w \notin L$。

✍️ 经典例题全解析（包含笔记精选及拓展题）

【例题 1】有限集合匹配

题目：设 $\Sigma = \{0, 1\}$，定义语言 $L = \{0, 01, 111\}$。 请判断以下字符串是否属于 $L$：

1. $w_1 = 01$

2. $w_2 = 10$

3. $w_3 = 1111$

解答过程：

• 对于 $w_1 = 01$：它直接出现在集合 $L$ 的显式列举中，因此 $01 \in L$。

• 对于 $w_2 = 10$：尽管 $10 \in \Sigma^*$，但它没有出现在 $L$ 中，因此 $10 \notin L$。

• 对于 $w_3 = 1111$：虽然由 $1$ 组成，但不在 $L$ 中，因此 $1111 \notin L$。

【例题 2】长度条件约束

题目：设 $\Sigma = \{0, 1\}$，定义语言 $L = \{ w \in \Sigma^* \mid w \text{ 的长度为偶数} \}$。 请判断以下字符串是否属于 $L$：

1. $w_1 = \epsilon$

2. $w_2 = 01$

3. $w_3 = 101$

解答过程：

• 对于 $w_1 = \epsilon$：$|\epsilon| = 0$。因为 $0$ 是偶数，所以 $\epsilon \in L$。

• 对于 $w_2 = 01$：$|01| = 2$。因为 $2$ 是偶数，所以 $01 \in L$。

• 对于 $w_3 = 101$：$|101| = 3$。因为 $3$ 是奇数，所以 $101 \notin L$。

【例题 3】首尾字符特征

题目：设 $\Sigma = \{a, b\}$，定义语言 $L = \{ w \in \Sigma^* \mid w \text{ 以 } a \text{ 开头} \}$。 请判断字符串 $w = ababa$ 是否属于 $L$。

解答过程：

1. 合法性检查：$ababa$ 仅包含 $a$ 和 $b$，因此 $ababa \in \Sigma^*$。

2. 规则检查：该语言要求“以 $a$ 开头”。

3. 比对：$ababa$ 的第一个字符是 $a$，满足条件。

• 结论：$ababa \in L$。

【例题 4】特定字符计数

题目：设 $\Sigma = \{a, b\}$，定义语言 $L = \{ w \in \Sigma^* \mid w \text{ 中恰好包含两个 } a \}$。 请判断字符串 $w = babab$ 是否属于 $L$。

解答过程：

1. 合法性检查：$babab \in \{a, b\}^*$。

2. 规则检查：要求“恰好包含两个 $a$”（即 $a$ 的个数等于 2）。

3. 计数比对：在 $babab$ 中，字符 $a$ 出现了 $2$ 次（分别在第 $2$ 和第 $4$ 个位置），字符 $b$ 出现了 $3$ 次。

• 结论：满足数量条件，因此 $babab \in L$。

【例题 5】多条件组合（综合演练）

题目：设 $\Sigma = \{0, 1\}$，定义语言 $L = \{ w \in \Sigma^* \mid w \text{ 以 } 01 \text{ 开头且以 } 10 \text{ 结尾} \}$。 请判断字符串 $w = 011110$ 是否属于 $L$。

解答过程：

1. 合法性检查：$011110 \in \{0, 1\}^*$，通过。

2. 拆解条件：

   • 条件 A：以 $01$ 开头。

   • 条件 B：以 $10$ 结尾。

3. 比对条件 A：$011110$ 的前两个字符为 $01$，满足。

4. 比对条件 B：$011110$ 的最后两个字符为 $10$，满足。

• 结论：由于同时满足条件 A 和条件 B，因此 $011110 \in L$。

📊 快速判定速查表

语言定义 $L$	待测字符串 $w$	是否属于 $L$	原因解析
所有以 $1$ 结尾的字符串	$1010$	不属于 ($\notin L$)	最后一个符号是 $0$
所有长度为偶数的字符串	$1100$	属于 ($\in L$)	长度为 4，4 是偶数
所有恰好包含两个 $a$ 的字符串	$ababa$	不属于 ($\notin L$)	包含 3 个 $a$，不满足“恰好两个”
所有至少包含一个 $b$ 的字符串	$aaaa$	不属于 ($\notin L$)	包含 0 个 $b$，不满足“至少一个”
所有由 $\{a,b\}$ 组成的字符串	$abc$	不属于 ($\notin L$)	$c \notin \Sigma$，根本不是合法的输入串

第六部分：承前启后——这些基础与后续课程有什么联系？

你现在掌握的“判断字符串是否属于某语言”是整个计算理论课程的核心灵魂。后续你将要学到的所有进阶工具，其本质都是围绕这个概念展开的：

                    ┌───────  DFA / NFA  (有限自动机：识别正则语言)
                    ├───────  PDA (下推自动机：识别上下文无关语言)
 识别 w 是否属于 L ──┼───────  Regex (正则表达式：描述语言的规则)
                    └───────  Turing Machine (图灵机：识别可计算语言)

1. DFA / NFA (确定性/非确定性有限自动机)：这就是一个“机器判定系统”。你输入一个字符串，机器在内部状态流转，最后停在“接受状态”则表示 $w \in L$，停在“拒绝状态”则表示 $w \notin L$。

2. 正则表达式 (Regular Expression)：一种用来高效描述语言 $L$ 的数学表达式。例如，用 $a(a \mid b)^*b$ 描述所有“以 $a$ 开头且以 $b$ 结尾的字符串”。

3. 图灵机 (Turing Machine)：计算理论的核心巅峰。它通过读写带判定任何复杂语言的归属问题，并据此定义了什么是“可计算的”。

掌握了字母表、字符串和语言的基础，你就已经拿到了进入计算理论殿堂的入场券！