• ChatGPT - Regular Language 闭包性质

计算理论复习笔记：正则语言的闭包性质与正则表达式

本笔记旨在帮助你快速、系统地掌握正则语言（Regular Language）的闭包性质（Union, Concatenation, Kleene Star）及其在正则表达式中的应用。本篇内容特别针对大阪大学情报工学专攻《计算理论》科目的常考点、经典思维误区进行梳理，并配有完整的演练解析。

第一部分：理解“闭包”与“自动机识别”

在深入具体的运算之前，我们必须首先在数学概念上达成共识，理清“闭包”的定义以及“自动机与语言”的本质区别。

1.1 什么是闭包（Closure）？

在数学中，“闭包”是一个非常优美的代数概念。

闭包定义：若一个集合 $S$ 在进行某种运算 $\text{op}$ 后，其结果仍然属于该集合 $S$，则称集合 $S$ 对运算 $\text{op}$ 具有闭包性（Closed under $\text{op}$）。

💡 核心类比：线性空间

正如你在物理或线性代数中学到的线性空间（Vector Space）：

• 设向量 $u, v \in V$，则其加法 $u + v$ 仍然属于 $V$。

• 设标量 $\alpha$，则数乘 $\alpha u$ 仍然属于 $V$。 由于运算结果不会脱离这个空间，我们称该空间对加法和数乘运算封闭。

计算理论中的映射：

• 我们的“空间”是：正则语言家族（The Family of Regular Languages）。

• 我们的“元素”是：正则语言 $L$（注意：语言是字符串的集合，而不是单个字符串）。

• 我们的“运算”是：并（Union）、连接（Concatenation） 和 Kleene 星号（Kleene Star）。 如果两个正则语言经过这些运算后，得到的全新语言仍然可以用 DFA、NFA 或正则表达式来表示（即仍属于正则语言家族），那么就称正则语言对这些运算具有闭包性质。

1.2 纠正盲区：DFA（机器）与 Language（语言）的区别

在学习中，初学者常问：“DFA 里面不都是状态吗？为什么我们可以说‘DFA $M_1$ 识别 $L_1$’？语言是怎么被放进机器里的？”

我们需要在逻辑上严格区分以下两个对象：

对象	定义与本质	角色/类比	举例
DFA (机器 $M$)	一个五元组形式化定义的数学模型： $M = (Q, \Sigma, \delta, q_0, F)$	分类器/判定机 类似于数字电路中的有限状态机（FSM）。状态转移由下一状态逻辑（驱动方程）决定，最终停留在接受状态相当于输出为 $1$。	具有状态集合 $\{q_0, q_1\}$，输入字母表 $\{0, 1\}$，转移函数，起始状态与接受状态。
Language (语言 $L$)	字符集 $\Sigma$ 上的字符串集合（Set of Strings）。	判定的数据集 里面装的是一个一个的“字符串”，不含任何状态。	$L = \{0, 00, 000, \dots\}$ 或 $L = \{w \mid w \text{ 以 } 1 \text{ 结尾}\}$

🔑 “识别（Recognize）”的本质

我们并没有把语言“放进” DFA。DFA $M$ 就像一个守门人：

1. 你输入一个字符串 $w$。

2. $M$ 顺着字符一个一个做状态转移。

3. 读完最后一个字符后：

   • 若当前状态 $q \in F$（接受状态），则 $M$ 接受（Accept） $w$。

   • 若当前状态 $q \notin F$（非接受状态），则 $M$ 拒绝（Reject） $w$。

我们将所有能被 $M$ 接受的字符串收集起来，组成一个集合，这个集合就是由机器 $M$ 识别的语言，记作 $L(M)$。

$L(M) = \{w \in \Sigma^* \mid M \text{ 接受 } w\}$

若一个语言 $L$ 能够被某台 DFA $M$ 识别（即 $L = L(M)$），那么根据定义，$L$ 就是一个正则语言。

📝 概念微测

问题：若一台 DFA $M$ 接受且仅接受字符串 $0, 00, 000$，拒绝其他所有输入，那么它所识别的语言 $L(M)$ 应如何用标准的集合表示？ 答案：$L(M) = \{0, 00, 000\}$。

第二部分：三大核心闭包性质详解

现在我们正式引入正则语言家族最著名的三个闭包性质：并（Union）、连接（Concatenation） 与 Kleene 星号（Kleene Star）。

                    ┌───────── 闭包性质 (Closure) ─────────┐
                    │                                     │
            1. 并 (Union) ∪                       2. 连接 (Concat) ·
      L1 ∪ L2 = {w | w ∈ L1 或 w ∈ L2}       L1L2 = {xy | x ∈ L1, y ∈ L2}
                    │                                     │
                    └──────── 3. Kleene Star (*) ─────────┘
                            L* = L⁰ ∪ L¹ ∪ L² ∪ ...

2.1 并运算 (Union) $\cup$

• 数学定义：

  $L_1 \cup L_2 = \{w \mid w \in L_1 \text{ 或 } w \in L_2\}$

• 通俗口诀：Union = OR (或)。只要字符串属于其中一个语言，就属于它们的并集。

• 例题： 若 $L_1 = \{0, 00\}$，$L_2 = \{1, 11\}$。 则 $L_1 \cup L_2 = \{0, 00, 1, 11\}$。

🛠️ 大阪大学常考构造法：乘积自动机 (Product Automaton)

如果 $L_1$ 和 $L_2$ 是正则语言，说明分别存在 DFA $M_1$ 和 $M_2$ 识别它们。 为了证明 $L_1 \cup L_2$ 也是正则语言，我们需要利用已知的 $M_1$ 和 $M_2$ 构造出一个新的 DFA $M$ 来识别并集。

1. 状态空间：$Q = Q_1 \times Q_2$，新状态写成二元组 $(q_i, q_j)$，表示同时记录两台 DFA 的当前状态。

2. 接受状态：

   $(r_1, r_2) \in F \iff r_1 \in F_1 \text{ 或 } r_2 \in F_2$

   即：只要第一台机器达到接受状态，或者第二台机器达到接受状态，新机器就接受。 (注：2026年大阪大学真题第 (2) 问就是要求考生填入积自动机的状态定义，来构造识别并集的 DFA。)

2.2 连接运算 (Concatenation) $\cdot$

• 数学定义：

  $L_1 L_2 = \{xy \mid x \in L_1, y \in L_2\}$

  其中 $xy$ 表示将字符串 $x$ 与 $y$ 首尾拼接。

• 通俗口诀：前半截来自第一个语言，后半截来自第二个语言。

• ⚠️ 避坑指南：连接运算不是集合取并，也不是简单的对应位置字符相乘。并且，连接是有顺序性的，即一般情况下 $L_1 L_2 \neq L_2 L_1$。

• 例题： 设 $L_1 = \{0, 11\}$，$L_2 = \{a, b\}$。 求连接结果 $L_1 L_2$。

  解析步骤： 我们将 $L_1$ 中的每一个元素与 $L_2$ 中的每一个元素逐一拼接：

  1. 用 $L_1$ 的 $0$ 拼接 $L_2$ 的元素 $\rightarrow 0a, 0b$

  2. 用 $L_1$ 的 $11$ 拼接 $L_2$ 的元素 $\rightarrow 11a, 11b$

  答案：$L_1 L_2 = \{0a, 0b, 11a, 11b\}$。

2.3 Kleene 星号运算 (Kleene Star) $*$

• 数学定义：

  $L^* = \bigcup_{k=0}^{\infty} L^k = L^0 \cup L^1 \cup L^2 \cup L^3 \cup \dots$

  其中规定：

  • $L^0 = \{\epsilon\}$（只含有空串 $\epsilon$ 的集合，相当于连接 0 次）。

  • $L^1 = L$（原语言本身）。

  • $L^2 = L L$（自己和自己连接，即任意两个原字符串拼接）。

  • $L^k = \underbrace{L L \dots L}_{k \text{ 次}}$。

• 通俗口诀：从语言中任选若干个字符串进行任意次（包括0次）拼接。

⚠️ 最容易失分的考点：空串 $\epsilon$

因为 $L^*$ 中一定包含 $L^0$，而 $L^0 = \{\epsilon\}$。 所以，对于任何语言 $L$，其 Kleene 星号运算结果 $L^*$ 必然包含空串 $\epsilon$！ 在考试时，无论括号里多复杂，只要最外层有 $*$，第一时间在答案里检查是否包含空串。

• 例题 1： 设 $L = \{ab\}$，求 $L^*$ 的前 4 个元素（按长度递增排列）。

• 解析：

  • 重复 0 次 ($L^0$)：$\epsilon$

  • 重复 1 次 ($L^1$)：$ab$

  • 重复 2 次 ($L^2$)：$abab$

  • 重复 3 次 ($L^3$)：$ababab$ 答案：$\{\epsilon, ab, abab, ababab\}$

• 例题 2： 设 $L = \{01, 1\}$。

  1. 求 $L^2$ 的结果。

  2. 求 $L^*$ 中所有长度不超过 3 的字符串集合。

  3. 判断字符串 $011$ 是否属于 $L^*$，并给出理由。

  详细解析：

  4. 求 $L^2 = L L$： 将 $\{01, 1\}$ 与自身进行连接运算：

     $\begin{aligned} 01 \cdot 01 &= 0101 \\ 01 \cdot 1 &= 011 \\ 1 \cdot 01 &= 101 \\ 1 \cdot 1 &= 11 \end{aligned}$

     所以：$L^2 = \{0101, 011, 101, 11\}$。

  5. 求 $L^*$ 中长度不超过 3 的串： 我们必须全面考察 $L^0, L^1, L^2, L^3 \dots$：

     • $L^0 = \{\epsilon\}$（长度 0，符合）

     • $L^1 = \{01, 1\}$（长度 2, 1，符合）

     • $L^2 = \{0101, 011, 101, 11\}$（长度超过 3 的 $0101$ 舍弃，保留 $011, 101, 11$）

     • $L^3 = L^2 L$： 我们用 $L^2$ 的串连接 $L$：

       • $11 \cdot 1 = 111$（长度 3，符合）

       • 其他拼接如 $11 \cdot 01 = 1101$（长度 4，舍弃）

     • $L^4$ 及以上：生成的字符串长度必然 $\ge 4$，舍弃。

     综上，将所有符合的串取并集： 答案：$\{\epsilon, 1, 11, 01, 111, 011, 101\}$。

  6. 判断 $011 \in L^*$ 吗？ 答案：属于。 理由：因为 $011$ 可以被拆分为 $01 \cdot 1$，其中 $01 \in L$ 且 $1 \in L$。属于 $L^2$，因此必然属于 $L^*$。_(注意：属于 L^_ 的判定依据是“能够被原语言中的子串拼接而成”，与其长度无关)*。

第三部分：正则表达式 (Regular Expression, Regex) 的代数意义

正则表达式是描述正则语言的代数符号系统。它把我们上面学的“三大闭包性质”转化为可书写的算式。

3.1 符号映射表

在计算理论与考试中，正则表达式的符号有以下严格定义：

正则表达式符号	对应的集合运算	含义说明
+ (或 $\mid$)	Union (并)	从左右候选表达式中选择一个匹配（OR 关系）。
直接相邻	Concatenation (连接)	按顺序先后拼接。
*	Kleene Star (星号)	括号内部的表达式可以重复任意次（包括 0 次）。

⚠️ 极其重要的思维纠正：选择的动态性

很多同学在看到 $(0+1)^*$ 时，会误以为：“先在 $0$ 和 $1$ 中挑一个，然后一直重复它（比如只能生成 $0000$ 或 $1111$）”。 这是完全错误的！

正确逻辑：最外层的 Kleene Star $*$ 代表了多次的拼接动作。在每一次进行拼接时，都可以重新在括号内部 $(0+1)$ 里进行一次独立的选择（选 $0$ 或者是选 $1$）。

• 生成过程演示：如何用 $(0+1)^*$ 生成 $10110$？

  • 第 1 次重复：在 $(0+1)$ 中选择 $1$

  • 第 2 次重复：在 $(0+1)$ 中选择 $0$

  • 第 3 次重复：在 $(0+1)$ 中选择 $1$

  • 第 4 次重复：在 $(0+1)$ 中选择 $1$

  • 第 5 次重复：在 $(0+1)$ 中选择 $0$

  • 重复结束。拼接后得到：$10110$。 因此，$(0+1)^*$ 匹配的是所有由 $0$ 和 $1$ 组成的任意有限长度二进制字符串（包含空串 $\epsilon$）。

3.2 经典正则表达式案例分析 (大阪大学高频考点)

为了在考试中实现秒杀，以下几个基础表达式需要像条件反射一样熟记：

📌 案例一：$(0+1)^*$

• 语言含义：所有由 $0$ 和 $1$ 组成的任意二进制字符串。

• 是否含 $\epsilon$：是。

📌 案例二：$(0+1)^* 1$

• 语言含义：前面可以是任意 0/1 串，但最后必须强制连接一个 $1$。即：所有以 $1$ 结尾的二进制串。

• 是否含 $\epsilon$：否（因为最后强制有 $1$，长度至少为 $1$）。

📌 案例三：$(0+1)^* 01$

• 语言含义：前面是任意 0/1 串，最后固定接 $01$。即：所有以 $01$ 结尾的二进制串。

• 是否含 $\epsilon$：否。

3.3 进阶练习与概念巩固

我们通过以下三个小题来检验阶段性学习成果：

✏️ 题 1：$1^*(0+1)$ 表示什么语言？请列举部分元素。

• 解析：

  • $1^*$ 代表任意多个 $1$（包括 0 个）。

  • $(0+1)$ 代表在末尾必须且只能在 $0$ 和 $1$ 中选择一个。

  • 将两部分进行连接运算，等价于：$1^*0 \cup 1^*1$。

• 答案：表示“若干个（可为0个）$1$ 后，接一个 $0$ 或 $1$”。

• 典型元素：$\{0, 1, 10, 11, 110, 111, 1110, \dots\}$。

✏️ 题 2：正则表达式 $(0+1)0$ 表示哪些字符串？

• 解析：

  • 括号 $(0+1)$ 表示选 $0$ 或 $1$。

  • 后面连接一个 $0$。

  • 结果为：选 $0$ 时连接 $0 \rightarrow 00$；选 $1$ 时连接 $0 \rightarrow 10$。

• 答案：仅表示集合 $\{00, 10\}$。(注意：不要写成小集合的并集形式，要直接写出拼接后的字符串)。

✏️ 题 3：$(0+1)^*0$ 用自然语言如何描述？

• 答案：所有由 $0$ 和 $1$ 组成、且最后一个字符（结尾）为 $0$ 的字符串。

第四部分：真题与高难题特训

现在，我们拿大阪大学的真题和极易混淆的压轴题来进行实战演练。

4.1 大阪大学 2026 年真题演练 (简化版)

【问题】：下面四个正则表达式中，哪一个表示“所有以 $11$ 结尾的二进制字符串”？ A. $(0+1)^*$

B. $(0+1)^*11$

C. $11(0+1)^*$

D. $1^*(0+1)$

【深度解析】：

• 选 A：代表所有二进制字符串，不要求以 $11$ 结尾。❌

• 选 B：$(0+1)^*$ 表示前半段是任意二进制字符串，最后 Concatenation（连接）一个 $11$，所以整串一定以 $11$ 结尾。符合题意。

• 选 C：表示开头必须是 $11$，后接任意二进制串。❌

• 选 D：表示若干个 $1$ 后面接一个 $0$ 或 $1$。❌

【答案】：B

4.2 终极压轴题深度剖析：$R = ((0+1)^*11)^*$

这道题是大阪大学最喜欢用于拉开差距的题目。由于双重 $*$ 嵌套，对概念的清晰度要求极高。

🔍 步步拆解：

我们将 $R = (A)^*$ 展开，其中内部表达式为 $A = (0+1)^*11$。 我们已经知道，$A$ 的物理含义是：“所有以 $11$ 结尾的字符串”。 那么，外层的 $*$ 代表：我们可以从这个集合 $A$ 中，任选若干个串，进行首尾连接。 也就是说：

$R = A^0 \cup A^1 \cup A^2 \cup A^3 \dots$

我们来逐一判定以下四个字符串是否属于 $R$：

1️⃣ 字符串：$\epsilon$

• 判定：属于。

• 原因：因为最外层是 Kleene Star，根据定义 $A^0 = \{\epsilon\}$ 必然在集合中，代表重复 0 次。

2️⃣ 字符串：$11$

• 判定：属于。

• 原因：由于 $11$ 本身就属于 $A$（因为 $11$ 是以 $11$ 结尾的），我们在外层选择重复 1 次（即 $A^1$）即可得到。

3️⃣ 字符串：$1111$

• 判定：属于。

• 原因：

  • 我们将它切分成两部分：$1111 = 11 \cdot 11$。

  • 第一部分 $11 \in A$，第二部分 $11 \in A$。

  • 根据 $A^2 = AA$，我们可以在第一遍时选择 $11$，在第二遍时也选择 $11$。

  • 拼接起来就是 $1111$。

4️⃣ 字符串：$1010$

• 判定：不属于。

• 原因：

  • 要想让一个串属于 $A^*$，它必须能够被拆分成若干段，且每一段都必须以 $11$ 结尾。

  • $1010$ 无法做这样的拆分。

  • 它本身也不以 $11$ 结尾，因此也不在 $A^1$ 中。

💡 核心总结公式

((0+1)^*11)^* \text{ 识别的语言是：}$$$$\text{所有能够被拆分为“若干个（含0个）均以 11 结尾的子串”相拼接而成的字符串。}

第五部分：复习自测黄金题库

请独立完成以下自测题，并对照答案解析，确保你的理解没有任何死角。

📝 巩固自测题

1. 若正则语言 $L_1$ 识别所有偶数长度的二进制字符串，$L_2$ 识别所有以 $0$ 结尾的二进制字符串。请问：

   • 字符串 $0101$ 属于 $L_1 \cup L_2$ 吗？

   • 字符串 $0101$ 属于 $L_1 L_2$ 吗？

2. 写出正则表达式 $(01+10)^*$ 能够生成的前 5 个最矮（长度递增）的字符串。

3. 如果一个正则表达式为 $(0+1)^* 0 (0+1)^*$，用自然语言应该如何描述它识别的语言？

🔑 答案与解析

第 1 题解析

• 第 1 问答案：属于。

  • 理由：$0101$ 的长度是 $4$（偶数），所以它属于 $L_1$。既然属于 $L_1$，根据并运算的定义（或关系），它必然属于并集 $L_1 \cup L_2$。

• 第 2 问答案：属于。

  • 理由：我们需要将 $0101$ 拆分成 $xy$ 的形式，使 $x \in L_1$ 且 $y \in L_2$。

  • 我们可以切分为：$x = 01$（长度为 2，属于偶数长度语言 $L_1$），$y = 01$（以 $1$ 结尾，不属于 $L_2$）$\rightarrow$ 失败。

  • 重新切分：$x = 010$（长度为 3，不属于 $L_1$）$\rightarrow$ 失败。

  • 重新切分：$x = \epsilon$（长度为 0，属于偶数长度语言 $L_1$），$y = 0101$（不以 $0$ 结尾，不属于 $L_2$）$\rightarrow$ 失败。

  • 等等，我们是不是漏了什么？ * 仔细观察：$0101$ 无法切分成 $x \in L_1$ 且 $y \in L_2$。

    • 若 $y$ 取最后一位 $1$（不以 $0$ 结尾），不行。

    • 若 $y$ 取最后两位 $01$（不以 $0$ 结尾），不行。

    • 若 $y$ 取最后三位 $101$（不以 $0$ 结尾），不行。

    • 若 $y$ 取全串 $0101$（不以 $0$ 结尾），不行。

  • 所以，$0101$ 不属于 $L_1 L_2$。

第 2 题解析

• 答案：$\{\epsilon, 01, 10, 0101, 0110\}$（注：长度为 $4$ 的串还有 $1001, 1010$，只要写出其中两个即可）。

• 解析：

  • 重复 0 次：$\epsilon$（长度 0）

  • 重复 1 次：在 $01$ 和 $10$ 中选一个 $\rightarrow 01, 10$（长度 2）

  • 重复 2 次：在 $\{01, 10\} \times \{01, 10\}$ 中选择拼接 $\rightarrow 0101, 0110, 1001, 1010$（长度 4）

第 3 题解析

• 答案：所有包含至少一个 $0$ 的二进制字符串。

• 解析：

  • 该表达式由三部分连接而成：前面是任意二进制串 $(0+1)^*$，中间是强制的字符 $0$，后面是任意二进制串 $(0+1)^*$。

  • 只要一个二进制串中含有一个 $0$，我们就可以把它写成“$0$ 左侧的全部串 + 字符 $0$ + $0$ 右侧的全部串”的形式，这与该正则表达式完全契合。