Formal Language and Automata

关于形式语言与自动机技术这门课我认为内容非常的少，考生只需要掌握正则语言，上下文无关语言以及其对应的自动机模型就可以了。自动机里面的状态转移图和数字电路中的时序电路设计有异曲同工之妙。我觉得这门课是一门很需要脑筋急转弯的课程…To learn this course, you have to preview Data Structure & Algorithm

Reference：

1. 哈工大Mooc by 王春雨
2. MIT Sisper

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio

1. Introduction

形式语言与自动机技术这门课的内容包括：

• 形式语言：定义计算语言的方式（正则语言、上下文无关语言等）。
• 自动机：描述语言识别的数学模型（有限自动机、下推自动机等）。
• 计算理论：讨论问题是否可以通过算法解决（可计算性）以及解决问题的资源消耗（复杂性）。

首先在学习这门课，我们需要认识一些自动机所需要的一些表示方法。这些表示方法在我们的有穷自动机和下推自动机同样适用。

1.1 字母表（Alphabet）

在形式语言与自动机中，字母表（Alphabet） 是一个基本的概念，它是用于构造语言的最小组成单位。字母表（通常记为 $\Sigma$）是一个有限的符号集合，其中的每个符号称为一个字母。

例如：

• $\Sigma = \{a, b\}$ 表示一个字母表，包含两个字母 $a$ 和 $b$。
• $\Sigma = \{0, 1\}$ 表示一个二进制字母表。
• $\Sigma = \{x, y, z\}$ 表示一个包含三个符号的字母表。

字母表是字符串和语言的基础：

1. 字符串：是由字母表中的符号按一定顺序排列而成的有限序列。

   • 例如：对 $\Sigma = \{a, b\}$，字符串可以是 $a$, $b$, $ab$, $bba$ 等。
   • 空字符串用 $\epsilon$ 表示，表示长度为 0 的字符串。

2. 语言：是字母表上所有字符串的某个子集。

   • 例如：对于 $\Sigma = \{a, b\}$，语言可以是所有以 $a$ 开头的字符串 $\{a, ab, abb, \dots\}$。

注意事项

• 字母表是有限的，但基于字母表生成的字符串集合可能是无限的。
• 字母表的大小和定义取决于具体问题的需求。

1.2 字符串（String）

在形式语言与自动机中，字符串（String） 是一个由字母表中符号按一定顺序排列而成的有限序列。字符串的定义如下

1. 给定字母表 $\Sigma$（一个有限符号集合），字符串是由 $\Sigma$ 中的符号组成的一个有限长度序列。

   • 例如：若 $\Sigma = \{a, b\}$，字符串可以是 $a$, $b$, $ab$, $bba$ 等。

2. 字符串的长度是序列中符号的个数，记为 $|w|$，其中 $w$ 是字符串。

   • 例如：若 $w = abba$，则 $|w| = 4$。

3. 特殊情况：空字符串表示长度为 $0$ 的字符串，用符号 $\epsilon$ 表示。

   • $\epsilon$ 是唯一的长度为 $0$ 的字符串，即 $|\epsilon| = 0$。
   • 注意，$\epsilon \notin \Sigma$ ，下面简单辨析一下
     • 字母表 $\Sigma$ 是一个有限符号的集合，表示语言构造的基本单位。它仅包含单个符号，不包括空字符串。
     • 空字符串 $\epsilon$ 是字符串的概念，它表示一个长度为 $0$ 的特殊字符串，而不是字母表中的符号。

常见的字符串的操作:

1. 连接：将两个字符串首尾相接形成新字符串。

   • 若 $w_1 = ab$ 且 $w_2 = ba$，则 $w_1w_2 = abba$。

2. 幂运算：将字符串自身重复多次，记为 $w^n$（$n \geq 0$）。

   • 例如：若 $w = ab$，则 $w^0 = \epsilon$，$w^1 = ab$，$w^2 = abab$。

3. 反转：将字符串的符号顺序倒置。

   • 例如：若 $w = abba$，则 $w^R = abba$。

下文会对常见的字符串操作进行详细推导。

字符串与语言的区别

• 字符串是语言的基本组成单位。
• 语言（Language） 是字母表上所有可能字符串的某个子集。

示例

• 若 $\Sigma = \{0, 1\}$，可能的字符串包括：$0$, $1$, $01$, $10$, $001$, 等。
• 空字符串 $\epsilon$ 始终是 $\Sigma^*$ 的成员（ $\Sigma^*$ 是所有字符串的集合）。

---

1.2.1 字符串长度的定义

在形式语言与自动机理论中，字符串长度是指字符串中所包含的字符个数。设 $\Sigma$ 是一个字母表（字符的有限集合），一个字符串 $w$ 是由字母表中字符的有限序列。字符串的长度用 $|w|$ 表示，其含义是 $w$ 中字符的个数：

• 空字符串 $\varepsilon$：长度为 $0$，即 $|\varepsilon| = 0$。
• 非空字符串：长度为字符串中所有字符的个数。

例如：

• $w = \text{abc}$，则 $|w| = 3$；
• $w = \varepsilon$，则 $|w| = 0$。

字符串长度 $|w|$ 可以通过递归方式定义如下：

1. 基例（Base case）：
   如果 $w = \varepsilon$（空字符串），那么 $|w| = 0$。

2. 递归关系（Recursive case）：
   如果 $w = xa$，其中 $x \in \Sigma^*$（是字母表 $\Sigma$ 的某个字符串）且 $a \in \Sigma$（是字母表中的一个字符），那么：
   $$
   |w| = |x| + 1
   $$

---

推导过程示例：以字符串 $w = \text{abc}$ 为例，设字母表 $\Sigma = \{a, b, c\}$：

1. $w = \text{abc}$，将其视为 $x = \text{ab}$ 和 $a = \text{c}$，则：
   $$
   |w| = |\text{ab}| + 1
   $$

2. 对 $|\text{ab}|$ 递归分解：
   $$
   |\text{ab}| = |\text{a}| + 1
   $$

3. 对 $|\text{a}|$ 再递归分解：
   $$
   |\text{a}| = |\varepsilon| + 1 = 0 + 1 = 1
   $$

4. 反向合并计算：
   $$
   |\text{ab}| = 1 + 1 = 2
   $$
   $$
   |\text{abc}| = 2 + 1 = 3
   $$

字符串长度的递归定义可以表示为：

$$
|w| =
\begin{cases}
0 & \text{if } w = \varepsilon \\
|x| + 1 & \text{if } w = xa, x \in \Sigma^*, a \in \Sigma
\end{cases}
$$

---

1.2.2 字符串连接的定义

在形式语言与自动机理论中，字符串连接（String Concatenation）是指将两个字符串按顺序组合在一起，形成一个新的字符串。连接操作是形式语言中一个非常重要的基本操作，通常用符号 “$\cdot$” 或直接用空格来表示。

给定两个字符串 $w_1$ 和 $w_2$，它们分别属于字母表 $\Sigma$ 上的语言 $\Sigma^*$，则它们的连接 $w_1 \cdot w_2$（或写作 $w_1 w_2$）是一个新的字符串，表示将 $w_1$ 和 $w_2$ 顺序连接在一起，形成一个新字符串。

形式上，假设：

• $w_1 = x_1 x_2 \dots x_m$，其中 $x_1, x_2, \dots, x_m \in \Sigma$，是一个长度为 $m$ 的字符串；
• $w_2 = y_1 y_2 \dots y_n$，其中 $y_1, y_2, \dots, y_n \in \Sigma$，是一个长度为 $n$ 的字符串。

那么，$w_1 \cdot w_2 = x_1 x_2 \dots x_m y_1 y_2 \dots y_n$，是一个长度为 $m+n$ 的新字符串。

字符串连接操作的基本性质：

1. 结合律（Associativity）： 字符串连接满足结合律，即对于任意三个字符串 $w_1, w_2, w_3 \in \Sigma^*$，都有：
   $$
   (w_1 \cdot w_2) \cdot w_3 = w_1 \cdot (w_2 \cdot w_3)
   $$

2. 单位元（Identity element）： 空字符串 $\varepsilon$ 是连接操作的单位元，即对于任何字符串 $w \in \Sigma^*$，都有：
   $$
   w \cdot \varepsilon = \varepsilon \cdot w = w
   $$

字符串连接示例：假设字母表 $\Sigma = {a, b}$，考虑以下字符串：

• $w_1 = \text{ab}$，
• $w_2 = \text{ba}$。

它们的连接 $w_1 \cdot w_2$ 为：
$$
w_1 \cdot w_2 = \text{ab} \cdot \text{ba} = \text{abba}
$$

---

字符串连接的递归表达式可以通过分段函数的方式来定义。假设 $w_1$ 和 $w_2$ 是两个字符串，递归地定义它们的连接操作 $w_1 \cdot w_2$ 如下：

$$
w_1 \cdot w_2 =
\begin{cases}
w_2, & \text{if } w_1 = \varepsilon \\
x_1 \cdot (x_2 \cdot \dots \cdot (x_m \cdot w_2)), & \text{if } w_1 = x_1 x_2 \dots x_m \text{ and } m > 0
\end{cases}
$$

1. 基例（Base case）： 如果 $w_1 = \varepsilon$（空字符串），则有：
   $$
   \varepsilon \cdot w_2 = w_2
   $$

2. 递归关系（Recursive case）： 如果 $w_1 = x_1 x_2 \dots x_m$，其中 $x_1, x_2, \dots, x_m \in \Sigma$，则递归地将 $w_1$ 分解成 $x_1$ 和剩下的部分 $x_2 \dots x_m$，然后将 $x_1$ 与递归结果 $x_2 \dots x_m \cdot w_2$ 连接：
   $$
   w_1 \cdot w_2 = x_1 \cdot (x_2 \cdot \dots \cdot (x_m \cdot w_2))
   $$

假设我们有两个字符串 $w_1 = \text{abc}$ 和 $w_2 = \text{def}$，我们来逐步推导它们的连接过程。

1. 首先，$w_1 = \text{abc}$，将其分解为 $w_1 = x_1 x_2 x_3$，其中 $x_1 = \text{a}$，$x_2 = \text{b}$，$x_3 = \text{c}$。

2. 根据递归关系：
   $$
   w_1 \cdot w_2 = \text{a} \cdot (\text{b} \cdot (\text{c} \cdot \text{def}))
   $$

   继续递归下去：
   $$
   \text{b} \cdot (\text{c} \cdot \text{def}) = \text{b} \cdot \text{cdef}
   $$

   最终得到：
   $$
   \text{a} \cdot (\text{b} \cdot (\text{c} \cdot \text{def})) = \text{abcdef}
   $$

   因此，$w_1 \cdot w_2 = \text{abcdef}$。

---

1.2.3 字符串幂运算的定义

在形式语言与自动机理论中，字符串的幂运算（String Power）是指将一个字符串自我连接若干次的操作。具体地，对于一个字符串 $w$ 和一个非负整数 $n$，$w^n$ 表示将字符串 $w$ 自我连接 $n$ 次。

定义： 设 $w$ 是一个字符串，$n$ 是一个非负整数。字符串 $w$ 的幂 $w^n$ 的定义如下：

• 基例：当 $n = 0$ 时，$w^0$ 被定义为空字符串 $\varepsilon$：
  $$
  w^0 = \varepsilon
  $$

• 递归关系：当 $n > 0$ 时，$w^n$ 被定义为将字符串 $w$ 连接 $n$ 次，即：
  $$
  w^n = w \cdot w^{n-1} \quad \text{for } n > 0
  $$

  这里，$\cdot$ 表示字符串连接操作。

字符串幂运算的性质：

1. 空字符串的幂：对于任意字符串 $w$，空字符串 $\varepsilon$ 的幂总是为空字符串：
   $$
   \varepsilon^n =
   \begin{cases}
   \varepsilon, & \text{if } n = 0 \\
   \text{undefined}, & \text{if } n > 0
   \end{cases}
   $$

2. 单位元素：对于任意字符串 $w$，有：
   $$
   w^0 = \varepsilon \quad \text{(空字符串)}
   $$
   且对于任意正整数 $n$：
   $$
   w^1 = w
   $$

3. 结合律：字符串幂运算具有结合律。例如，对于任意字符串 $w$ 和非负整数 $n$、$m$，有：
   $$
   w^{n+m} = w^n \cdot w^m
   $$

4. 易错点辨析：对于任意字符串 $w_1$ 和 $w_2$，以及非负整数 $n$，字符串连接的幂运算并不满足分配律。具体地，字符串连接的幂遵循以下规律：
   $$
   (w_1 \cdot w_2)^n = (w_1 w_2) \cdot (w_1 w_2) \cdot \dots \cdot (w_1 w_2) \quad \text{(总共 $n$ 次连接)}
   $$

   而不是将幂分配到每个字符串上：
   $$
   (w_1 \cdot w_2)^n \neq w_1^n \cdot w_2^n
   $$

   这是一个常见的误解。字符串连接的幂是按整体连接的，而不是按每个字符串的幂分别计算。

---

示例： 假设字母表 $\Sigma = {a, b}$，并且考虑字符串 $w = \text{ab}$。

1. 当 $n = 0$ 时：
   $$
   w^0 = \varepsilon
   $$

2. 当 $n = 1$ 时：
   $$
   w^1 = \text{ab}
   $$

3. 当 $n = 2$ 时：
   $$
   w^2 = \text{ab} \cdot \text{ab} = \text{abab}
   $$

4. 当 $n = 3$ 时：
   $$
   w^3 = \text{ab} \cdot \text{abab} = \text{ababab}
   $$

通过这些示例，可以看出字符串的幂运算是将字符串 $w$ 自我连接多次，产生新的更长的字符串。

---

递推关系推导：假设字符串 $w = x_1 x_2 \dots x_m$，其中 $x_1, x_2, \dots, x_m$ 是 $w$ 的各个字符。若 $w^n$ 表示字符串 $w$ 自我连接 $n$ 次，则递归定义如下：

1. 基例： 当 $n = 0$ 时，$w^0 = \varepsilon$。

2. 递归关系： 当 $n > 0$ 时：
   $$
   w^n = w \cdot w^{n-1}
   $$

3. 因此我们可以写出递推表达式：

$$
w=
\begin{cases}
\epsilon,\quad n = 0 \\
w \cdot w^{n-1}, \quad x>0
\end{cases}
$$

---

1.2.4 字符串集合的定义

一个字符串是字母表中字符的有限序列，字符串的集合是字母表中所有可能字符串的集合。例如，字母表 $\Sigma = \{a, b\}$ 中的所有可能的长度为 2 的字符串集合是：

$$
\{aa, ab, ba, bb\}
$$

在形式语言中，我们可以对字符串集合执行运算，常见的操作包括：

1. 串联（Concatenation）：给定两个语言 $L_1$ 和 $L_2$，它们的串联 $L_1 \cdot L_2$ 是所有可能的通过将 $L_1$ 中的元素与 $L_2$ 中的元素连接而成的字符串集合。例如：

   • 若 $L_1 = \{a, b\}$ 和 $L_2 = \{c, d\}$，则：
     $$
     L_1 \cdot L_2 = \{ac, ad, bc, bd\}
     $$

2. 闭包（Kleene Star）：给定一个语言 $L$，它的 Kleene 闭包 $L^*$ 是所有 $L$ 中零个或多个字符串的串联集合，即：
   $$
   L^* = \{\varepsilon\} \cup L \cup L^2 \cup L^3 \cup \dots
   $$
   其中，$\varepsilon$ 表示空字符串，$L^n$ 表示所有长度为 $n$ 的字符串的集合，$n \geq 0$。

   例如，假设 $L = \{a, b\}$，则：
   $$
   L^* = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, aab, \dots \}
   $$

   • 正闭包（Positive Closure）：正闭包 $L^+$ 是由 $L$ 中一个或多个字符串的串联组成的集合。即：
     $$
     L^+ = L \cup L^2 \cup L^3 \cup \dots
     $$
     正闭包可以看作是 Kleene 闭包去除空字符串部分。例如，如果 $L = {a, b}$，则：
     $$
     L^+ = \{a, b, aa, ab, ba, bb, aaa, aab, \dots\}
     $$

3. 并集（Union）：给定两个语言 $L_1$ 和 $L_2$，它们的并集 $L_1 \cup L_2$ 是包含 $L_1$ 和 $L_2$ 中所有字符串的语言集合。例如：

   • 若 $L_1 = \{a, b\}$ 和 $L_2 = \{c, d\}$，则：
     $$
     L_1 \cup L_2 = \{a, b, c, d\}
     $$

4. 差集（Difference）：给定两个语言 $L_1$ 和 $L_2$，它们的差集 $L_1 \setminus L_2$ 是包含所有属于 $L_1$ 但不属于 $L_2$ 的字符串的语言集合。例如：

   • 若 $L_1 = \{a, b, c\}$ 和 $L_2 = \{b, c, d\}$，则：
     $$
     L_1 \setminus L_2 = \{a\}
     $$

5. 集合的 n 次幂运算（n-th Power of a Set）：给定一个语言 $L$ 和一个非负整数 $n$，语言 $L$ 的 n 次幂 $L^n$ 是由 $L$ 中所有长度为 $n$ 的字符串组成的集合。具体定义如下：

   • 当 $n = 0$ 时，$L^0 = \{\varepsilon\}$，即仅包含空字符串。
   • 当 $n > 0$ 时，$L^n$ 包含所有由 $L$ 中的字符串串联组成的长度为 $n$ 的字符串。例如：
     • 若 $L = \{a, b\}$，则：
       • $L^1 = \{a, b\}$
       • $L^2 = \{aa, ab, ba, bb\}$
       • $L^3 = \{aaa, aab, aba, abb, baa, bab, bba, bbb\}$

   通过定义 $L^n$，我们可以理解语言中不同长度的字符串是如何通过多个字符串的串联来生成的。

1.3 语言（Language）

语言（Language）是一个由字母表上的字符串组成的集合，字符串是字母表上符号的有限序列。形式语言通常是根据某种特定的规则或语法定义的字符串集合。形式语言广泛应用于计算机科学中的编程语言设计、编译原理、人工智能、自然语言处理等领域。

给定一个字母表 $\Sigma$，语言 $L$ 是 $\Sigma$ 上所有合法字符串的集合。我们可以使用集合表示语言，记作：
$$
L \subseteq \Sigma^*
$$
其中，$\Sigma^*$ 是字母表 $\Sigma$ 上所有可能的字符串的集合，包括空字符串 $\varepsilon$。

字母表（Alphabet） 是构成语言中所有字符串的基本单位，是一个有限的符号集合，通常用 $\Sigma$ 表示。字母表的元素可以是任何字符、符号或数字。例如：

• 二进制字母表：$\Sigma = \{0, 1\}$
• 字母表：$\Sigma = \{a, b, c, \dots\}$
• 十进制字母表：$\Sigma = \{0, 1, 2, \dots, 9\}$

字符串是由字母表 $\Sigma$ 中的符号按照一定顺序排列组成的有限序列。字符串的长度是有限的，通常用 $w$ 表示一个字符串。常见的符号包括：

• 空字符串 $\varepsilon$，表示一个不含任何符号的字符串。
• 字符串 $w$ 是字母表 $\Sigma$ 中的符号按顺序排列形成的一个有序序列。例如：
  • 如果 $\Sigma = \{a, b\}$，则字符串 $w = \text{ab}$ 是字母表 $\Sigma$ 中字符的一个序列。

字符串的长度是字符串中符号的数量，记作 $|w|$。例如：

• $|\varepsilon| = 0$（空字符串的长度为零）
• $|w| = 3$，如果 $w = \text{abc}$

根据其生成规则或接受条件，语言可以分为以下几类：

1. 正规语言（Regular Language）：正规语言是最简单的一类语言，可以由有限自动机（DFA/NFA）接受或通过正规表达式表示。正规语言可以通过正规文法生成，并且有许多应用，如文本搜索、词法分析等。

   • A language is called a regular language if some infinite automaton recognizes it

2. 上下文无关语言（Context-Free Language）：上下文无关语言是由上下文无关文法（CFG）生成的语言。它们通常可以由推理自动机（如下推自动机）接受，广泛用于编程语言的语法分析。

3. 上下文相关语言（Context-Sensitive Language）：上下文相关语言是由上下文相关文法（CSG）生成的语言，通常由线性有界自动机接受。它们比上下文无关语言更强，但也更复杂。

4. 递归可枚举语言（Recursively Enumerable Language）：递归可枚举语言是可以通过图灵机接受的语言。它们可以包含一些不能有效计算的语言，是计算理论中的最广泛类。

特殊语言类型：

1. 空语言（Empty Language）：空语言是一个不包含任何字符串的集合，记作 $\emptyset$。例如，对于字母表 $\Sigma = \{a, b\}$，如果定义的规则不允许任何字符串出现，那么该语言就是空语言：

   $$
   L = \emptyset
   $$

   这里需要辨析下面的一个结论： $\emptyset$ 不包含任何元素，即：$|\emptyset| = 0$（集合的大小为 0），而 $\{\varepsilon\}$ 包含一个具体的元素（空字符串）。

   $$
   \emptyset \neq \{\varepsilon\}
   $$

2. 全集语言（Universal Language）：全集语言是包含字母表 $\Sigma$ 上所有可能字符串的语言，通常记作 $\Sigma^*$。它包含所有长度为任意数目的字符串，包括空字符串。例如：
   $$
   L = \Sigma^* = \{\varepsilon, a, b, ab, aa, ba, \dots \}
   $$

3. 单一元素语言（Singleton Language）：单一元素语言是只包含一个字符串的语言。例如，若字母表为 $\Sigma = \{a, b\}$，语言 $L = \{ab\}$ 只有一个字符串元素：
   $$
   L = \{ab\}
   $$

语言的运算包括：

1. 串联（Concatenation）：给定两个语言 $L_1$ 和 $L_2$，它们的串联 $L_1 \cdot L_2$ 是所有可能通过将 $L_1$ 中的字符串与 $L_2$ 中的字符串连接起来得到的字符串的集合。

2. 并集（Union）：给定两个语言 $L_1$ 和 $L_2$，它们的并集 $L_1 \cup L_2$ 是包含所有属于 $L_1$ 或 $L_2$ 的字符串的集合。

3. 差集（Difference）：给定两个语言 $L_1$ 和 $L_2$，它们的差集 $L_1 \setminus L_2$ 是包含所有属于 $L_1$ 但不属于 $L_2$ 的字符串的集合。

4. 闭包（Closure）：

   • Kleene 闭包（Kleene Star）：语言 $L$ 的 Kleene 闭包 $L^*$ 是包含所有 $L$ 中零个或多个字符串串联的语言。
   • 正闭包（Positive Closure）：语言 $L$ 的正闭包 $L^+$ 是包含所有 $L$ 中一个或多个字符串串联的语言。

2. Finite Automata

有限自动机 (Finite Automaton, FA) 是一种理论模型，用来描述和识别形式语言中的某些类型的语言。它是自动机理论中的基础之一，广泛应用于计算机科学、编译原理、正则表达式等领域。本章内容我们需要熟悉并且掌握确定性有限自动机（DFA）和非确定性有限自动机 （NFA）

2.1 DFA

确定性有限自动机（DFA，Deterministic Finite Automaton） 是一种计算模型，用于识别正则语言。它由一个有限的状态集合组成，每次在一个特定的输入符号下，从某一状态转换到唯一的另一个状态，因此被称为“确定性”。

DFA 可以通过五元组来定义：

$$
M = (Q, \Sigma, \delta, q_0, F)
$$

其中：

• Q：状态集，表示所有可能的状态。$ Q = \{q_0, q_1, q_2, \dots, q_n\} $ 是有限的。

• Σ：输入字母表，是一个有限的符号集合，表示自动机可以接受的输入字符。通常 $ \Sigma = \{a, b, \dots\} $。

• δ：转移函数，定义了每个状态在给定输入符号时的转移情况。对于任何状态 $ q_i \in Q $ 和输入符号 $ a \in \Sigma $，转移函数 δ 给出了唯一的下一状态 $ q_j \in Q $。即：
  $$
  \delta : Q \times \Sigma \to Q
  $$

• q₀：初始状态，表示自动机开始时所处的状态。它是状态集 $ Q $ 中的一个元素，即 $ q_0 \in Q $。

• F：接受状态集，表示自动机在接受输入并成功识别一个字符串时所处的状态集合。$ F \subseteq Q $，是状态集 $ Q $ 的一个子集。

DFA 是通过一个确定的过程来处理输入字符串的。它从初始状态 $ q_0 $ 开始，逐个读取输入字符串中的符号，并根据当前状态和输入符号，按照转移函数 $ \delta $ 进行状态转移。每次读取一个符号后，自动机都会进入一个新的状态。最终，输入串处理完毕后，如果自动机处于一个接受状态，则该输入字符串被接受；否则，它被拒绝。

DFA有如下性质：

• 确定性：在每个状态下，对于每一个输入符号，DFA都有一个唯一的转移状态。即不存在多个可能的状态转移。
• 有限性：DFA有一个有限的状态集合，因此它只能识别有限的状态。

---

假设我们设计一个DFA来识别所有包含 偶数个0 的二进制字符串。这个语言的正则表达式是 $ (1^\ast 0 1^\ast 0)^\ast $。

• 状态集 $ Q = \{q_0, q_1\} $，其中：

  • $ q_0 $ 表示当前读取的 0 的个数是偶数个（接受状态）。
  • $ q_1 $ 表示当前读取的 0 的个数是奇数个。

• 输入字母表 $ \Sigma = \{0, 1\} $。

• 转移函数 $ \delta $ 可以这样定义：

  • $ \delta(q_0, 0) = q_1 $（如果当前状态是 $ q_0 $，读取到 0 后转到 $ q_1 $）。
  • $ \delta(q_0, 1) = q_0 $（如果当前状态是 $ q_0 $，读取到 1 后保持在 $ q_0 $）。
  • $ \delta(q_1, 0) = q_0 $（如果当前状态是 $ q_1 $，读取到 0 后转到 $ q_0 $）。
  • $ \delta(q_1, 1) = q_1 $（如果当前状态是 $ q_1 $，读取到 1 后保持在 $ q_1 $）。

• 初始状态 $ q_0 $，因为一开始是偶数个 0。

• 接受状态集 $ F = \{q_0\} $，即只有在状态 $ q_0 $ 时，DFA 才接受输入。

DFA的状态转换示意图如下：

我们可以画一个状态转移表：

当前状态	输入符号 = 0	输入符号 = 1
$\text{*}q_0$	$q_1$	$q_0$
$q_1$	$q_0$	$q_1$

• 初始状态：$q_0$
• 接受状态：$q_0$（用 * 表示）

假设输入字符串是 1010，我们来分析 DFA 的运行过程：

• 初始状态 $q_0$。
• 读取第一个字符 ‘1’，根据转移函数 $ \delta(q_0, 1) = q_0 $，仍然处于状态 $q_0$。
• 读取第二个字符 ‘0’，根据转移函数 $ \delta(q_0, 0) = q_1 $，转到状态 $q_1$。
• 读取第三个字符 ‘1’，根据转移函数 $ \delta(q_1, 1) = q_1 $，仍然处于状态 $q_1$。
• 读取第四个字符 ‘0’，根据转移函数 $ \delta(q_1, 0) = q_0 $，转回状态 $q_0$。

最终，自动机处于接受状态 $q_0$，因此输入字符串 “1010” 被接受。

---

2.1.1 DFA的扩展转移函数

在形式语言与自动机理论中，DFA的扩展转移函数（Extended Transition Function）是指在原始转移函数的基础上，对DFA的状态转移进行扩展，使其能够处理整个输入字符串，而不仅仅是单个符号。这个扩展函数通常表示为 $ \delta^* $，它允许我们对一个输入字符串进行逐个字符的状态转移。

扩展转移函数的定义：设定

• $\delta$ 是原始的转移函数，它是一个从状态和输入符号到下一个状态的映射：
  $$
  \delta : Q \times \Sigma \to Q
  $$
  其中，$Q$ 是状态集，$\Sigma$ 是输入字母表。

• 扩展转移函数 $\delta^* : Q \times \Sigma^* \to Q$ ，它扩展了原始转移函数，使其能够接受任意长度的输入串，并返回最终的状态。

形式化地，扩展转移函数定义为：

$$
\delta^*(q, \epsilon) = q
$$

这里，$\epsilon$ 表示空串，表示在没有任何输入时，自动机保持在原状态 $q$。

对于一个非空的输入串 $w = a_1 a_2 \dots a_n \in \Sigma^*$，扩展转移函数满足以下递归关系：

$$
\delta^*(q, a_1 a_2 \dots a_n) = \delta(\delta^*(q, a_1 a_2 \dots a_{n-1}), a_n)
$$

即，扩展转移函数首先对前 $n-1$ 个符号计算转移，并最终得到最后一个符号的转移。

扩展转移函数允许我们一次性地处理整个输入串，而不是每次只处理一个符号。通过使用这个扩展函数，我们可以计算在输入串的每一个字符都被处理后的最终状态。这在计算是否接受某个字符串时非常有用，因为我们只需要检查自动机最终是否处于接受状态。

还是用上面的状态转移图举个例子

当前状态	输入符号 = 0	输入符号 = 1
$\text{*}q_0$	$q_1$	$q_0$
$q_1$	$q_0$	$q_1$

初始状态是 $q_0$，接受状态是 $q_0$。

我们可以使用扩展转移函数来处理整个输入串。假设输入字符串是 $w = 1010$。

1. 计算 $\delta^*(q_0, \epsilon) = q_0$，即没有输入时，自动机仍然处于初始状态 $q_0$。
2. 计算 $\delta^*(q_0, 1) = \delta(q_0, 1) = q_0$，读取第一个字符 ‘1’ 后，仍然处于状态 $q_0$。
3. 计算 $\delta^*(q_0, 10) = \delta(\delta^*(q_0, 1), 0) = \delta(q_0, 0) = q_1$，读取字符 ‘0’ 后，自动机转到状态 $q_1$。
4. 计算 $\delta^*(q_1, 101) = \delta(\delta^*(q_1, 10), 1) = \delta(q_1, 1) = q_1$，读取字符 ‘1’ 后，仍然处于状态 $q_1$。
5. 计算 $\delta^*(q_1, 1010) = \delta(\delta^*(q_1, 101), 0) = \delta(q_1, 0) = q_0$，读取最后一个字符 ‘0’ 后，自动机转回状态 $q_0$。

最终，$\delta^*(q_0, 1010) = q_0$，因为最终状态 $q_0$ 是接受状态，因此输入字符串 1010被接受。

最终总结一下，我们可以得出，DFA的扩展转移函数为：

$$
\delta^*(q, w) =
\begin{cases}
q, & \text{if } w = \epsilon \\
\delta(\delta^*(q, w_1 w_2 \dots w_{n-1}), w_n), & \text{if } w = w_1 w_2 \dots w_n \text{ and } n > 0
\end{cases}
$$

---

2.2 NFA

非确定性有限自动机（NFA，Nondeterministic Finite Automaton） 是另一种计算模型，与DFA类似，NFA也用于识别正则语言。与DFA不同的是，NFA在每个状态下，给定某个输入符号时，可能存在多个不同的转移路径，或者在某些情况下甚至可以不进行任何状态转移。这就是它的“非确定性”特性。

NFA同样可以通过五元组来定义：

$$
M = (Q, \Sigma, \delta, q_0, F)
$$

其中：

• Q：状态集，表示所有可能的状态。$ Q = \{q_0, q_1, q_2, \dots, q_n\} $ 是有限的。

• Σ：输入字母表，是一个有限的符号集合，表示自动机可以接受的输入字符。通常 $\Sigma = \{a, b, \dots\}$。

• δ：转移函数，定义了每个状态在给定输入符号时的转移情况。与DFA不同，NFA的转移函数允许多个可能的下一状态，或者在某些状态下，输入符号可能不产生任何转移（即允许空转移）。因此，转移函数 $\delta$ 是从状态集到状态集的映射：
  $$
  \delta : Q \times \Sigma \to 2^Q
  $$
  其中 $2^Q$ 表示状态集的幂集，表示可能的多个目标状态。

• q₀：初始状态，表示自动机开始时所处的状态。它是状态集 $Q$ 中的一个元素，即 $q_0 \in Q$。

• F：接受状态集，表示自动机在接受输入并成功识别一个字符串时所处的状态集合。$F \subseteq Q$，是状态集 $Q$ 的一个子集。

NFA处理输入字符串的方式与DFA相似，但是在每个步骤中，NFA可以选择不同的状态转移，或者在某些输入符号下可能没有任何状态转移。NFA并不是沿着一个确定的路径处理输入，而是沿着所有可能的路径并行地进行状态转移。最终，NFA接受输入字符串当且仅当存在至少一条路径能够让它停留在接受状态。

NFA与DFA的主要区别：

• 非确定性：在每个状态下，对于每一个输入符号，NFA可以有多个可能的转移状态，或者根本没有转移（空转移）。
• 空转移（ε-转移）：NFA可以有空转移，即在没有任何输入符号的情况下，从一个状态转移到另一个状态。下文会讲解ε-NFA和NFA等价。

---

假设我们设计一个NFA来识别所有包含 至少一个1 的二进制字符串。这个语言的正则表达式是 $(0|1)^* 1(0|1)^*$。

• 状态集 $Q = \{q_0, q_1\}$，其中：

  • $q_0$ 是我们尚未看到任何1的状态
  • $q_1$ 是我们已经至少看到一个1的状态

• 输入字母表 $\Sigma = \{0, 1\}$

• 转移函数 $\delta$ 定义如下：

  • $\delta(q_0, 0) = \{q_0\}$（在初始状态读到0，继续等待1的出现）
  • $\delta(q_0, 1) = \{q_1\}$（在初始状态读到1，转移到接受状态）
  • $\delta(q_1, 0) = \{q_1\}$（已经看到1后，读到0保持在接受状态）
  • $\delta(q_1, 1) = \{q_1\}$（已经看到1后，读到1保持在接受状态）

• 初始状态 $q_0$（自然从未读取到1的状态开始）

• 接受状态集 $F = \{q_1\}$（只要曾经读取到1，就应该接受）

我们可以用状态转移表来更清晰地展示：

当前状态	输入符号 = 0	输入符号 = 1
$q_0$	${q_0}$	${q_1}$
$\text{*}q_1$	${q_1}$	${q_1}$

• 初始状态：$q_0$
• 接受状态：$q_1$（用 * 表示）

让我们分析当输入字符串为 “0110” 时NFA的运行过程：

1. 从初始状态 $q_0$ 开始
2. 读取第一个字符 ‘0’：$\delta(q_0, 0) = \{q_0\}$，保持在状态 $q_0$
3. 读取第二个字符 ‘1’：$\delta(q_0, 1) = \{q_1\}$，转移到状态 $q_1$
4. 读取第三个字符 ‘1’：$\delta(q_1, 1) = \{q_1\}$，保持在状态 $q_1$
5. 读取第四个字符 ‘0’：$\delta(q_1, 0) = \{q_1\}$，保持在状态 $q_1$

由于最终停在接受状态 $q_1$，因此字符串 0110 被接受。这符合我们的预期，因为它确实包含至少一个1（实际上包含两个1）。

---

再来看一个例子。设计接受全部以01结尾的串的NFA。

首先，自动机需要能够识别所有以 01 结尾的字符串，而不关注字符串前面的部分。我们需要理解这个语言接受什么样的字符串：

• “01” 应该被接受
• “101” 应该被接受
• “1101” 应该被接受
• “11101” 应该被接受
• 但 “011” 不应该被接受（因为中间有0）
• “10” 不应该被接受（没有以01结尾）

接下来是我们的解题步骤

1. 定义状态集 Q：

   • 我们需要设计的 NFA 至少有三个状态：
     • $q_0$：初始状态，表示当前没有识别到“01”结尾。
     • $q_1$：表示已经读取了一个 0，即我们已经识别到了 0，等待接收 1 作为结束符。
     • $q_2$：接受状态，表示已经识别到 01 结尾，自动机接受字符串。

2. 定义输入字母表 Σ：

   • 由于字符串只由字符 0 和 1 构成，字母表为：$ \Sigma = \{0, 1\} $。

3. 定义转移函数 δ：

   • $ \delta(q_0, 1) = \{q_0\} $：如果当前状态是 $q_0$，输入 1 后仍然处于 $q_0$，表示读取 1 不影响结尾是否为 01。
   • $ \delta(q_0, 0) = \{q_1\} $：如果当前状态是 $q_0$，输入 0 后转移到 $q_1$，表示遇到了一个 0，准备接受接下来的 1；还有一种情况是当前输入的0并不是倒数第二个字符，因此停留在$q_0$
   • $ \delta(q_1, 1) = \{q_2\} $：如果当前状态是 $q_1$，输入 1 后转移到 $q_2$，表示成功识别到了以 01 结尾；
   • $ \delta(q_1, 0) = \{q_1\} $：如果当前状态是 $q_1$，输入 0 后走到了未定义的状态，因此走到$\emptyset$
   • $ \delta(q_2, 1) = \{q_2\} $：没出现我们定义的状态，走到 $\emptyset$
   • $ \delta(q_2, 0) = \{q_1\} $：没出现我们定义的状态，走到 $\emptyset$

4. 定义初始状态$q_0$ :

   • 初始状态是 $q_0$，表示开始时尚未识别到 01 结尾。

5. 定义接受状态集 F :

   • 接受状态是 $q_2$，表示已经识别到以 01 结尾的字符串。

当前状态	输入符号 = 0	输入符号 = 1
$q_0$	$\{q_0,q_1\}$	$\{q_0\}$
$q_1$	$\emptyset$	$\{q_2\}$
$\text{*}q_2$	$\emptyset$	$\emptyset$

• 初始状态：$q_0$
• 接受状态：$q_2$（用 * 表示）

假设输入字符串是 1101，我们来分析 NFA 的运行过程：

1. 初始状态 $q_0$。
2. 读取第一个字符 ‘1’，根据转移函数 $ \delta(q_0, 1) = \{q_0\} $，保持在状态 $q_0$。
3. 读取第二个字符 ‘1’，根据转移函数 $ \delta(q_0, 1) = \{q_0\} $，保持在状态 $q_0$。
4. 读取第三个字符 ‘0’，根据转移函数 $ \delta(q_0, 0) = \{q_1\} $，转移到状态 $\{q_0,q_1\}$。
5. 读取第四个字符 ‘1’，对于$q_0$，根据转移函数 $ \delta(q_0, 0) = \{q_0,q_1\} $ 。对于$q_1$，$ \delta(q_1, 1) = \{q_2\} $ 。这时候可能出现三种状态，存在一种状态$q_2$能被NFA接受

最终，NFA停在接受状态 $q_2$，因此输入字符串 1101 被接受。

---

2.2.1 NFA的扩展转移函数

在非确定性有限自动机（NFA）中，扩展转移函数是对传统转移函数的扩展。它允许我们从一个状态开始，处理整个输入字符串，而不仅仅是处理单个字符。扩展转移函数定义了 NFA 如何从一个状态开始，读取整个输入字符串后，到达的状态集。

假设我们有一个NFA，定义为 $M = (Q, \Sigma, \delta, q_0, F)$，其中：

• $Q$ 是状态集。
• $\Sigma$ 是输入字母表。
• $\delta$ 是转移函数。
• $q_0$ 是初始状态。
• $F$ 是接受状态集。

扩展转移函数 $ \delta^* $ 是从状态到状态集的映射，定义如下：

$$
\delta^*(q, w) = \delta^*(q, w_1 w_2 \dots w_n)
$$

其中，$w = w_1 w_2 \dots w_n$ 是输入字符串，$w_1, w_2, \dots, w_n$ 是字符串 $w$ 中的各个字符。扩展转移函数遵循以下递归定义：

Step1: 空串的处理

对于空串（即 $w = \epsilon$），扩展转移函数返回包含当前状态的状态集，即：

$$
\delta^*(q, \epsilon) = {q}
$$

这意味着，当输入为空时，NFA 仍然停留在当前状态。

Step2: 递归处理非空字符串

如果输入字符串 $w = w_1 w_2 \dots w_n$ 非空，扩展转移函数 $\delta^*$ 会递归地调用自身来处理子串 $w_1 w_2 \dots w_{n-1}$，然后再根据当前状态和最后一个字符 $w_n$ 进行状态转移。具体的递归形式如下：

$$
\delta^*(q, w) = \bigcup_{r \in \delta(q, w_1)} \delta^*(r, w_2 \dots w_n)
$$

这意味着，对于每个可能的目标状态 $r$（从当前状态 $q$ 通过字符 $w_1$ 转移得到的状态），我们递归地求出从状态 $r$ 开始，处理剩余字符串 $w_2 \dots w_n$ 后的状态集，并将这些状态集进行并集运算。

总结一下，我们可以得出NFA的状态转移函数如下：

$$
\delta^*(q, w) =
\begin{cases}
{q}, & \text{if } w = \epsilon \\
\bigcup_{r \in \delta(q, w_1)} \delta^*(r, w_2 \dots w_n), & \text{if } w = w_1 w_2 \dots w_n \text{ and } n > 0
\end{cases}
$$

---

举个例子: 假设我们有一个简单的 NFA，其中状态集 $Q = \{q_0, q_1\}$，输入字母表 $\Sigma = \{0, 1\}$，转移函数 $\delta$ 如下：

• $ \delta(q_0, 0) = \{q_0, q_1\} $
• $ \delta(q_0, 1) = \{q_0\} $
• $ \delta(q_1, 1) = \{q_0\} $

假设我们要计算 $\delta^*(q_0, 01)$，也就是从状态 $q_0$ 开始，处理字符串 01 后最终到达的状态集。

1. 首先，考虑空串情况：

$$
\delta^*(q_0, \epsilon) = \{q_0\}
$$

2. 然后，处理第一个字符 0：

$$
\delta(q_0, 0) = \{q_0, q_1\}
$$

3. 接着，处理剩余的字符串 1。我们需要从上一步得到的所有状态（即 $q_0$ 和 $q_1$）继续进行状态转移：

   • 对于状态 $q_0$，$ \delta(q_0, 1) = \{q_0\} $。
   • 对于状态 $q_1$，$ \delta(q_1, 1) = \{q_0\} $。

4. 将这两次转移的结果合并：

$$
\delta^*(q_0, 01) = \{q_0\} \cup \{q_0\} = \{q_0\}
$$

因此，从状态 $q_0$ 开始处理字符串 01 后，最终到达的状态是 $q_0$。

总结一下NFA的扩展函数有如下特点：

• 空串的扩展转移函数 $\delta^*(q, \epsilon)$ 使得当前状态保持不变。
• 递归计算扩展转移函数是通过逐步处理输入字符串，并根据每个字符的转移结果来更新状态集。
• 扩展转移函数允许我们处理整个字符串的转移，而不仅仅是一个字符，这对 NFA 的运行至关重要，因为 NFA 可以在多个状态间“并行”进行状态转移。

---

2.2.2 $\epsilon$-NFA

$\epsilon$-NFA（Epsilon-Non-deterministic Finite Automaton） 是一种特殊的非确定性有限自动机（NFA）。与普通的 NFA 相比，$\epsilon$-NFA 允许使用 $\epsilon$ 转移（即空转移）。$\epsilon$ 转移意味着在没有读取任何输入字符的情况下，自动机可以从一个状态跳转到另一个状态。

一个 $\epsilon$-NFA 通常用以下五元组表示：

$$
M = (Q, \Sigma, \delta, q_0, F)
$$

其中：

• $Q$：状态集（有限集合）。
• $\Sigma$：输入字母表（有限集合）。
• $\delta$：状态转移函数，$\delta: Q \times (\Sigma \cup {\epsilon}) \to 2^Q$。注意，这里 $\delta$ 可以包含 $\epsilon$ 转移。
• $q_0$：初始状态，$q_0 \in Q$。
• $F$：接受状态集，$F \subseteq Q$。

$\epsilon$-NFA 具有以下特性：

1. $\epsilon$ 转移：

   • 自动机可以通过 $\epsilon$ 转移从一个状态跳转到另一个状态，而无需消耗任何输入字符。
   • 例如，如果 $\delta(q_1, \epsilon) = \{q_2, q_3\}$，自动机可以从状态 $q_1$ 转移到 $q_2$ 或 $q_3$，而不需要读取输入字符。

2. 非确定性：

   • 和普通 NFA 一样，$\epsilon$-NFA 也具有非确定性：对于相同的输入字符，自动机可能有多个可能的转移路径。

3. 接受条件：

   • 一个字符串 $w$ 被 $\epsilon$-NFA 接受，当且仅当：
     • 从初始状态 $q_0$ 开始，沿着可能的路径（包括 $\epsilon$ 转移），读取完字符串 $w$ 后，最终能到达某个接受状态 $f \in F$。

$\epsilon$ 闭包是 $\epsilon$-NFA 的一个关键概念。它描述了从某个状态 $q$ 开始，通过任意多次 $\epsilon$ 转移可以到达的状态集合。

记 $\epsilon$ 闭包为 $\text{E-closure}(q)$，定义如下：

$$
\text{E-closure}(q) = \{ p \in Q \mid p \text{ 是从 } q \text{ 经 $\epsilon$ 转移可到达的状态} \}
$$

如果从状态 $q$ 开始经过若干次 $\epsilon$ 转移可以到达状态 $p$，则 $p \in \text{E-closure}(q)$。

---

考虑一个简单的 $\epsilon$-NFA，定义如下：

• 状态集：$Q = \{q_0, q_1, q_2\}$。
• 输入字母表：$\Sigma = \{a, b\}$。
• 初始状态：$q_0$。
• 接受状态集：$F = \{q_2\}$。
• 转移函数 $\delta$：
  • $\delta(q_0, \epsilon) = \{q_1\}$。
  • $\delta(q_1, a) = \{q_1, q_2\}$。
  • $\delta(q_2, b) = \{q_2\}$。

我们可以用状态转移图表示这个 $\epsilon$-NFA：

$\epsilon$ 闭包计算

• $\text{E-closure}(q_0) = \{q_0, q_1\}$ （$q_1$ 是通过 $\epsilon$ 转移从 $q_0$ 可达）。
• $\text{E-closure}(q_1) = \{q_1\}$。
• $\text{E-closure}(q_2) = \{q_2\}$。

假设输入字符串是 “a”，分析其是否被接受：

1. 初始状态 $q_0$，根据 $\epsilon$ 闭包，$\text{E-closure}(q_0) = \{q_0, q_1\}$。
2. 读取第一个字符 “a”：
   • 从 $q_1$ 读取 “a” 后，可以到达状态 $q_1$ 和 $q_2$。
   • 从 $q_0$ 无法直接读取 “a”。
3. 计算 $\epsilon$ 闭包：
   • $\text{E-closure}(\{q_1, q_2\}) = \{q_1, q_2\}$。
4. 最终状态集包含 $q_2$，它是一个接受状态。

因此，字符串 “a” 被该 $\epsilon$-NFA 接受。

上面的$\epsilon$-NFA接受的语言是以一个或多个 ‘a’ 结束，并且可以在后面跟上零个或多个 ‘b’。即正则表达式为 $a^+ b^*$。

---

2.2.3 $\epsilon$-NFA的扩展转移函数

一个非确定性有限自动机（NFA）由五元组 $(Q, \Sigma, \delta, q_0, F)$ 组成，其中：

• $Q$ 是状态集，
• $\Sigma$ 是输入字母表，
• $\delta: Q \times \Sigma \to \mathcal{P}(Q)$ 是转移函数（映射一个状态和输入符号到可能的状态集合），
• $q_0 \in Q$ 是初始状态，
• $F \subseteq Q$ 是接受状态集。

在 $\epsilon$-NFA 中，除了常规的转移外，还允许存在 $\epsilon$（空字符串）转移，意味着自动机可以在没有任何输入的情况下从一个状态转移到另一个状态。

$\epsilon$-NFA的扩展转移函数 $\delta^*(q, w)$ 用于计算从状态 $q$ 开始，处理输入字符串 $w$ 后可能到达的所有状态。这个函数需要分别考虑两种情况：当输入字符串为空（$w = \epsilon$）时，以及输入字符串非空（$w \neq \epsilon$）时。可以定义为如下的分段函数：

$$
\delta^*(q, w) =
\begin{cases}
E\text{-closure}(q), & \text{if } w = \epsilon \\
\bigcup_{q’ \in \delta(q, a)} \delta^*(q’, w’), & \text{if } w = a w’ \text{ and } a \in \Sigma
\end{cases}
$$

其中：

• 如果 $w = \epsilon$，表示输入字符串为空，那么扩展转移函数的值是从状态 $q$ 开始，所有通过 $\epsilon$ 转移能够到达的状态集合，即 $E$-closure($q$)。
• 如果 $w = a w’$，表示输入字符串非空，且可以分解为第一个符号 $a$ 和剩余部分 $w’$，那么扩展转移函数的值是所有从状态 $q$ 通过符号 $a$ 转移后，再继续处理 $w’$ 后可能到达的状态的集合。这些状态是通过递归计算 $\delta^*(q’, w’)$ 来得到的，其中 $q’$ 是状态 $q$ 经过符号 $a$ 转移后到达的状态。

假设有一个简单的 $\epsilon$-NFA，其状态集为 $Q = \{q_0, q_1, q_2\}$，字母表为 $\Sigma = \{a, b\}$，初始状态为 $q_0$，接受状态为 $F = \{q_1\}$，且转移函数如下：

• $\delta(q_0, a) = \{q_1\}$
• $\delta(q_1, b) = \{q_2\}$
• $\delta(q_0, \epsilon) = \{q_2\}$

则其空转移闭包为：

$$
E\text{-closure}(q_0) = \{q_0, q_2\}
$$

扩展转移函数计算为：

• 对于输入字符串 $a$，从状态 $q_0$ 开始，$E$-closure 包含 $q_0$ 和 $q_2$，因此扩展转移将考虑状态 $q_0$ 和 $q_2$ 的转移。
  • 从 $q_0$，转移到 $q_1$。
  • 从 $q_2$，没有输入符号 $a$ 的转移。

所以，扩展转移函数为：

$$
\delta^*(q_0, a) = \{q_1, q_2\}
$$

• 对于输入字符串 $ab$，我们首先从状态 $q_0$ 处理 $a$，然后再从 $q_1$ 处理 $b$。
  • 从 $q_0$ 处理 $a$ 后，到达状态 $q_1$。
  • 从 $q_1$ 处理 $b$ 后，到达状态 $q_2$。

所以，扩展转移函数为：

$$
\delta^*(q_0, ab) = \{q_2\}
$$

---

2.2.4 $\epsilon$-NFA与NFA等价性证明

为了证明 $\epsilon$-NFA 和 NFA 之间的等价性，即任何一个 $\epsilon$-NFA 都可以转换为一个等价的 NFA，我们将使用数学归纳法来推导和证明。

定义：

• $\epsilon$-NFA（Epsilon-Non-deterministic Finite Automaton）：与普通的 NFA 不同，$\epsilon$-NFA 允许在没有消耗任何输入字符的情况下，通过 $\epsilon$ 转移从一个状态跳转到另一个状态。
• NFA（Non-deterministic Finite Automaton）：普通的非确定性有限自动机，在每个状态下对每个输入符号至多有一个转移。

证明目标： 对于每个 $\epsilon$-NFA，存在一个等价的 NFA，可以接受相同的语言。

证明思路： 我们将采用归纳法来证明，即：任何 $\epsilon$-NFA 都可以通过一个构造转换为一个等价的 NFA。

Step 1：基础情况

假设我们有一个最简单的 $\epsilon$-NFA，它没有任何 $\epsilon$ 转移。即这个 $\epsilon$-NFA 实际上是一个普通的 NFA，因此显然是等价的。

• $\epsilon$-NFA 就是一个普通的 NFA。
• 因此，这种情况我们已经证明了等价性。

Step 2：归纳假设

假设对于所有状态数目小于 $n$ 的 $\epsilon$-NFA，我们已经证明它们与相应的 NFA 等价。即：对所有状态数目小于 $n$ 的 $\epsilon$-NFA，我们都能构造一个等价的 NFA。

Step 3：归纳步骤

现在考虑一个有 $n$ 个状态的 $\epsilon$-NFA。我们需要通过构造一个 NFA 来证明它与 NFA 等价。

假设我们的 $\epsilon$-NFA 定义为：

$$
M = (Q, \Sigma, \delta, q_0, F)
$$

其中：

• $Q = \{q_0, q_1, q_2, \dots, q_{n-1}\}$ 是状态集。
• $\Sigma$ 是输入字母表。
• $\delta$ 是转移函数，$\delta: Q \times (\Sigma \cup {\epsilon}) \to 2^Q$，表示从状态到状态的转移。
• $q_0$ 是初始状态。
• $F \subseteq Q$ 是接受状态集。

我们的任务是构造一个等价的 NFA，用来接受相同的语言。

---

构造过程:

1. 扩展状态集：

   • 对于给定的 $\epsilon$-NFA，我们构造一个新的 NFA，将其状态集 $Q$ 扩展为 $\tilde{Q}$，其中 $\tilde{Q}$ 表示每个状态的 $\epsilon$ 闭包。也就是说，$\tilde{Q}$ 中的每个元素是 $\epsilon$ 闭包 集合，表示从原状态集的每个状态出发，经过若干个 $\epsilon$ 转移后可能到达的所有状态。

2. 定义新的转移函数：

   • 对于每一个 $\tilde{q} \in \tilde{Q}$ 和输入符号 $a \in \Sigma$，新的转移函数 $\tilde{\delta}$ 将定义为：
     $$
     \tilde{\delta}(\tilde{q}, a) = \bigcup_{q \in \tilde{q}} \delta(q, a)
     $$
     其中 $\tilde{q}$ 是一个 $\epsilon$ 闭包 集合，而 $\delta(q, a)$ 是普通的 NFA 转移。
   • 注意，$\tilde{q}$ 代表的是从状态集合中通过 $\epsilon$ 转移到达的所有状态，因此 $\tilde{\delta}(\tilde{q}, a)$ 是所有从该集合内的状态通过输入字符 $a$ 能到达的状态的并集。

3. 定义初始状态和接受状态：

   • 新的初始状态是 $\tilde{q_0} = \text{E-closure}(q_0)$，即初始状态 $q_0$ 经过 $\epsilon$ 闭包后到达的状态集合。
   • 接受状态集 $F’ = \{\tilde{q} \mid \tilde{q} \cap F \neq \emptyset\}$，即任何包含原接受状态 $F$ 中某个状态的状态集合都作为新的接受状态。

---

证明等价性

我们要证明，通过上述构造的 NFA 能够接受与原 $\epsilon$-NFA 相同的语言。我们使用归纳法步骤中的假设和构造的转换来证明这一点。

1. $\epsilon$ 闭包和转移函数：

   • 在 $\epsilon$-NFA 中，任何通过 $\epsilon$ 转移到达的状态都能被纳入 NFA 的转移函数中。由于 $\epsilon$ 转移没有消耗输入字符，因此 NFA 的转移函数扩展了对 $\epsilon$ 转移的处理。
   • 每个 $\epsilon$-NFA 的 $\epsilon$ 闭包都被映射为 NFA 的状态集合，而输入字符会在这个集合内传播。

2. 接受条件：

   • NFA 通过判断是否可以到达一个包含原接受状态的集合来确定是否接受字符串。这与 $\epsilon$-NFA 的接受条件一致，即只要从初始状态出发经过输入串到达某个接受状态，就被接受。

3. 语言相等性：

   • 由于 $\epsilon$-NFA 的每一步转移都在 NFA 中得到了精确的映射，并且接受状态的条件也被正确保留，因此构造的 NFA 接受的语言与原 $\epsilon$-NFA 接受的语言是相同的。

通过以上构造和证明，我们可以得出结论：任何一个 $\epsilon$-NFA 都可以转换为一个等价的 NFA，即 $\epsilon$-NFA$ \equiv$ NFA。

此后不再明确区分$\epsilon$-NFA和NFA，因为它们都是NFA

---

2.3 DFA和NFA等价性证明

在形式语言与自动机理论中，确定性有限自动机（DFA）和非确定性有限自动机（NFA）是两种常见的自动机模型。它们用于识别正则语言，并且DFA 和 NFA 是等价的，即它们识别的语言是完全一样的。具体来说，任何一个 NFA 都可以转换成一个等价的 DFA，反之亦然。以下是 DFA 和 NFA 等价性的证明过程。

DFA 是一个五元组 $(Q, \Sigma, \delta, q_0, F)$，其中：

• $Q$ 是有限状态集。
• $\Sigma$ 是输入字母表。
• $\delta: Q \times \Sigma \to Q$ 是状态转移函数，给定当前状态和输入符号，确定唯一的下一个状态。
• $q_0 \in Q$ 是初始状态。
• $F \subseteq Q$ 是接受状态集。

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

• $Q$ 是有限状态集。
• $\Sigma$ 是输入字母表。
• $\delta: Q \times \Sigma \to \mathcal{P}(Q)$ 是状态转移函数，给定当前状态和输入符号，可以转移到多个状态（即可以是空的或多个状态的集合）。
• $q_0 \in Q$ 是初始状态。
• $F \subseteq Q$ 是接受状态集。

我们要证明的是，每个 NFA 都可以转化为一个等价的 DFA。为此，我们将通过构造来展示如何从 NFA 构造 DFA，使得它们识别的语言是一样的。

分析：从 NFA 转换到 DFA

假设有一个 NFA $N = (Q, \Sigma, \delta, q_0, F)$，我们想构造一个等价的 DFA $D = (Q’, \Sigma, \delta’, q_0’, F’)$。

1. 状态集：DFA 的状态集 $Q’$ 由 NFA 的状态集的子集组成。更具体地，DFA 的状态对应于 NFA 的状态集合的一个子集。即 $Q’ \subseteq 2^Q$（所有 NFA 状态的集合的幂集）。

2. 初始状态：DFA 的初始状态 $q_0’$ 是 NFA 初始状态的 $\epsilon$-闭包。记 $E\text{-closure}(q_0)$ 为 NFA 状态 $q_0$ 的空转移闭包。于是，DFA 的初始状态是 $q_0’ = E\text{-closure}(q_0)$。

3. 转移函数：对于 DFA 中的每个状态（它是 NFA 状态的一个子集），DFA 的转移函数 $\delta’(S, a)$ 被定义为所有 NFA 状态在读取符号 $a$ 后所能到达的状态的 $\epsilon$-闭包：

   $$ \delta’(S, a) = E\text{-closure} \left( \bigcup_{q \in S} \delta(q, a) \right) $$

   也就是说，DFA 的转移函数是 NFA 中所有可能的状态集合的组合。

4. 接受状态集：DFA 的接受状态集 $F’$ 由 NFA 中的所有包含接受状态的状态集合组成。即：

   $$ F’ = \{ S \subseteq Q \mid S \cap F \neq \emptyset \} $$

   也就是说，DFA 中只要某个状态子集包含 NFA 的某个接受状态，它就被认为是接受状态。

证明：

为了证明从 NFA 到 DFA 的转换是有效的，即两者识别的语言是一样的，我们可以分为以下几步：

1. 从 NFA 接受的语言到 DFA：

   • NFA 对输入字符串 $w$ 执行多个路径，并在路径中存在至少一条接受状态时就接受字符串。
   • 对于 DFA，它基于一个状态子集来模拟所有这些路径。由于每个状态子集都包括了 NFA 的多个状态，DFA 必定能够找到 NFA 中的一个路径来接受字符串。

   因此，如果一个字符串被 NFA 接受，它也会被通过构造的 DFA 接受。

2. 从 DFA 接受的语言到 NFA：

   • DFA 在每一步都有唯一的转移，因此它只能遵循一个路径。这个路径可以直接对应于 NFA 的多个可能路径。
   • 因此，如果 DFA 接受一个字符串，那么这个字符串也会被 NFA 接受（尽管 NFA 可能有多个路径，但至少有一条与 DFA 的唯一路径相同）。

由于这两个方向的转换都成立，因此 DFA 和 NFA 是等价的。

假设我们有一个简单的 NFA，其状态集为 $Q = \{q_0, q_1\}$，字母表为 $\Sigma = \{a, b\}$，初始状态为 $q_0$，接受状态为 $F = \{q_1\}$，转移函数如下：

• $\delta(q_0, a) = \{q_0, q_1\}$
• $\delta(q_0, b) = \{q_0\}$
• $\delta(q_1, a) = \{q_1\}$
• $\delta(q_1, b) = \{q_1\}$

可以看到，NFA 在状态 $q_0$ 时，对于输入 $a$ 可以转移到 $q_0$ 或 $q_1$。我们可以按照上述方法将此 NFA 转换为一个等价的 DFA。

这里我们简单总结一下：

• DFA 和 NFA 是等价的，它们可以识别相同的正则语言。
• NFA 到 DFA 的转换是通过将 NFA 状态的所有子集映射到 DFA 状态的过程来实现的。
• 从 NFA 到 DFA 的转换能够保留语言不变，并且可以通过递归地计算状态的 $\epsilon$-闭包和转移来实现。

这个等价性证明展示了尽管 DFA 和 NFA 在结构上有所不同，但它们的能力是等同的，都能够识别正则语言(Regular Language)。

---

2.4 State Elimination Method

状态消除法（State Elimination Method） 是一种常用于将有限状态机（Finite State Machine, FSM）或确定性有限自动机（Deterministic Finite Automaton, DFA）转换为正则表达式的技术。在形式语言与自动机的学习中，这一方法是将有限状态机的转移图简化为一个相应的正则表达式的有效工具。

基本步骤

1. 构造状态转移图：
   开始时，首先需要有一个确定的有限状态机（DFA）或者非确定的有限状态机（NFA），其状态转移图应包括：

   • 各状态
   • 状态之间的转移（可能是输入字符）
   • 初态与终态的标定

2. 从图中删除状态：
   在每一步中，选择一个非终态进行删除。删除一个状态时，需考虑：

   • 状态间的所有可能的转移路径。
   • 通过删除该状态，可能会导致一些新路径的产生。

3. 更新转移关系：
   删除某一状态后，所有从该状态出发的转移关系必须通过其它状态来代替。具体地：

   • 如果有从状态 A 到状态 B 的路径 a 和从状态 B 到状态 C 的路径 b，那么删除状态 B 后，可以通过路径 a 和 b 连接成新的路径 ab。
   • 对于状态 B 本身的自环路径（比如 B 到 B 的路径），要通过循环自环的组合形成新的路径。

4. 重复删除直到只剩下起始状态和终止状态：
   继续删除其他非终态，逐步简化自动机的结构，直到只剩下一个起始状态和一个或多个终止状态。这时可以从起始状态到终止状态的路径表示为一个正则表达式。

5. 得到正则表达式：
   一旦删除所有状态，只剩下两个状态（起始状态和终止状态），从起始状态到终止状态的所有路径就是自动机的正则表达式。

3. Regular Language

正则语言 (Regular Language) 是形式语言理论中的一个重要概念，通常与有限自动机（Finite Automata, FA）和正则表达式（Regular Expressions, RE）相关联。正则语言是可以被有限自动机识别或由正则表达式描述的语言。它们的特点是相对简单，能够用有限的计算资源进行识别或生成。

形式化地，正则语言是一个语言集合，满足以下条件之一：

• 它可以被一个有限自动机识别。
• 它可以通过正则表达式来描述。
• 它可以通过正则文法生成。

这些语言可以被归类为正规语言，它们的生成和识别过程是有限的，不需要无限的计算资源。

正则语言可以通过 DFA 或 NFA 来识别。尽管 DFA 和 NFA 之间在形式上有所不同，实际上它们是等价的，因为每一个 NFA 都可以被转换成一个等效的 DFA。

有限自动机与正则表达式的等价性证明留到后面

有限自动机 (Finite Automaton) 是一种计算模型，它由一组状态、一个输入字母表、一个转换函数、一个初始状态和一些接受状态组成。有限自动机有两种类型：

• 确定性有限自动机 (DFA) ：对于每个状态和输入符号，都有唯一的转移。
• 非确定性有限自动机 (NFA) ：对于某些状态和输入符号，可能有多个转移或者没有转移。

正则语言具有一些有用的性质，包括：

• 闭包性质：正则语言在以下操作下保持闭合，即操作结果仍然是正则语言。

  • 并运算：如果 $L_1$ 和 $L_2$ 是正则语言，则 $L_1 \cup L_2$ 也是正则语言。
  • 连接运算：如果 $L_1$ 和 $L_2$ 是正则语言，则 $L_1 \cdot L_2$ 也是正则语言。
  • 星号闭包（Kleene闭包）：如果 $L$ 是正则语言，则 $L^*$ 也是正则语言。
  • 补运算：正则语言对于补集操作是封闭的，假设 $L$ 是正则语言，则 $\overline{L}$ 也是正则语言。

• 可表示性：正则语言可以用正则表达式来描述。每个正则表达式都定义了一个正则语言。

后面内容对这里的正确性进行证明

尽管正则语言非常有用，它们也有一些限制：

• 正则语言无法描述上下文相关语言或上下文无关语言中一些更复杂的结构。例如，正则语言不能识别平衡的括号或相互嵌套的结构。
• 正则语言只能识别相对简单的模式（如重复模式、选择模式），对于更复杂的结构，它们的表达能力有限。

正则语言和正则表达式在计算机科学中有广泛应用，尤其是在文本处理领域，如：

• 文本搜索：正则表达式广泛用于字符串匹配和文本搜索。
• 编译器设计：在编译器中，正则语言用于词法分析阶段，识别输入的词法单位（如关键字、标识符、操作符等）。
• 数据验证：在输入数据验证中，正则表达式被用于检查输入是否符合特定模式（如电子邮件地址、电话号码等）。

---

1. 正则语言的简单示例：

   • 语言 $L = {a, b}$，即由字符 ‘a’ 或 ‘b’ 组成的语言，可以由正则表达式 $a|b$ 来表示。

2. 使用 Kleene 星号操作：

   • 语言 $L = {a^n \mid n \geq 0}$，即包含任意数量的字符 ‘a’ 的语言，可以用正则表达式 $a^*$ 来表示。

3. 连接操作：

   • 语言 $L = {ab, abc}$，即包含字符串 ‘ab’ 和 ‘abc’ 的语言，可以通过正则表达式 $ab|abc$ 来表示。

---

3.1 Regular Expression

正则表达式 (Regular Expression, RE) 是一种用于描述字符串模式的形式化语言，广泛应用于文本搜索、数据匹配、编译器的词法分析等领域。在形式语言与自动机的理论中，正则表达式用于定义正则语言，它们能够描述可以被有限自动机识别的语言。

正则表达式是一种通过特定规则组合字母、符号和运算符来表示字符串集合的工具。它由字母表（通常为有限的字符集）中的符号以及以下几种运算符组合而成：

• 字面量字符：如字符 a、b、1 等，它们直接表示一个特定的字符。
• 连接 (Concatenation) ：将两个正则表达式拼接在一起，表示这两个模式依次出现。例如，ab 表示第一个字符是 a，第二个字符是 b。(也可以用·来表示)
• 并运算 (Union) ：表示选择操作，表示两个模式的并集。用竖线 | 表示，如 a|b 表示匹配 a 或 b。（也可以用+来表示并运算）
• Kleene 星号 (Kleene Star) ：表示零次或多次重复某个模式。用星号 * 表示，如 a* 表示匹配零次或多次字符 a。
• 括号 (Parentheses) ：用于分组操作，将多个元素或子表达式组合成一个单位。例如，(ab)* 表示零次或多次重复 ab。
• 字符集 (Character Class) ：用于匹配一组字符中的任意一个。用方括号 [] 表示，如 [a-z] 表示匹配小写字母中的任何一个。
• 取反 (Negation) ：表示匹配不在指定字符集中的字符。用 ^ 在字符集的开头表示，如 [^0-9] 表示匹配任意非数字字符。

---

下面列举一些简单的例子：

1. 匹配一个单一字符：

   • a：匹配字符 a。

2. 匹配字符的选择：

   • a|b：匹配字符 a 或字符 b。

3. 匹配多个字符：

   • abc：匹配字符串 abc。

4. 匹配字符重复：

   • a*：匹配零次或多次字符 a，即可以匹配空字符串、a、aa、aaa 等。
   • (ab)*：匹配零次或多次 ab，即可以匹配空字符串、ab、abab 等。

5. 匹配字符集合：

   • [0-9]：匹配任意一个数字字符。
   • [a-zA-Z]：匹配任意一个英文字母（不区分大小写）。

6. 匹配任意字符：

   • .：表示匹配任意单个字符（除了换行符）。

---

正则表达式广泛应用于多个领域，主要包括：

• 文本搜索与替换：可以在文本中查找匹配特定模式的字符串，或对匹配的部分进行替换。
• 数据验证：验证用户输入是否符合特定模式，如电子邮件、电话号码等。
• 编译器与解释器：在编译器的词法分析阶段，正则表达式用于识别源代码中的词法单元（tokens），如关键字、标识符、常数等。
• 日志分析与处理：从大量的日志文件中提取出符合特定模式的数据，进行后续分析。

尽管正则表达式非常强大，但它也有一些限制，主要体现在以下方面：

• 正则表达式无法处理上下文依赖的结构，比如匹配平衡的括号或递归模式。
• 对于复杂的语言结构，正则表达式的表达能力是有限的。对于需要更复杂模式匹配的任务，可能需要更高级的解析技术，如上下文无关文法或上下文相关文法。

这里就引入了后面章节的下推自动机和上下文无关文法

---

正则表达式中的运算符有一定的优先级，决定了它们在表达式中组合的顺序。理解这些优先级对于正确解析和构建正则表达式至关重要。

运算优先级总结：

1. () ：分组，最高优先级。
2. 量词 *, +, ?, {n,m} ：应用于前面的字符或表达式。
3. [] 和 [^] ：字符集和取反。
4. | ：选择，最低优先级。

示例：

• a(b|c)*d ：匹配 a 后跟 b 或 c 任意次（包括零次）再跟 d。这里，(b|c) 优先于 *。
• a|b* ：先匹配 b*，然后匹配 a，因为 * 的优先级高于 |。

修考题目中会有许多正则表达式的考点，我就放在修考真题里来讲解吧…

---

3.2 有限自动机与正则表达式的等价性证明

第一部分：基本定义

一个确定性有限自动机(DFA) $M$ 是一个五元组 $M = (Q, \Sigma, \delta, q_0, F)$，其中：

• $Q$ 是有限的状态集
• $\Sigma$ 是有限的输入字母表
• $\delta: Q \times \Sigma \rightarrow Q$ 是转移函数
• $q_0 \in Q$ 是初始状态
• $F \subseteq Q$ 是接受状态集合

一个非确定性有限自动机(NFA) $M$ 是一个五元组 $M = (Q, \Sigma, \delta, q_0, F)$，其中：

• $\delta: Q \times (\Sigma \cup {\varepsilon}) \rightarrow \mathcal{P}(Q)$ 是转移函数，$\mathcal{P}(Q)$表示$Q$的幂集
• 其他组件与DFA定义相同

正则表达式归纳定义如下：

1. $\emptyset$ 是正则表达式
2. $\varepsilon$ 是正则表达式
3. 对于任何 $a \in \Sigma$，$a$ 是正则表达式
4. 如果 $r$ 和 $s$ 是正则表达式，则：
   • $(r \cdot s)$ 是正则表达式（连接）
   • $(r|s)$ 是正则表达式（选择）
   • $(r*)$ 是正则表达式（Kleene闭包）

正则表达式表示的语言: $L(r)$ 表示正则表达式 $r$ 表示的语言，归纳定义如下：

1. $L(\emptyset) = \emptyset$
2. $L(\varepsilon) = \{\varepsilon\}$
3. $L(a) = \{a\}$, $a \in \Sigma$
4. $L(r \cdot s) = L(r) \cdot L(s)$
5. $L(r|s) = L(r) \cup L(s)$
6. $L(r^*) = L(r)* = \bigcup_{i \geq 0} L(r)^i$

第二部分：正则表达式到有限自动机的转换

定理:Thompson构造:

• 对于任意正则表达式 $r$，存在一个接受 $L(r)$ 的$\varepsilon$-NFA。

我们用结构归纳法证明。

基础情况：

1. $r = \emptyset$：
   构造 $M = (\{q_0\}, \Sigma, \delta, q_0, \emptyset)$，其中$\delta$为空函数

2. $r = \varepsilon$：
   构造 $M = (\{q_0\}, \Sigma, \delta, q_0, \{q_0\})$，其中$\delta$为空函数

3. $r = a$，$a \in \Sigma$：
   构造 $M = (\{q_0, q_1\}, \Sigma, \delta, q_0, \{q_1\})$，其中
   $\delta(q_0, a) = \{q_1\}$

归纳步骤：
假设对于正则表达式 $r_1$ 和 $r_2$，已经构造出接受 $L(r_1)$ 和 $L(r_2)$ 的NFA $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ 和 $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$。

1. 连接 $r = r_1 \cdot r_2$：
   构造 $M = (Q_1 \cup Q_2, \Sigma, \delta, s_1, F_2)$，其中

   • $\delta(q, a) = \delta_1(q, a)$ 对于 $q \in Q_1, a \in \Sigma$
   • $\delta(q, a) = \delta_2(q, a)$ 对于 $q \in Q_2, a \in \Sigma$
   • $\delta(f, \varepsilon) = {s_2}$ 对于所有 $f \in F_1$

2. 选择 $r = r_1|r_2$：
   构造 $M = (Q_1 \cup Q_2 \cup \{q_0\}, \Sigma, \delta, q_0, F_1 \cup F_2)$，其中

   • $\delta(q_0, \varepsilon) = {s_1, s_2}$
   • 其他转移同上

3. Kleene闭包 $r = r_1*$：
   构造 $M = (Q_1 \cup \{q_0\}, \Sigma, \delta, q_0, \{q_0\} \cup F_1)$，其中

   • $\delta(q_0, \varepsilon) = \{s_1\}$
   • $\delta(f, \varepsilon) = \{s_1, q_0\}$ 对于所有 $f \in F_1$

第三部分：有限自动机到正则表达式的转换

广义化的Kleene定理: 对于任意NFA $M$，存在一个正则表达式 $r$，使得 $L(M) = L(r)$。

证明：

给定NFA $M = (Q, \Sigma, \delta, q_0, F)$，令 $Q = \{1, 2, …, n\}$。

1. 定义生成式 $R_{ij}^k$，表示从状态$i$到状态$j$的路径，其中中间状态编号不超过$k$。

2. 基础情况 $(k = 0)$：$R_{ij}^0 = \{a | j \in \delta(i, a)\} \cup \{\varepsilon | i = j\}$

3. 归纳步骤：$R_{ij}^k = R_{ij}^{k-1} \cup R_{ik}^{k-1}(R_{kk}^{k-1})^*R_{kj}^{k-1}$

4. 最终表达式：$r = \bigcup\{R_{0j}^n | j \in F\}$

第四部分：等价性证明的完成

Kleene定理: 一个语言是正则的，当且仅当它能被某个有限自动机识别。

The language is regular if and only if it can be recognized by some finite automaton.

证明：

1. $(\Rightarrow)$ 由定理2.1，每个正则表达式都可以转换为等价的NFA
2. $(\Leftarrow)$ 由定理3.1，每个NFA都可以转换为等价的正则表达式

补充定理：对于任意正则表达式 $r$，如果 $M$ 是通过Thompson构造得到的NFA，那么：
$L(M) = L(r)$

证明： 用归纳法证明，对应每个构造步骤，证明：
$w \in L(r) \Leftrightarrow w \in L(M)$

这里的等价性证明非常繁琐…我们只需要知道有限自动机和正则表达式在表示语言的能力上等价即可。直接记结论。

---

3.3 正则表达式的代数定律

正则表达式的代数定律是形式语言与自动机理论中的重要内容，它描述了正则表达式在运算过程中具有的一些代数性质。这些定律可以帮助简化和推导正则表达式，进而用于分析和构造自动机。以下是常见的正则表达式代数定律：

1.交换律 (Commutative Law)

• 对于两种运算，正则表达式的并运算是满足交换律的，但是连接运算是不满足的。
• 并运算：
  $$
  A + B = B + A
  $$
  意思是，两个正则表达式的并运算可以交换顺序。
• 连接运算：
  $$
  A \cdot B \neq B \cdot A
  $$

2.结合律 (Associative Law)

• 并运算：
  $$
  (A + B) + C = A + (B + C)
  $$
• 连接运算：
  $$
  (A \cdot B) \cdot C = A \cdot (B \cdot C)
  $$

3.分配律 (Distributive Law)

• 连接对并的分配律：
  $$
  A \cdot (B + C) = (A \cdot B) + (A \cdot C)
  $$
• 并对连接的分配律：
  $$
  (A + B) \cdot C = (A \cdot C) + (B \cdot C)
  $$

4.单位元律 (Identity Law)

• 正则表达式中有“单位元”概念，通常用空集和空字符串表示。
  • 空集 $∅$ 与并运算：
    $$
    A + \emptyset = A
    $$
  • 空字符串 $ε$ 与连接运算：
    $$
    A \cdot \varepsilon = A
    $$

5.幂集运算 (Kleene Star)

• Kleene星（表示零次或多次重复）有一些特殊的性质：
  • 结合律：
    $$
    (A^*)^* = A^*
    $$
  • 吸收律：
    $$
    A \cdot A^* = A^*
    $$
    $$
    A^* \cdot A = A^*
    $$
  • 与空集结合：
    $$
    \emptyset^* = \varepsilon
    $$
  • 空字符串的 Kleene 星：
    $$
    \varepsilon^* = \varepsilon
    $$

---

3.4 Pumping Lemma

正则语言的泵引理（Pumping Lemma）是形式语言与自动机理论中的一个重要工具，用于证明某个语言不是正则语言。泵引理提供了一种“泵”的性质，即正则语言中的某些字符串可以在一定条件下重复（或“泵”）而不改变该字符串是否属于语言。

泵引理主要适用于正则语言，它指出：如果一个语言是正则的，那么存在一个常数 $p$（泵长度），对于任何长度大于或等于 $p$ 的字符串 $s \in L$（该字符串属于语言 $L$），都可以将 $s$ 分解成以下三部分：

• $s = xyz$，其中：
  • $x$ 是 $s$ 的前缀（可能为空）。
  • $y$ 是可以被“泵”的部分，且 $|y| > 0$。
  • $z$ 是 $s$ 的后缀（可能为空）。

并且，对于任意 $i \geq 0$，字符串 $xy^i z$ 都应该属于语言 $L$，也就是说，$y$ 可以重复任意次数而不影响 $s$ 是否在语言 $L$ 中。

---

3.4.1 正则语言的泵引理证明

泵引理是正则语言的一个重要性质，它指出：如果一个语言是正则的，那么存在一个常数 $p$（泵长度），对于任何长度大于或等于 $p$ 的字符串 $s \in L$（该字符串属于语言 $L$），都可以将 $s$ 分解成以下三部分：

• $s = xyz$，其中：
  • $x$ 是 $s$ 的前缀（可能为空）。
  • $y$ 是可以被“泵”的部分，且 $|y| > 0$。
  • $z$ 是 $s$ 的后缀（可能为空）。

并且，对于任意 $i \geq 0$，字符串 $xy^i z$ 都应该属于语言 $L$，也就是说，$y$ 可以重复任意次数而不影响 $s$ 是否在语言 $L$ 中。

证明思路:

1. 假设语言是正则的：假设语言 $L$ 是正则的，那么存在一个有限状态自动机（DFA）能够接受语言 $L$。我们称该自动机为 $M$，其状态数为 $q$（即 $M$ 的状态集大小）。设 $p = q$，这是泵引理中的泵长度。

2. 选择适当的字符串$s$ ：选择一个字符串 $s \in L$，且 $|s| \geq p$。由于 $s$ 的长度大于或等于 $p$，它会经过 DFA $M$ 的多个状态，并且会在某些状态之间重复。

3. 应用鸽巢原理(Pigeonhole principle) ：根据鸽巢原理，若一个物体放入有限多个箱子中，且物体数量超过箱子数量，那么至少有一个箱子中必须放入超过一个物体。

   在这里，DFA $M$ 有 $p$ 个状态（箱子），而字符串 $s$ 长度至少为 $p$，因此在 $s$ 从起始状态到终止状态的过程中，至少有两个不同的位置会经过相同的状态。具体地，假设 $s = a_1 a_2 \dots a_n$，其中 $n \geq p$，我们可以表示 $s$ 的执行过程中的状态序列为：
   $$
   q_0, q_1, q_2, \dots, q_n
   $$
   其中 $q_0$ 是初始状态，$q_1, q_2, \dots, q_n$ 是字符串 $s$ 中每个字符对应的状态转换。

   由于状态总共有 $p$ 个，因此，根据鸽巢原理，在这 $n$ 步转换中，必然存在一个状态 $q_i$（在 $1 \leq i \leq n$）至少重复一次。假设 $q_i = q_j$ 且 $i < j$，那么在 $s$ 中，$a_i, a_{i+1}, \dots, a_j$ 这部分的输入字符会使自动机回到同一个状态。这就为我们提供了分解字符串 $s$ 的依据。

4. 分解字符串$s$ ：假设字符串 $s$ 被分解为：
   $$
   s = x , y , z
   $$
   其中：

   • $x = a_1 a_2 \dots a_{i-1}$（从起始位置到重复状态之前的部分），
   • $y = a_i a_{i+1} \dots a_{j-1}$（从第一个重复状态到第二个重复状态之间的部分），
   • $z = a_j a_{j+1} \dots a_n$（从第二个重复状态之后的部分）。

   注意到 $y$ 至少包含一个字符，因为 $i < j$，所以 $|y| > 0$。

5. 验证泵操作 ：现在我们需要验证，对于任意 $i \geq 0$，字符串 $xy^i z$ 仍然属于语言 $L$。

   • 由于 $y$ 的重复仅仅是使自动机在状态空间中来回循环，但没有改变接受状态，因此可以通过重复 $y$ 来构造新的字符串 $xy^i z$，使得新的字符串也能被自动机接受。即：
     $$
     xy^i z \in L \quad \text{对于任意} \quad i \geq 0
     $$
     这就完成了对泵引理的证明。

通过鸽巢原理，我们证明了正则语言的泵引理。我们假设语言是正则的，构造一个长度大于等于泵长度 $p$ 的字符串，并应用鸽巢原理来确定字符串中的某些部分是重复的。然后，通过分解字符串并使用状态重复性（即“泵”）来证明任意重复的部分都不会改变字符串是否属于语言，从而完成了泵引理的证明。

---

3.4.2 泵引理的形式化描述

假设 $L$ 是一个正则语言，那么存在一个常数 $p$，满足：

1. 对于任意的字符串 $s \in L$，如果 $|s| \geq p$，那么 $s$ 可以被分解为 $s = xyz$，且满足：

   • $|xy| \leq p$，
   • $|y| > 0$。

2. 对于任意 $i \geq 0$，字符串 $xy^i z \in L$。

泵引理的作用是帮助我们证明某个语言不是正则的。具体来说，如果我们能够找到一个语言中的某个字符串，并且我们无法将它分解成符合上述条件的三部分（即无法“泵”），那么就可以证明该语言不是正则的。

如何使用泵引理证明语言不是正则的?

1. 假设语言是正则的：首先假设语言 $L$ 是正则的，那么根据泵引理，必定存在一个泵长度 $p$。

2. 选择一个适当的字符串：从语言 $L$ 中选择一个特定的字符串 $s$，使得 $|s| \geq p$。

3. 尝试分解字符串：尝试将该字符串 $s$ 分解为 $s = xyz$，并确保满足上述条件。特别注意，$y$ 部分必须满足 $|y| > 0$。

4. 尝试泵操作：通过不同的 $i$ 值（即对 $y$ 进行不同次数的重复），构造新的字符串 $xy^i z$。

5. 找出矛盾：如果在某些情况下，$xy^i z$ 不再属于语言 $L$，那么就说明假设语言 $L$ 是正则的错误，从而得出结论，$L$ 不是正则语言。

---

例子 1： 语言 $L = \{ a^n b^n \mid n \geq 0 \}$

我们来尝试使用泵引理证明这个语言不是正则的。

1. 假设 $L$ 是正则的，那么根据泵引理，存在一个常数 $p$，对于任意 $s \in L$ 且 $|s| \geq p$，都可以分解为 $s = xyz$，并且满足：

   • $|xy| \leq p$，
   • $|y| > 0$。

2. 选择 $s = a^p b^p$ 作为字符串。显然，$|s| = 2p \geq p$，所以 $s$ 必须符合泵引理。

3. 根据泵引理，$s = xyz$ 且 $|xy| \leq p$，这意味着 $x$ 和 $y$ 只能包含字符 $a$，而 $z$ 中包含的字符则包含 $b$。

4. 由于 $y$ 至少包含一个 $a$（因为 $|y| > 0$），我们可以通过泵操作，选择 $i = 2$ 生成字符串 $xy^2z$，即将 $y$ 中的 $a$ 重复一次。结果是一个包含 $p+1$ 个 $a$ 和 $p$ 个 $b$ 的字符串，显然它不属于语言 $L$，因为 $L$ 中的字符串必须有相同数量的 $a$ 和 $b$。

5. 由于构造的字符串不属于 $L$，这与我们假设 $L$ 是正则语言相矛盾。因此，语言 $L = { a^n b^n \mid n \geq 0 }$ 不是正则的。

例子 2： 语言 $L = \{ ww \mid w \in {a, b}^* \}$

1. 假设 $L$ 是正则的，那么根据泵引理，存在一个泵长度 $p$。

2. 选择 $s = a^p b^p a^p b^p$ 作为字符串，显然，$|s| = 4p \geq p$，所以 $s$ 必须符合泵引理。

3. 根据泵引理，$s = xyz$ 且 $|xy| \leq p$，这意味着 $x$ 和 $y$ 只能包含字符 $a$，而 $z$ 中包含的字符包含 $b$ 和后面的部分。

4. 通过泵操作，选择 $i = 2$ 生成字符串 $xy^2z$。由于 $y$ 部分仅包含 $a$，所以将 $y$ 重复后，得到的字符串是 $a^{p+k} b^p a^p b^p$（其中 $k > 0$）。显然，这个字符串不能保持原始形式 $ww$，因为它不再符合形式 $ww$（即左右两部分必须完全相同）。

5. 因此，语言 $L$ 不是正则的。

泵引理是用来证明某个语言不是正则语言的重要工具。通过假设某个语言是正则的，并利用泵引理来分析该语言的字符串，若能找到无法满足泵引理条件的字符串，就能证明该语言不是正则语言。它为我们提供了一个有效的手段来排除正则性，尤其在证明一些较为复杂的语言不是正则语言时非常有用。

---

3.5 正则语言的封闭性

正则语言的封闭性（Closure Property）是指正则语言在某些操作下的结果仍然是正则语言。也就是说，如果我们对正则语言进行某些运算操作，那么得到的语言仍然是正则的。我们要证明正则语言在以下几种情况下是封闭的：

• 并（Union）
• 交（Intersection）
• 连接（Concatenation）
• 闭包（Kleene Closure）
• 补（Complement）
• 差（Difference）
• 反转（Reversal）
• 同态（Homomorphism）
• 逆同态（Inverse Homomorphism）

修考题经常考前面6个封闭性性质的证明,重点掌握

---

3.5.1 并运算的封闭性

并运算（Union）指的是将两个语言中的所有字符串合并在一起，构成一个新的语言。具体来说，给定两个语言 $L_1$ 和 $L_2$，它们的并集定义为：

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

这意味着，任何一个属于 $L_1$ 或者 $L_2$ 的字符串都将属于 $L_1 \cup L_2$。

问题： 如果 $L_1$ 和 $L_2$ 是正则语言，那么 $L_1 \cup L_2$ 是否也是正则语言？

答案是：是的，正则语言对于并运算是封闭的。也就是说，若 $L_1$ 和 $L_2$ 都是正则语言，那么它们的并集 $L_1 \cup L_2$ 也是正则语言。

---

为了证明正则语言对并运算封闭，我们将使用有限状态自动机（DFA）来表示正则语言。具体来说，若我们有两个 DFA 分别接受 $L_1$ 和 $L_2$，我们将构造一个新的自动机来接受它们的并集。

Step 1： 假设 $L_1$ 和 $L_2$ 是正则语言

假设我们有两个正则语言 $L_1$ 和 $L_2$，并且分别由 DFA $M_1$ 和 DFA $M_2$ 接受。

• $M_1$ 是接受 $L_1$ 的 DFA，其中有状态集 $Q_1$，起始状态 $q_1^0$，接受状态集 $F_1$，以及转移函数 $\delta_1$。
• $M_2$ 是接受 $L_2$ 的 DFA，其中有状态集 $Q_2$，起始状态 $q_2^0$，接受状态集 $F_2$，以及转移函数 $\delta_2$。

我们的目标是构造一个新的 DFA $M$，使得它接受 $L_1 \cup L_2$。

Step 2： 构造一个新的自动机 $M$ 来接受 $L_1 \cup L_2$

我们将使用一个新的起始状态，并通过非确定性选择进入 $M_1$ 或 $M_2$ 来模拟两个原始的 DFA。这种方法是基于非确定性有限自动机（NFA）的构造，最后我们将转换为一个 DFA。

1. 状态集：新的自动机 $M$ 的状态集是 $Q_1 \cup Q_2$。也就是说，$M$ 的状态集合包括 $M_1$ 和 $M_2$ 的所有状态。

2. 起始状态：$M$ 的起始状态 $q_0$ 是一个新的状态，表示新的起始状态。我们通过 $\epsilon$-转换从 $q_0$ 转移到 $q_1^0$（$M_1$ 的起始状态）或者 $q_2^0$（$M_2$ 的起始状态）。这表示新的自动机可以选择进入 $M_1$ 或 $M_2$ 来继续执行。

3. 接受状态：$M$ 的接受状态是 $M_1$ 和 $M_2$ 的接受状态集合的并集，即 $F = F_1 \cup F_2$。这意味着，只要 $M$ 到达 $M_1$ 或 $M_2$ 中的任何接受状态，就接受该字符串。

4. 转移函数：新的转移函数 $\delta$ 是如下定义的：

   • 如果在状态 $q_1$ 上，按照 $M_1$ 的转移函数进行转移；
   • 如果在状态 $q_2$ 上，按照 $M_2$ 的转移函数进行转移；
   • 从新的起始状态 $q_0$ 可以通过 $\epsilon$-转换分别转移到 $M_1$ 和 $M_2$ 的起始状态。

这样，我们通过构造一个新的 NFA 来接受 $L_1 \cup L_2$。由于 NFA 和 DFA 等价，最终我们可以将 NFA 转换为一个等价的 DFA，因此我们得出结论，$L_1 \cup L_2$ 是正则语言。

通过构造一个新的 NFA，我们证明了正则语言对于并运算是封闭的。具体地说，若 $L_1$ 和 $L_2$ 是正则语言，则它们的并集 $L_1 \cup L_2$ 也是正则语言。因为 NFA 和 DFA 等价，最终我们可以将 NFA 转换为 DFA，从而证明 $L_1 \cup L_2$ 是正则语言。

---

举个例子： 假设我们有两个正则语言：

1. $L_1 = \{ a^n \mid n \geq 1 \}$，由 DFA $M_1$ 接受。
2. $L_2 = \{ b^n \mid n \geq 1 \}$，由 DFA $M_2$ 接受。

我们希望构造一个 DFA 来接受 $L_1 \cup L_2$，即接受所有形式为 $a^n$ 或 $b^n$ 的字符串。通过上面的方法，构造出的 DFA 会有以下状态：

• 起始状态 $q_0$，可以通过 $\epsilon$-转换进入 $M_1$ 或 $M_2$ 的起始状态。
• 接受状态为 $M_1$ 和 $M_2$ 的所有接受状态的并集。
• 转移规则根据 $M_1$ 和 $M_2$ 的转移规则构造。

该 DFA 将正确接受 $a^n$ 或 $b^n$ 形式的字符串，因此它能够接受 $L_1 \cup L_2$。

通过构造一个新的 NFA 来接受并集 $L_1 \cup L_2$，并利用 NFA 和 DFA 等价的性质，我们证明了正则语言对于并运算是封闭的。即：如果 $L_1$ 和 $L_2$ 都是正则语言，那么它们的并集 $L_1 \cup L_2$ 也是正则语言。

---

3.5.2 交运算的封闭性

交运算（Intersection）用于表示两个语言中的共同部分。给定两个语言 $L_1$ 和 $L_2$，它们的交运算定义为：

$$
L_1 \cap L_2 = \{ w \mid w \in L_1 \text{ and } w \in L_2 \}
$$

这意味着 $L_1 \cap L_2$ 包含所有同时属于 $L_1$ 和 $L_2$ 的字符串。

问题： 如果 $L_1$ 和 $L_2$ 都是正则语言，那么 $L_1 \cap L_2$ 是否也是正则语言？

答案是：是的，正则语言对于交运算是封闭的。也就是说，若 $L_1$ 和 $L_2$ 都是正则语言，那么它们的交运算 $L_1 \cap L_2$ 也是正则语言。

---

为了证明正则语言对交运算封闭，我们将利用有限状态自动机（DFA）来表示正则语言。具体来说，若 $L_1$ 和 $L_2$ 分别由 DFA $M_1$ 和 DFA $M_2$ 接受，我们将通过构造一个新的自动机来接受 $L_1 \cap L_2$。

Step 1： 假设 $L_1$ 和 $L_2$ 是正则语言

假设 $L_1$ 和 $L_2$ 都是正则语言，并且分别由 DFA $M_1$ 和 DFA $M_2$ 接受。

• $M_1$ 是接受 $L_1$ 的 DFA，其中有状态集 $Q_1$，起始状态 $q_1^0$，接受状态集 $F_1$，以及转移函数 $\delta_1$。
• $M_2$ 是接受 $L_2$ 的 DFA，其中有状态集 $Q_2$，起始状态 $q_2^0$，接受状态集 $F_2$，以及转移函数 $\delta_2$。

我们的目标是构造一个新的 DFA $M$ 来接受 $L_1 \cap L_2$，即所有同时属于 $L_1$ 和 $L_2$ 的字符串。

Step 2： 构造一个新的自动机 $M$ 来接受 $L_1 \cap L_2$

为了构造接受交集 $L_1 \cap L_2$ 的 DFA，我们可以使用两个 DFA 的 直积自动机（product automaton）。直积自动机的状态集是由两个原始自动机的状态对组成，并且状态转移是由两个 DFA 的转移规则共同决定的。

1. 状态集：$M$ 的状态集是 $Q_1 \times Q_2$，即每个状态由 $M_1$ 和 $M_2$ 的一个状态对组成。

2. 起始状态：$M$ 的起始状态是 $(q_1^0, q_2^0)$，即 $M_1$ 和 $M_2$ 的起始状态的组合。

3. 接受状态：$M$ 的接受状态集是 $F_1 \times F_2$，即 $M_1$ 和 $M_2$ 的接受状态的组合。这意味着只有当 $M_1$ 和 $M_2$ 都到达各自的接受状态时，$M$ 才会接受该字符串。

4. 转移函数：$M$ 的转移函数是通过 $M_1$ 和 $M_2$ 的转移函数组合得到的。具体来说，如果 $M_1$ 在状态 $q_1$ 接收输入符号 $a$ 并转移到状态 $q_1’$，同时 $M_2$ 在状态 $q_2$ 接收输入符号 $a$ 并转移到状态 $q_2’$，那么 $M$ 在状态 $(q_1, q_2)$ 接收输入符号 $a$ 后将转移到状态 $(q_1’, q_2’)$。

通过这种构造，$M$ 就可以接受所有同时属于 $L_1$ 和 $L_2$ 的字符串，即接受交集 $L_1 \cap L_2$。

通过构造一个新的 DFA 来接受交集 $L_1 \cap L_2$，我们证明了正则语言对于交运算是封闭的。具体地说，若 $L_1$ 和 $L_2$ 都是正则语言，则它们的交运算 $L_1 \cap L_2$ 也是正则语言。

---

假设我们有两个正则语言：

1. $L_1 = { a^n b^m \mid n \geq 1 \text{ and } m \geq 1 }$，即由一个或多个 ‘a’ 后跟一个或多个 ‘b’ 构成的字符串。
2. $L_2 = { a^n b^n \mid n \geq 1 }$，即由相同数量的 ‘a’ 和 ‘b’ 构成的字符串。

为了构造一个 DFA 来接受交集 $L_1 \cap L_2$，我们需要利用两个 DFA：

• $M_1$ 是接受 $L_1$ 的 DFA。
• $M_2$ 是接受 $L_2$ 的 DFA。

我们将通过直积构造法（product construction）来构造一个新的 DFA，它接受 $L_1 \cap L_2$。

步骤 1：构造直积自动机

1. 状态集：

   • $M_1$ 的状态集为 $Q_1$，$M_2$ 的状态集为 $Q_2$，因此交集自动机 $M$ 的状态集是 $Q_1 \times Q_2$，即每个状态是由 $M_1$ 和 $M_2$ 的状态对组成。

2. 起始状态：

   • $M_1$ 的起始状态是 $q_1^0$，$M_2$ 的起始状态是 $q_2^0$，因此交集自动机的起始状态是 $(q_1^0, q_2^0)$。

3. 接受状态：

   • $M_1$ 的接受状态集为 $F_1$，$M_2$ 的接受状态集为 $F_2$。因此，交集自动机的接受状态集为 $F_1 \times F_2$，即所有 $M_1$ 和 $M_2$ 都接受的状态对。

4. 转移函数：

   • 假设 $M_1$ 在状态 $q_1$ 接收符号 $a$ 后转移到状态 $q_1’$，同时 $M_2$ 在状态 $q_2$ 接收符号 $a$ 后转移到状态 $q_2’$，那么交集自动机 $M$ 在状态 $(q_1, q_2)$ 接收符号 $a$ 后将转移到状态 $(q_1’, q_2’)$。

交集 DFA 的转移函数是通过两个原始 DFA 的转移函数组合而成的。

步骤 2：构造过程的分析

我们需要考虑交集 DFA 的工作过程：

• 对于输入字符串的处理：

  1. 交集自动机将逐步处理输入字符串，状态转移遵循 $M_1$ 和 $M_2$ 的转移规则。
  2. 当读取到字符 ‘a’ 时，$M_1$ 继续在它的状态上移动，而 $M_2$ 也继续在它的状态上移动。
  3. 当读取到字符 ‘b’ 时，$M_1$ 和 $M_2$ 分别继续处理接下来的字符，保持状态的变化。

• 接受条件：

  • 字符串必须同时满足两个条件：它属于 $L_1$（即形如 $a^n b^m$），并且它属于 $L_2$（即形如 $a^n b^n$）。因此，交集自动机接受的字符串必须是形如 $a^n b^n$，且 $n \geq 1$。

通过这个构造，交集自动机能够接受所有形如 $a^n b^n$ 的字符串，其中 $n \geq 1$，即 $L_1 \cap L_2 = \{ a^n b^n \mid n \geq 1 \}$。

通过直积构造法，最终我们得到一个新的 DFA，它接受所有形如 $a^n b^n$ 的字符串。

通过构造一个新的 DFA 来接受交集运算 $L_1 \cap L_2$，我们证明了正则语言对于交运算是封闭的。即：如果 $L_1$ 和 $L_2$ 都是正则语言，那么它们的交运算 $L_1 \cap L_2$ 也是正则语言。

---

3.5.3 连接运算的封闭性

连接运算（Concatenation）是另一种常见的运算。连接运算指的是将两个语言中的所有字符串拼接在一起，构成一个新的语言。具体来说，给定两个语言 $L_1$ 和 $L_2$，它们的连接运算定义为：

$$
L_1 \cdot L_2 = \{ w_1w_2 \mid w_1 \in L_1, w_2 \in L_2 \}
$$

这意味着，任何一个由 $L_1$ 中的字符串 $w_1$ 和 $L_2$ 中的字符串 $w_2$ 拼接而成的字符串都属于 $L_1 \cdot L_2$。

问题： 如果 $L_1$ 和 $L_2$ 是正则语言，那么 $L_1 \cdot L_2$ 是否也是正则语言？

答案是：是的，正则语言对于连接运算是封闭的。也就是说，若 $L_1$ 和 $L_2$ 都是正则语言，那么它们的连接运算 $L_1 \cdot L_2$ 也是正则语言。

---

为了证明正则语言对连接运算封闭，我们将使用有限状态自动机（DFA）来表示正则语言。具体来说，若我们有两个 DFA 分别接受 $L_1$ 和 $L_2$，我们将构造一个新的自动机来接受它们的连接。

Step 1： 假设 $L_1$ 和 $L_2$ 是正则语言

假设我们有两个正则语言 $L_1$ 和 $L_2$，并且分别由 DFA $M_1$ 和 DFA $M_2$ 接受。

• $M_1$ 是接受 $L_1$ 的 DFA，其中有状态集 $Q_1$，起始状态 $q_1^0$，接受状态集 $F_1$，以及转移函数 $\delta_1$。
• $M_2$ 是接受 $L_2$ 的 DFA，其中有状态集 $Q_2$，起始状态 $q_2^0$，接受状态集 $F_2$，以及转移函数 $\delta_2$。

我们的目标是构造一个新的 DFA $M$，使得它接受 $L_1 \cdot L_2$。

Step 2： 构造一个新的自动机 $M$ 来接受 $L_1 \cdot L_2$

我们可以通过在 $M_1$ 的接受状态添加 $\epsilon$-转换，来将 $M_1$ 和 $M_2$ 连接起来，从而构造一个新的 DFA 来接受 $L_1 \cdot L_2$。

1. 状态集：新的自动机 $M$ 的状态集是 $Q_1 \cup Q_2$，即包含 $M_1$ 和 $M_2$ 的所有状态。

2. 起始状态：$M$ 的起始状态是 $q_1^0$（即 $M_1$ 的起始状态）。从 $q_1^0$ 开始执行。

3. 接受状态：$M$ 的接受状态是 $F_2$，即 $M_2$ 的接受状态集。表示当 $M_2$ 达到接受状态时，接受该字符串。

4. 转移函数：

   • 如果在 $M_1$ 的状态中，按照 $M_1$ 的转移函数 $\delta_1$ 进行转移；
   • 如果在 $M_2$ 的状态中，按照 $M_2$ 的转移函数 $\delta_2$ 进行转移；
   • 当 $M_1$ 进入接受状态时，增加从 $M_1$ 的接受状态到 $M_2$ 的起始状态 $q_2^0$ 的 $\epsilon$-转换。

通过这种方式，新的自动机可以先接受 $L_1$ 中的字符串，然后接着接受 $L_2$ 中的字符串，最终接受整个字符串。

通过构造一个新的 DFA 来接受连接 $L_1 \cdot L_2$，我们证明了正则语言对于连接运算是封闭的。具体地说，若 $L_1$ 和 $L_2$ 是正则语言，则它们的连接 $L_1 \cdot L_2$ 也是正则语言。

---

举个例子：假设我们有两个正则语言：

1. $L_1 = \{ a^n \mid n \geq 1 \}$，由 DFA $M_1$ 接受。
2. $L_2 = \{ b^m \mid m \geq 1 \}$，由 DFA $M_2$ 接受。

我们希望构造一个 DFA 来接受 $L_1 \cdot L_2$，即接受所有形式为 $a^n b^m$（$n, m \geq 1$）的字符串。通过上面的构造方法，得到的 DFA 将有以下状态：

• 起始状态 $q_1^0$，接受 $L_1$ 中的 $a^n$ 字符串。
• 一旦 $M_1$ 接受完 $a^n$，它会通过 $\epsilon$-转换跳转到 $M_2$，然后接受 $b^m$ 字符串。
• 接受状态为 $M_2$ 的接受状态集。

该 DFA 将正确接受所有形如 $a^n b^m$ 的字符串，因此它能够接受 $L_1 \cdot L_2$。

通过构造一个新的 DFA 来接受连接运算 $L_1 \cdot L_2$，我们证明了正则语言对于连接运算是封闭的。即：如果 $L_1$ 和 $L_2$ 都是正则语言，那么它们的连接 $L_1 \cdot L_2$ 也是正则语言。

---

3.5.4 闭包运算的封闭性

闭包运算（Kleene closure）用于表示一个语言中所有可能的字符串的任意次重复（包括空字符串）。给定一个语言 $L$，其 Kleene 闭包表示为：

$$
L^* = \{ w_1 w_2 \cdots w_k \mid k \geq 0, w_i \in L \text{ for all } i \}
$$

这意味着 $L^*$ 包含所有由 $L$ 中的字符串组成的串，且可以重复零次或多次。换句话说，$L^*$ 包括空字符串 $\epsilon$ 以及 $L$ 中字符串的任意数量的串联。

问题： 如果 $L$ 是正则语言，那么 $L^*$ 是否也是正则语言？

答案是：是的，正则语言对于 Kleene 闭包运算是封闭的。也就是说，若 $L$ 是正则语言，那么它的 Kleene 闭包 $L^*$ 也是正则语言。

---

为了证明正则语言对闭包运算封闭，我们将使用有限状态自动机（DFA）来表示正则语言。具体来说，若 $L$ 是由某个 DFA $M$ 接受的正则语言，那么我们将构造一个新的自动机来接受 $L^*$。

Step 1： 假设 $L$ 是正则语言

假设 $L$ 是一个正则语言，并且由 DFA $M$ 接受。$M$ 的状态集为 $Q$，起始状态为 $q_0$，接受状态集为 $F$，以及转移函数为 $\delta$。

我们的目标是构造一个新的 DFA $M^*$ 来接受 $L^*$，即接受所有在 $L$ 中的字符串的任意次重复（包括空字符串）。

Step 2： 构造一个新的自动机 $M^*$ 来接受 $L^*$

我们通过对原始 DFA $M$ 进行修改来构造一个新的 DFA $M^*$，使其能够接受 $L^*$。

1. 状态集：$M^*$ 的状态集仍然是 $Q$，即与 $M$ 相同。

2. 起始状态：$M^*$ 的起始状态是原来的起始状态 $q_0$，并且我们将 $q_0$ 设置为一个额外的接受状态，因为空字符串 $\epsilon$ 也属于 $L^*$。

3. 接受状态：$M^*$ 的接受状态集是 $F \cup \{q_0\}$，即包括 $M$ 的接受状态以及起始状态 $q_0$（空字符串的情况）。

4. 转移函数：对于 $M^*$ 的转移函数：

   • 如果 $M$ 在某个状态 $q$ 上接收到输入符号 $a$，并转移到状态 $q’$，那么 $M^*$ 在状态 $q$ 上接收到 $a$ 后也转移到状态 $q’$。
   • 另外，在 $M^*$ 中，当它到达某个接受状态时，它可以通过一个 $\epsilon$-转换回到原来的起始状态 $q_0$，以实现对重复的字符串的处理。

通过这种方式，$M^*$ 可以接受 $L$ 中所有字符串的任意次重复，并且包括空字符串。

通过对原始 DFA $M$ 进行修改，我们证明了正则语言对于闭包运算是封闭的。具体地说，若 $L$ 是正则语言，则它的 Kleene 闭包 $L^*$ 也是正则语言。

---

举个例子： 假设我们有一个正则语言：

1. $L = \{ a^n \mid n \geq 1 \}$，由 DFA $M$ 接受。

我们希望构造一个 DFA 来接受 $L^*$，即接受所有形式为 $a^n$（$n \geq 1$）的字符串的任意次重复。这将包括像 $\epsilon$（空字符串）、$a$, $aa$, $aaa$ 等等的所有可能组合。

通过上面的构造方法，得到的 DFA 将有以下状态：

• 起始状态 $q_0$，既是接受状态也是新的起始状态，因为我们需要接受空字符串。
• 从 $q_0$ 出发，如果接收到 $a$，则转移到 $q_1$（即接受 $a$）。
• 一旦到达 $q_1$，它可以继续接收更多的 $a$ 字符串。
• 在每次接收完一个字符串后，我们都可以通过 $\epsilon$-转换返回到起始状态 $q_0$，从而实现对多个 $a$ 字符串的重复。

该 DFA 将正确接受 $a^n$ 的任意次重复形式，因此它能够接受 $L^*$。

通过构造一个新的 DFA 来接受 Kleene 闭包 $L^*$，我们证明了正则语言对于闭包运算是封闭的。即：如果 $L$ 是正则语言，那么它的 Kleene 闭包 $L^*$ 也是正则语言。

---

3.5.5 补运算的封闭性

补运算（Complement）用于表示一个语言中不包含的所有字符串。给定一个语言 $L$，它的补语言 $\overline{L}$ 定义为：

$$
\overline{L} = \Sigma^* \setminus L
$$

其中，$\Sigma^*$ 表示所有可能的字符串的集合，$L$ 是一个语言，$\overline{L}$ 就是包含所有不属于 $L$ 的字符串的语言。

问题： 如果 $L$ 是正则语言，那么 $\overline{L}$ 是否也是正则语言？

答案是：是的，正则语言对于补运算是封闭的。也就是说，若 $L$ 是正则语言，那么它的补语言 $\overline{L}$ 也是正则语言。

---

为了证明正则语言对补运算封闭，我们将使用有限状态自动机（DFA）来表示正则语言。具体来说，若 $L$ 是由某个 DFA $M$ 接受的正则语言，那么我们将通过改变 $M$ 来构造一个新的 DFA 来接受 $\overline{L}$。

Step 1： 假设 $L$ 是正则语言

假设 $L$ 是一个正则语言，并且由 DFA $M$ 接受。$M$ 的状态集为 $Q$，起始状态为 $q_0$，接受状态集为 $F$，以及转移函数为 $\delta$。

我们的目标是构造一个新的 DFA $M’$ 来接受 $\overline{L}$，即接受所有不属于 $L$ 的字符串。

Step 2： 构造一个新的自动机 $M’$ 来接受 $\overline{L}$

我们可以通过改变 $M$ 中接受状态的定义来构造一个新的 DFA 来接受 $\overline{L}$。

1. 状态集：$M’$ 的状态集与 $M$ 相同，即 $Q$。

2. 起始状态：$M’$ 的起始状态与 $M$ 相同，即 $q_0$。

3. 接受状态：$M’$ 的接受状态集是 $M$ 中所有非接受状态的集合。也就是说，如果 $M$ 中的接受状态集是 $F$，那么 $M’$ 中的接受状态集就是 $Q \setminus F$，即所有不属于 $F$ 的状态。

4. 转移函数：$M’$ 的转移函数与 $M$ 的转移函数完全相同。也就是说，$M’$ 仍然按照 $M$ 中的转移规则进行状态转换。

通过这种方式，$M’$ 会接受所有不属于 $L$ 的字符串，即它接受的语言是 $\overline{L}$。

---

3.5.6 差运算的封闭性

差运算（Difference）用于表示一个语言中的所有字符串减去另一个语言中的字符串。给定两个语言 $L_1$ 和 $L_2$，它们的差运算定义为：

$$
L_1 - L_2 = \{ w \mid w \in L_1 \text{ and } w \notin L_2 \}
$$

这意味着 $L_1 - L_2$ 包含所有属于 $L_1$ 但不属于 $L_2$ 的字符串。

问题： 如果 $L_1$ 和 $L_2$ 都是正则语言，那么 $L_1 - L_2$ 是否也是正则语言？

答案是：是的，正则语言对于差运算是封闭的。也就是说，若 $L_1$ 和 $L_2$ 都是正则语言，那么它们的差运算 $L_1 - L_2$ 也是正则语言。

---

为了证明正则语言对差运算封闭，我们将利用正则语言的补运算封闭性以及交运算封闭性来完成证明。具体来说，若 $L_1$ 和 $L_2$ 都是正则语言，那么 $L_1 - L_2$ 可以表示为 $L_1 \cap \overline{L_2}$，即 $L_1$ 与 $L_2$ 的补语言 $\overline{L_2}$ 的交集。

Step 1： 假设 $L_1$ 和 $L_2$ 是正则语言

假设 $L_1$ 和 $L_2$ 都是正则语言，并且分别由 DFA $M_1$ 和 DFA $M_2$ 接受。

• $M_1$ 是接受 $L_1$ 的 DFA，其中有状态集 $Q_1$，起始状态 $q_1^0$，接受状态集 $F_1$，以及转移函数 $\delta_1$。
• $M_2$ 是接受 $L_2$ 的 DFA，其中有状态集 $Q_2$，起始状态 $q_2^0$，接受状态集 $F_2$，以及转移函数 $\delta_2$。

我们想要构造一个新的 DFA 来接受 $L_1 - L_2$，即所有属于 $L_1$ 但不属于 $L_2$ 的字符串。

Step 2： 利用补运算和交运算构造新自动机

首先，利用正则语言对补运算的封闭性，我们知道，如果 $L_2$ 是正则语言，那么它的补语言 $\overline{L_2}$ 也是正则语言。然后，利用正则语言对交运算的封闭性，我们知道 $L_1 \cap \overline{L_2}$ 也是正则语言。

1. 构造 $M_1$ 和 $M_2$ 的补自动机： 假设 $M_1$ 和 $M_2$ 是接受 $L_1$ 和 $L_2$ 的 DFA。我们可以通过对 $M_2$ 进行修改，构造一个新的 DFA 来接受 $L_2$ 的补语言 $\overline{L_2}$，方法与补运算的证明相同。

2. 构造 $L_1 \cap \overline{L_2}$ 的交集自动机： 利用正则语言对交运算的封闭性，我们可以构造一个新的 DFA 来接受 $L_1 \cap \overline{L_2}$。这可以通过构造两个 DFA 的直积自动机（product automaton）来实现：每个状态对包含 $M_1$ 和 $M_2$ 的状态对，转移规则通过两者的转移函数组合来确定。（状态是两个自动机状态的笛卡尔积）

通过这样的构造，新的自动机可以接受所有属于 $L_1$ 但不属于 $L_2$ 的字符串，即接受差语言 $L_1 - L_2$。

通过利用正则语言对补运算和交运算的封闭性，我们证明了正则语言对于差运算是封闭的。具体地说，若 $L_1$ 和 $L_2$ 都是正则语言，则它们的差运算 $L_1 - L_2$ 也是正则语言。

---

3.5.7 反转运算的封闭性

我们来探讨正则语言在反转运算下的封闭性。即，如果一个语言是正则的，那么它的反转语言也是正则的。

定义： 给定一个语言 $L$，我们定义其反转语言 $L^R$ 为：

$$
L^R = \{ w^R \mid w \in L \}
$$

其中，$w^R$ 是字符串 $w$ 的反转。例如，如果 $w = \text{abc}$，则 $w^R = \text{cba}$。

正则语言的封闭性意味着，如果 $L$ 是一个正则语言，那么 $L^R$ 也一定是正则语言。

我们通过以下步骤来证明正则语言对反转运算是封闭的：

1. 假设 $L$ 是一个正则语言，那么存在一个确定性有限自动机（DFA） $M$ 来接受 $L$。我们的目标是构造一个 DFA 来接受 $L^R$。

2. 构造反转的非确定性有限自动机（NFA）：

   • 假设 $M = (Q, \Sigma, \delta, q_0, F)$ 是接受语言 $L$ 的 DFA，其中：
     • $Q$ 是状态集，
     • $\Sigma$ 是输入字母表，
     • $\delta$ 是转移函数，
     • $q_0$ 是起始状态，
     • $F$ 是接受状态集。

   我们需要构造一个 NFA $M^R = (Q, \Sigma, \delta^R, q_0^R, F^R)$ 来接受语言 $L^R$。

3. 反转过程的步骤：

   • 反转接受状态：NFA 的接受状态集 $F^R$ 应该是原 DFA $M$ 的起始状态 $q_0$。
   • 反转转移函数：在 $M$ 中，每个状态到另一个状态的转移是由 $\delta$ 定义的。在 $M^R$ 中，我们将这些转移反向，即如果在 $M$ 中有一个转移 $\delta(q, a) = p$，那么在 $M^R$ 中，$p$ 到 $q$ 也应有一个转移，记作 $\delta^R(p, a) = q$。
   • 起始状态：NFA $M^R$ 的起始状态是 $M$ 的接受状态集 $F$ 中的所有状态。这是因为我们希望通过反转路径从接受状态回到起始状态。

4. 从 NFA 到 DFA：

   • 由于正则语言是通过 DFA 接受的，因此我们可以通过子集构造法将 NFA 转换为一个等价的 DFA。这个 DFA 将接受语言 $L^R$。

5. 结论：

   • 通过构造 NFA 和将其转换为 DFA，我们证明了反转运算对于正则语言是封闭的。

正则语言对反转运算是封闭的，即如果一个语言是正则的，那么它的反转语言也是正则的。通过构造 NFA 来接受反转语言，并利用子集构造法将其转化为 DFA，我们证明了这一点。

---

3.5.8 同态运算的封闭性

在形式语言理论中，同态（Homomorphism）是指将一个语言中的字母按某种规则替换为另一个字母或字母串的操作。我们来探讨正则语言在同态运算下的封闭性。即，如果一个语言是正则的，那么它的同态映射后的语言也是正则的。

定义：

给定一个字母表 $\Sigma$ 和一个同态映射 $\varphi: \Sigma^* \to \Gamma^*$，其中 $\Gamma$ 是另一个字母表，$\varphi$ 是将字符串从 $\Sigma$ 字母表映射到 $\Gamma$ 字母表的映射。

假设我们有一个语言 $L \subseteq \Sigma^*$，则语言 $L^\varphi$ 是通过对语言 $L$ 中的每个字符串应用同态映射 $\varphi$ 得到的语言：

$$
L^\varphi = { \varphi(w) \mid w \in L }
$$

其中，$\varphi(w)$ 是字符串 $w$ 在同态映射下的结果。我们的目标是证明正则语言在同态下是封闭的，即如果 $L$ 是正则语言，那么 $L^\varphi$ 也是正则语言。

我们通过以下步骤来证明正则语言对同态运算是封闭的：

1. 假设 $L$ 是一个正则语言：

   • 如果 $L$ 是正则语言，那么存在一个 DFA（确定性有限自动机）$M = (Q, \Sigma, \delta, q_0, F)$ 来接受 $L$。

2. 定义同态映射：

   • 给定一个同态映射 $\varphi: \Sigma^* \to \Gamma^*$，它将字母表 $\Sigma$ 上的每个符号映射到 $\Gamma$ 上的字符串。
   • 例如，假设 $\varphi$ 将 $\Sigma = {a, b}$ 映射到 $\Gamma = {0, 1}$，其中 $\varphi(a) = 0$，$\varphi(b) = 11$。对于字符串 $w = ab$, $\varphi(w) = 011$。

3. 构造接受 $L^\varphi$ 的 NFA：

   • 给定 DFA $M$ 接受语言 $L$，我们将构造一个新的 NFA 来接受语言 $L^\varphi$。
   • 对于 $M$ 中的每个状态转移 $\delta(q, a) = p$，我们将新的 NFA 中的转移改为 $\delta’(q, \varphi(a)) = p$，即每次读取字母 $a$ 时，我们在新自动机中读取 $\varphi(a)$。

4. 从 NFA 到 DFA：

   • 由于正则语言是通过 DFA 接受的，因此我们可以通过子集构造法（subset construction）将这个新的 NFA 转换为一个等价的 DFA。

5. 结论：

   • 通过上述构造过程，我们证明了正则语言在同态下是封闭的，即如果 $L$ 是正则语言，那么 $L^\varphi$ 也是正则语言。

---

子集构造法是将一个 NFA 转换为等价的 DFA 的经典方法。具体过程如下：

1. NFA 的状态集：

   • 假设我们已经构造了一个 NFA $M^\varphi = (Q, \Gamma, \delta’, q_0, F)$ 来接受语言 $L^\varphi$，其中：
     • $Q$ 是 NFA 的状态集，
     • $\Gamma$ 是新的字母表（经过同态映射后），
     • $\delta’$ 是新的转移函数，
     • $q_0$ 是起始状态，
     • $F$ 是接受状态集。
   • 在这个 NFA 中，状态的转移是非确定性的，因此多个状态可能会同时被激活。

2. DFA 的状态集：

   • 对应的 DFA 状态集是 NFA 状态集的子集。具体来说，DFA 中的每个状态都表示 NFA 中某些状态的集合。这些集合是 NFA 在某个状态和输入符号下可能到达的状态的集合。

3. DFA 状态转移：

   • 假设 DFA 的当前状态是 $S \subseteq Q$（即 NFA 中某些状态的集合），而当前输入符号是 $a \in \Gamma$。DFA 的下一状态是由 NFA 对每个状态集合的转移决定的：
     $$
     \delta_{\text{DFA}}(S, a) = \bigcup_{q \in S} \delta’(q, a)
     $$
     也就是说，DFA 状态转移函数根据当前的输入符号 $a$，将所有处于集合 $S$ 中的 NFA 状态的转移结果联合起来，得到新的状态集合。

4. DFA 的起始状态：

   • DFA 的起始状态对应于 NFA 起始状态的集合。假设 NFA 的起始状态是 $q_0$，那么 DFA 的起始状态是包含 $q_0$ 的集合：${q_0}$。

5. DFA 的接受状态：

   • DFA 中的接受状态集合是 NFA 中任何包含接受状态的集合。具体来说，DFA 的状态 $S$ 是接受状态，如果 $S$ 包含 NFA 的某个接受状态。

6. 结束：

   • 通过这些步骤，我们就能够构造一个 DFA，它的状态集由 NFA 的状态集的子集组成，转移函数由 NFA 的转移函数导出，起始状态和接受状态也对应了 NFA 中的起始状态和接受状态。

例子：假设我们有一个简单的 NFA 和同态映射：

• NFA $M^\varphi$ 接受语言 $L^\varphi$，其中 $\Sigma = {a, b}$ 和 $\Gamma = {0, 1}$，并且同态映射 $\varphi$ 如下：

  • $\varphi(a) = 0$
  • $\varphi(b) = 11$

• 假设 $L = {ab, aa, abba}$，我们想要计算 $L^\varphi$，即应用同态映射后得到的语言：

  • $\varphi(ab) = 011$
  • $\varphi(aa) = 00$
  • $\varphi(abba) = 0111$

根据这些映射，我们可以构造一个 NFA 来接受 $L^\varphi = {011, 00, 0111}$。接下来，我们使用子集构造法将 NFA 转换为一个 DFA。

---

3.5.9 逆同态运算的封闭性

在形式语言理论中，逆同态（Inverse Homomorphism）是指将一个语言中的字符串的各个字母按某种规则反向映射到字母表中的操作。我们来探讨正则语言在逆同态运算下的封闭性。即，如果一个语言是正则的，那么它的逆同态映射后的语言也是正则的。

定义：给定一个字母表 $\Sigma$ 和一个同态映射 $\varphi: \Sigma^* \to \Gamma^*$，其中 $\Gamma$ 是另一个字母表，$\varphi$ 是将字符串从 $\Sigma$ 字母表映射到 $\Gamma$ 字母表的映射。

逆同态映射是一个将一个字符串从 $\Gamma^*$ 映射到 $\Sigma^*$ 的操作，记作 $\varphi^{-1}$. 对于任意的字符串 $w \in \Gamma^*$，$\varphi^{-1}(w)$ 表示所有可能的字符串，它们在同态映射 $\varphi$ 下可以映射到 $w$。

逆同态语言 $L^{\varphi^{-1}}$ 是对语言 $L$ 应用逆同态映射 $\varphi^{-1}$ 后得到的语言：

$$
L^{\varphi^{-1}} = \{ w \in \Sigma^* \mid \varphi(w) \in L \}
$$

即，语言 $L^{\varphi^{-1}}$ 包含所有可以通过同态映射 $\varphi$ 映射到语言 $L$ 中的字符串。

我们要证明的是：如果 $L$ 是正则语言，那么 $L^{\varphi^{-1}}$ 也是正则语言。

我们通过以下步骤来证明正则语言在逆同态运算下是封闭的：

1. 假设 $L$ 是正则语言：

   • 如果 $L$ 是正则语言，那么存在一个 DFA（确定性有限自动机）$M = (Q, \Sigma, \delta, q_0, F)$ 来接受 $L$。

2. 定义逆同态映射：

   • 给定一个同态映射 $\varphi: \Sigma^* \to \Gamma^*$，我们定义其逆同态映射为 $\varphi^{-1}$，即对于每个字符串 $w \in \Gamma^*$，$\varphi^{-1}(w)$ 是所有可以被映射到 $w$ 的字符串。

3. 构造逆同态的 NFA：

   • 假设我们已经有一个 DFA $M = (Q, \Sigma, \delta, q_0, F)$ 来接受语言 $L$。我们要构造一个接受语言 $L^{\varphi^{-1}}$ 的 NFA。
   • 逆同态的状态转移：对于每个输入符号 $a \in \Gamma$，如果在 DFA 中有转移 $\delta(q, \varphi(a)) = p$，则在逆同态的 NFA 中，我们可以反向将转移为从 $p$ 到 $q$ 的转移。
   • 这个反向的过程类似于同态的构造，只不过是在反向应用同态映射的结果。

4. 从 NFA 到 DFA：

   • 由于正则语言是通过 DFA 接受的，因此我们可以通过子集构造法（subset construction）将这个新的 NFA 转换为一个等价的 DFA。

5. 结论：

   • 通过构造逆同态的 NFA，并通过子集构造法将其转化为 DFA，我们证明了正则语言在逆同态运算下是封闭的。

正则语言对逆同态运算是封闭的。也就是说，如果一个语言是正则的，那么它经过逆同态映射后的语言也是正则语言。我们通过将 DFA 中的转移规则反向应用于 NFA，进而通过子集构造法将其转化为 DFA，证明了这一点。

---

3.6 自动机最小化

自动机最小化是形式语言与自动机理论中的一个重要主题，其目的是将一个确定有限自动机（DFA）转化为一个状态数量最少的等价自动机。最小化的目的是减少状态数量，进而减少计算复杂度和存储需求。

最小化的目标是通过合并一些等价的状态来简化自动机。两个状态被称为等价的，如果它们在自动机中的行为相同，即对于任何输入串，它们的转移和接受状态是一样的。

---

3.6.1 状态的等价性

在自动机理论中，两个状态 $q_1$ 和 $q_2$ 被称为 等价状态，如果它们在给定的输入下，能够产生相同的行为。具体来说，两个状态 $q_1$ 和 $q_2$ 是等价的，意味着对于每一个输入串 $w$，从状态 $q_1$ 和 $q_2$ 出发，最终是否接受该串的结果是相同的。

形式化地讲，状态 $q_1$ 和 $q_2$ 等价，若满足以下条件：

1. 对于每个输入串 $w$，从 $q_1$ 和 $q_2$ 出发，最终的接受状态是否一致。即：
   $$
   \delta(q_1, w) \in F \iff \delta(q_2, w) \in F
   $$
   其中，$\delta(q, w)$ 表示从状态 $q$ 出发读取输入串 $w$ 后到达的状态，$F$ 是接受状态的集合。

等价状态的数学证明：假设我们有一个确定有限自动机（DFA） $M = (Q, \Sigma, \delta, q_0, F)$，其中：

• $Q$ 是状态集合；
• $\Sigma$ 是输入字母表；
• $\delta$ 是状态转移函数；
• $q_0$ 是初始状态；
• $F$ 是接受状态集合。

我们要证明两个状态 $q_1$ 和 $q_2$ 等价，即：
$$
\delta(q_1, w) \in F \iff \delta(q_2, w) \in F \quad \text{对所有输入串 } w \text{ 成立}.
$$

证明过程：

1. 定义等价关系：
   定义一个等价关系 $\sim$ 在状态集 $Q$ 上。对于任意两个状态 $q_1$ 和 $q_2$：

   $$
   q_1 \sim q_2 \iff \forall w \in \Sigma^*, \delta(q_1, w) \in F \iff \delta(q_2, w) \in F
   $$
   即 $q_1$ 和 $q_2$ 等价当且仅当，对于任意的输入串 $w$，从 $q_1$ 和 $q_2$ 出发，最终是否接受该串的结果是相同的。

2. 划分状态集：
   通过上述等价关系 $\sim$，将状态集 $Q$ 划分为若干个等价类，每个等价类中的状态对于所有输入串具有相同的接受行为。

3. 构造最小化自动机：
   在自动机最小化过程中，合并那些属于同一个等价类的状态。这些状态在任何输入下的行为完全一致，因此可以作为一个状态来表示，从而得到最小化的自动机。

反证法证明：

假设 $q_1$ 和 $q_2$ 是两个状态，它们在行为上是等价的，即：
$$
\delta(q_1, w) \in F \iff \delta(q_2, w) \in F \quad \text{对于所有的输入串 } w.
$$

接下来我们证明：如果 $q_1 \sim q_2$，那么它们的转移关系完全一致。

1. 假设我们有一个输入字母 $a \in \Sigma$ 和状态 $q_1$, $q_2$，即考虑从 $q_1$ 和 $q_2$ 出发，分别读取输入字母 $a$ 后转移到新的状态。

2. 由于 $q_1 \sim q_2$，对于任意的输入串 $w$，从 $q_1$ 和 $q_2$ 出发，最终的接受状态是相同的。因此，考虑输入串 $w = a$ 时，从 $q_1$ 和 $q_2$ 出发，都会进入同一个接受状态或非接受状态。

3. 从这个反推，我们可以得出：从状态 $q_1$ 和 $q_2$ 读取输入字母 $a$ 后，必须转移到相同的状态。因此，状态转移关系 $\delta(q_1, a) = \delta(q_2, a)$ 必然成立。

4. 由于 $q_1 \sim q_2$ 对于所有输入串 $w$ 都成立，因此可以逐步推断出它们的转移关系一致。

通过上述过程，我们证明了两个状态 $q_1$ 和 $q_2$ 的等价性意味着它们的转移函数在所有输入下都一致，从而可以被合并为一个状态。在自动机最小化过程中，等价的状态可以被合并，从而简化自动机的结构，减少状态数量。

---

3.6.2 填表算法

对于任意一个DFA，我们都可以找到一个等价的、状态数最少的DFA。两个状态如果对于任何输入串都产生相同的接受/拒绝行为，我们就说它们是等价的。

让我们通过一个具体的例子来理解这个过程。考虑一个识别所有以”ab”结尾的二进制串的DFA：

形式化定义如下：

• 状态集合 $Q = \{q_0, q_1, q_2, q_3, q_4\}$
• 字母表 $\Sigma = \{a, b\}$
• 初始状态 = $q_0$
• 接受状态 $F = \{q_4\}$

转移函数 $\delta$ 可以表示为：

状态	$a$	$b$
$q_0$	$q_1$	$q_3$
$q_1$	$q_1$	$q_2$
$q_2$	$q_1$	$q_4$
$q_3$	$q_1$	$q_3$
$q_4$	$q_1$	$q_3$

填表算法步骤如下：

Step 1 :初始区分

首先，我们将所有状态分为两组：

• 接受状态：$\{q_4\}$
• 非接受状态：$\{q_0, q_1, q_2, q_3\}$

Step 2 :构建初始表格

我们创建一个对角表格，标记明显不等价的状态对（一个是接受状态，一个是非接受状态）：

	$q_1$	$q_2$	$q_3$	$q_4$
$q_0$	-	-	-	X
$q_1$		-	-	X
$q_2$			-	X
$q_3$				X

其中 X 表示这对状态明显不等价。

补充一下什么是等价：

• 如果 $q_i \in F$ 且 $q_j \notin F$，则 $(q_i, q_j)$ 不等价。
• 如果 $q_i \notin F$ 且 $q_j \in F$，则 $(q_i, q_j)$ 不等价。
• 否则，将 $(q_i, q_j)$ 标记为等价。

Step 3 :迭代区分过程

对于每对状态 $p,q$，我们需要检查：

• 在每个输入符号 $a \in \Sigma$ 下
• 如果 $\delta(p,a)$ 和 $\delta(q,a)$ 已被标记为不等价
• 则 $p$ 和 $q$ 也应被标记为不等价

例如，检查 $(q_0,q_1)$：

• 输入 $a$：$\delta(q_0,a)=q_1$, $\delta(q_1,a)=q_1$ （转向相同状态）
• 输入 $b$：$\delta(q_0,b)=q_3$, $\delta(q_1,b)=q_2$
• 由于 $q_2$ 和 $q_3$ 在到达接受状态 $q_4$ 的能力上不同，所以 $q_0$ 和 $q_1$ 是不等价的

最终的表格变为：

	$q_1$	$q_2$	$q_3$	$q_4$
$q_0$	X	X	X	X
$q_1$		X	X	X
$q_2$			X	X
$q_3$				X

Step 4 : 合并等价状态

根据最终表格，我们可以看到所有状态对都被标记为不等价，因此这个自动机已经是最小的了。

如果有未被标记的状态对 $(p,q)$，则：

• 创建一个新状态 $[p]$ 代表 $p$ 和 $q$ 的等价类
• 新状态的转移函数：$\delta([p],a) = [\delta(p,a)]$
• 如果 $p$ 或 $q$ 是接受状态，则 $[p]$ 也是接受状态
• 如果 $p$ 或 $q$ 是初始状态，则 $[p]$ 也是初始状态

填表算法基于以下重要概念：

1. Myhill-Nerode 定理：两个状态等价当且仅当它们对于任何输入串都有相同的接受性

2. 等价关系的传递性：如果状态 $p$ 等价于 $q$，且 $q$ 等价于 $r$，则 $p$ 等价于 $r$

3. 不等价的传递性：如果输入 $w$ 能区分状态 $p$ 和 $q$，则 $w$ 也能区分所有等价于 $p$ 的状态和所有等价于 $q$ 的状态

这个算法的时间复杂度为 $O(n^2)$，其中 $n$ 是状态数。它是求解DFA最小化问题的一个经典且高效的算法。

4. Context-Free Language

上下文无关文法（Context-free grammar，CFG）是一种形式化的文法，用于生成语言。它由一个包含以下四个部分的四元组组成：

$$
G = (V, \Sigma, R, S)
$$

• $V$：变量（非终结符）的集合。
• $\Sigma$：终结符的集合，即语言中的字母表。
• $R$：产生式规则的集合，每个规则的形态为 $A \rightarrow \alpha$，其中 $A \in V$ 是一个非终结符，$\alpha$ 是由终结符和非终结符组成的字符串（可以为空，表示空串）。
• $S$：开始符号，是一个特殊的非终结符，表示语言的开始。

上下文无关文法的关键在于其产生式规则的结构：每个产生式的左边是一个单一的非终结符（例如 $A$），右边是一个由终结符和非终结符组成的字符串（例如 $\alpha$）。这一点与上下文相关文法不同，后者的产生式规则的左边可以是多个符号的组合（非终结符或终结符）。

---

4.1 上下文无关语言的定义

上下文无关语言（CFL）是由上下文无关文法（CFG）生成的语言。换句话说，如果一个语言可以通过某个上下文无关文法的规则从开始符号 $S$ 推导出一个字符串，那么这个字符串就属于上下文无关语言。

上下文无关语言是一种形式语言，其生成规则由上下文无关文法（CFG）定义，不依赖于符号周围的上下文。

例如，考虑如下文法：$aSb \rightarrow aYb \mid \epsilon$

这个文法的符号串Y是根据S的派生式产生的，不依赖S的上下文a和b。

上下文无关语言有如下特性：

• 递归结构：上下文无关语言能够表示递归结构。它能够处理很多具有递归特征的语言，例如编程语言中的嵌套结构（如括号匹配、表达式求值等）。
• 构造性强：上下文无关语言不仅可以描述自然语言中的一些结构，还能表达很多编程语言的语法。
• 推导和归约：上下文无关语言的推导过程是基于替换规则的应用，直到生成一个由终结符组成的字符串。这个过程通常是“递归下降”的。

上下文无关语言与 下推自动机（Pushdown Automaton，PDA） 密切相关。下推自动机是能够识别上下文无关语言的一种自动机模型。下推自动机与有限自动机的主要区别在于它有一个栈，可以用来存储额外的信息，从而实现对递归结构的处理。

例如，对于文法 $S \rightarrow aSb \mid \epsilon$

下推自动机可以使用栈来存储“a”并在遇到“b”时逐一弹出栈顶的“a”，从而保证字符串中的“a”和“b”的数量相等。

上下文无关语言的例子：

• $\{ a^n b^n \mid n \geq 0 \}$（例如 $aabbb$）
• $\{ w \mid w \text{ 是一个合法的括号序列} \}$，比如 $(())$、(())、(()()() )等。
• 编程语言中的语法，如 C 语言中的函数定义、条件表达式等。

尽管上下文无关语言在很多实际应用中都非常重要，但它们并不是万能的。上下文无关语言不能处理所有类型的语言，例如，语言

$$
\{ a^n b^n c^n \mid n \geq 0 \}
$$

就不是上下文无关的，因为它需要同时确保 $a$、$b$、$c$ 的数量相等，这超出了上下文无关文法的能力。

上下文无关语言（CFL）是一类可以由上下文无关文法生成的语言，具有非常广泛的应用，尤其在编程语言的语法分析中。它们能够表示许多递归结构，但并不具备表达所有形式语言的能力。上下文无关语言可以通过下推自动机进行识别，其计算能力介于有限自动机和图灵机之间。

接下来的内容我们就仔细探讨上下文无关语言的特点和识别它的PDA的特点

---

4.2 Derivation & Reduction

• 派生是从开始符号出发，一步步通过应用文法规则，直到得到一个终结符的串。
• 规约是从终结符串开始，一步步逆向应用文法规则，将其简化为开始符号。

派生和规约是语法分析的两个核心过程，在编译器的语法分析阶段起着至关重要的作用。

• 最左派生和最右派生是两种不同的推导方式，它们规定了在派生过程中每一步替换的顺序：最左派生总是替换最左边的非终结符，最右派生总是替换最右边的非终结符。
• 规约是派生过程的逆过程，通过逆向应用产生式规则，将终结符串简化回开始符号。

这两者在语法分析和推导中各有重要作用，理解它们对于学习上下文无关语言的解析非常关键。

---

4.2.1 派生（Derivation）

派生是根据文法规则从开始符号 $S$ 开始，逐步替换非终结符，直到得到一个仅由终结符组成的字符串的过程。派生有两种常见的形式：最左派生和最右派生。

最左派生（Left Derivation）

最左派生指的是在派生过程中，每一步都选择最左边的非终结符进行替换。换句话说，在每一步推导中，总是选择最左边的非终结符来进行替换，直到最终只剩下终结符。

最右派生（Right Derivation）

最右派生指的是在派生过程中，每一步都选择最右边的非终结符进行替换。也就是说，在每一步推导中，总是选择最右边的非终结符来进行替换，直到最终只剩下终结符。

举个简单的例子辨别一下最左派生和最右派生：

$
E \rightarrow E + T \mid T \
$

$
T \rightarrow T * F \mid F
$

$
F \rightarrow (E) \mid id
$

让我们用这个文法来推导表达式 id + id * id。

在最左派生中,我们每次都选择最左边的非终结符来替换:

从起始符号开始：$E$

使用 $E \rightarrow E + T$ 替换最左边的 $E$：$E \Rightarrow E + T$

使用 $E \rightarrow T$ 替换最左边的 $E$：$E \Rightarrow T + T$

使用 $T \rightarrow F$ 替换最左边的 $T$：$E \Rightarrow F + T$

使用 $F \rightarrow id$ 替换 $F$：$E \Rightarrow id + T$

使用 $T \rightarrow T * F$ 替换 $T$：$E \Rightarrow id + T * F$

使用 $T \rightarrow F$ 替换 $T$：$E \Rightarrow id + F * F$

使用 $F \rightarrow id$ 替换第一个 $F$：$E \Rightarrow id + id * F$

使用 $F \rightarrow id$ 替换最后的 $F$：$E \Rightarrow id + id * id$

---

在最右派生中,我们每次都选择最右边的非终结符来替换:

从起始符号开始：$E$

使用 $E \rightarrow E + T$ 替换 $E$：$E \Rightarrow E + T$

使用 $T \rightarrow T * F$ 替换最右边的 $T$：$E \Rightarrow E + T * F$

使用 $T \rightarrow F$ 替换 $T$：$E \Rightarrow E + F * F$

使用 $F \rightarrow id$ 替换最右边的 $F$：$E \Rightarrow E + F * id$

使用 $F \rightarrow id$ 替换剩下的 $F$：$E \Rightarrow E + id * id$

使用 $E \rightarrow T$ 替换 $E$：$E \Rightarrow T + id * id$

使用 $T \rightarrow F$ 替换 $T$：$E \Rightarrow F + id * id$

使用 $F \rightarrow id$ 替换 $F$：$E \Rightarrow id + id * id$

---

4.2.2 规约（Reduction）

规约是派生的反过程，即从一个终结符字符串开始，逐步通过逆向应用文法规则，将字符串中的终结符和非终结符替换回更高层次的非终结符，直到恢复到开始符号 $S$ 为止。规约和派生是上下文无关文法中解析过程的两个主要组成部分。

在规约过程中，每一步都是根据文法的产生式规则来“逆向”推导。例如，如果有一个产生式 $A \rightarrow \alpha$，并且我们当前的字符串中包含 $\alpha$，则我们可以用 $A$ 来替代 $\alpha$。

假设我们已经得到了一个字符串（比如终结符的串），然后通过逆推规则一步一步将其还原为开始符号 $S$：

1. 如果字符串中包含某个产生式的右边部分（例如 $A \rightarrow \alpha$），我们可以用左边的非终结符 $A$ 替换掉右边的部分 $\alpha$。
2. 继续这个过程，直到字符串被简化为开始符号 $S$。

规约通常是在语法分析过程中进行的，尤其是自顶向下或自底向上的语法分析方法。

---

假设我们有输入字符串 $id + id * id$，我们将展示如何将其规约回开始符号 $E$。规约过程实际上是最右派生的逆过程，我们需要从右向左观察并应用合适的产生式规则。
详细规约步骤

• 第一步规约：观察最右端的 $id$，应用规则 $F \rightarrow id$
  $$id + id * id \Rightarrow id + id * F$$

• 第二步规约：继续向左，遇到另一个 $id$，同样应用规则 $F \rightarrow id$
  $$id + id * F \Rightarrow id + F * F$$

• 第三步规约：现在我们看到 $ F * F $ 的形式，这符合规则 $
  T \rightarrow T*F$

$$id + F * F \Rightarrow id + T$$

• 第四步规约：处理最左边的 $id$，应用规则 $F \rightarrow id$
  $$id + T \Rightarrow F + T$$

• 最后一步规约：应用规则 $E \rightarrow E + T$，将 $F + T$ 规约为 $E$
  $$F + T \Rightarrow E$$

---

4.3 文法等价性

在上下文无关文法（Context-Free Grammar, CFG）中，文法等价性指的是两个文法生成相同语言，即它们能够产生相同的所有字符串。换句话说，若两个文法 $G_1$ 和 $G_2$ 对于任意输入串 $w$ 都能通过各自的推导产生这个字符串 $w$，则我们称这两个文法是等价的。

文法等价性的常见方式：

1. 语言等价：
   如果两个文法生成相同的语言，即它们能够生成相同的所有字符串，那么我们说这两个文法是语言等价的。

   对于文法 $G_1$ 和 $G_2$，如果 $\mathcal{L}(G_1) = \mathcal{L}(G_2)$（其中 $\mathcal{L}(G)$ 表示文法 $G$ 生成的语言），那么它们是语言等价的。

2. 推导等价：
   两个文法可能有不同的推导方式，但如果它们生成相同的语言，且能够通过等价的推导步骤将一个文法的推导转换为另一个文法的推导，我们也可以认为这两个文法在某种程度上是等价的。通常来说，如果文法 $G_1$ 和 $G_2$ 通过推导能够互相转换，它们也可以被视为等价的。

判断文法是否等价：

• 直接比较语言：通过生成的语言是否相同来判断两个文法是否等价。
• 转换法：通过将一个文法转换为另一个文法的等价形式（例如，转换为简化文法、正规文法等）来判断它们是否等价。

让我举一个正确的语言等价的文法例子:

$G_1$:

$$
S \rightarrow aA
$$

$$
A \rightarrow aA \mid b
$$

$G_2$:

$$
S \rightarrow a a^* b
$$

这两个文法都生成语言 $L = \{a^nb | n \geq 1\}$,即至少包含一个 $a$ 后面跟着一个 $b$ 的所有字符串。
我们可以验证:

$G_1$ 中,第一步必须生成一个 $a$,然后 $A$ 可以生成任意多个 $a$ 最后生成一个 $b$
$G_2$ 直接表达了这个语言的形式:一个 $a$ 后面跟着任意多个 $a$ (包括零个),最后是一个 $b$

这两个文法虽然写法不同,但生成的语言完全相同,所以它们是语言等价的。

文法等价性通常是通过比较两个文法生成的语言是否相同来判断的。如果两个文法生成的语言相同，则我们认为它们是等价的。

---

4.4 Parse Tree

在形式语言与自动机的学习中，语法分析树（Parse Tree） 是一个非常重要的概念。它通常用于表示一个输入字符串在某个特定文法下的语法结构，反映了该字符串如何由文法规则生成。语法分析树可以帮助我们理解输入字符串是如何符合某种文法的，并且它是编译器中的一个核心组件，特别是在编译过程的语法分析阶段。

4.4.1 语法分析树定义

语法分析树是一棵树形结构，其特点如下：

• 根节点：树的根通常代表语言的开始符号（Start Symbol），例如 $S$（常见于上下文无关文法）。
• 内部节点：每个内部节点表示文法中的某个非终结符，或者在某些情况下可能是终结符的组合。
• 叶节点：树的叶子节点表示文法中的终结符，也就是输入字符串的实际字符或符号。

构建语法分析树的过程实际上是推导过程的可视化。对于一个给定的输入字符串，通过应用文法规则逐步替代非终结符，直到最终替换成终结符。具体的过程包括：

1. 选择开始符号，例如 $S$。
2. 使用文法规则（例如 $S \to aSb \mid \epsilon$）将开始符号逐步展开，生成新的非终结符。
3. 每次展开都会在树中添加一个新的节点，并继续扩展，直到输入字符串完全匹配到叶节点为止。
4. 最终生成的树形结构就是该输入字符串的语法分析树。

假设我们有一个简单的上下文无关文法：

$$
S \to aSb \mid \epsilon
$$

我们想分析字符串 "aabb" 是否符合这个文法。

• 步骤 1：从根节点开始，$S$。
• 步骤 2：使用 $S \to aSb$ 规则，得到 $S \to aSb$。
• 步骤 3：继续展开 $S \to aSb$，得到 $S \to aaSbb$。
• 步骤 4：再次应用 $S \to \epsilon$，得到 $S \to aa\epsilon bb$，结果是 "aabb"。

对应的语法分析树如下：

  S
 /|\
a S b
   /|\
  a S b
     |
     ε

4.4.2 语法分析树与派生

语法分析树是派生过程的图形化表示。每一次应用文法规则都对应语法分析树中的一个分支或一个节点的展开。具体来说：

• 根节点：表示开始符号。
• 内部节点：表示一个非终结符，并且这些非终结符是通过相应的文法规则展开的。
• 叶子节点：表示终结符，通常是输入字符串的实际字符。

从派生到语法分析树：

• 给定一个派生过程，我们可以通过每一步推导生成一个节点，并将其按顺序组织成一棵树。
• 每个非终结符的应用对应语法分析树中的一个内节点，每次替代操作都创建树的分支。

从语法分析树到派生：

• 通过语法分析树，我们可以逆向得到派生过程。从根节点开始，逐层向下，按照每个节点的子节点选择合适的文法规则，逆推出每一步派生。

根据上面例子的语法分析树

  S
 /|\
a S b
   /|\
  a S b
     |
     ε

可以看到：

• 每一步派生都对应树中的每一层节点展开，每一层都是一个文法规则的应用。
• 从语法分析树回推派生：从根到叶的路径，可以通过每个非终结符的替换规则反推出派生过程。

4.4.3 Grammar Ambiguity

文法的歧义性（ Grammar Ambiguity）指的是一种情况：对于某个文法，它可以通过多种不同的方式生成同一个字符串，导致该字符串存在多个不同的语法分析树（Parse Tree）或推导（Derivations）。这种属性使得文法具有歧义性。

如果一个文法 $G$ 存在某个字符串 $w$（属于该文法生成的语言 $L(G)$），使得 $w$ 有两种或更多不同的最左推导（Leftmost Derivations）、最右推导或语法分析树，则称该文法 $G$ 是歧义文法。

换句话说：

• 该文法中的某些规则允许通过多种不同的方式从开始符号 $S$ 推导出字符串 $w$。
• 歧义产生的原因是文法的结构无法唯一确定字符串的生成方式。

---

歧义文法的例子：考虑以下文法 $G$：

$$
S \to S + S \mid S \times S \mid a
$$

• 终结符 $a$ 表示一个变量或操作数。
• 非终结符 $S$ 表示一个表达式。

该文法可以生成字符串 $a + a \times a$，但这个字符串有两种不同的语法分析树：

1. 如果优先处理“+”操作：

  S
 /|\
S  + S
|    /|\
a   S  x S
    |    |
    a    a

1. 如果优先处理“×”操作：

  S
 /|\
S  x S
|    |
a   S
    /|\
   S  + S
   |    |
   a    a

这两棵语法分析树对应相同的字符串 $a + a \times a$，但它们表示的结构和含义不同（例如，不同的操作符优先级会导致计算结果不同）。

文法歧义性的影响

• 语义不明确：文法的歧义性使得字符串的含义变得不明确。例如，在编程语言中，歧义文法可能会导致相同的表达式得出不同的结果。
• 解析困难：歧义文法更难解析，因为解析器可能无法唯一确定语法分析树。
• 编译器设计问题：大多数编程语言都要求文法是无歧义的，以确保代码的解析和执行是确定性的。

遗憾的是，对于一个任意上下文无关文法（CFG），无法通过算法判断文法是否是歧义的。这是形式语言理论中的一个已知的不可判定问题（Undecidable Problem）。
不过，对于简单的情况，可以通过手动检查某些字符串是否有多种推导方式来发现歧义。

---

如何消除歧义: 如果一个文法是歧义的，有时可以将其重写为一个等价的无歧义文法。例如，上述的算术表达式文法可以通过引入操作符优先级和结合性规则来消除歧义：

• 定义优先级：乘法（$\times$）的优先级高于加法（$+$）。
• 定义结合性：加法和乘法均为左结合。

重写后的文法如下：

$$
E \to E + T \mid T
$$
$$
T \to T \times F \mid F
$$
$$
F \to a
$$

在这个文法中，字符串 $a + a \times a$ 的语法分析树唯一，结构如下：

  E
 /|\
E  + T
|    |
F    T
|    |
a    F
     |
     a

这棵语法分析树清楚地表示了“$\times$”比“$+$”具有更高的优先级，从而消除了歧义。

文法的歧义性不仅存在于编程语言或形式语言中，也经常出现在自然语言中。例如：

I saw the man with a telescope

这句话有两种解释：

1. 我用望远镜看到了这个人。
2. 我看到了一个拿着望远镜的人。

这种歧义也可以用两棵不同的语法分析树表示，与形式语言中的歧义类似。

4.5 文法化简与范式

文法化简是形式语言与自动机理论中的重要内容，用于简化上下文无关文法（CFG），使其更易于分析或实现。文法化简的目标是通过一系列步骤，移除冗余规则和符号，同时保持生成语言不变。主要包括以下三步：

Step 1: 消除无用符号

无用符号是指在文法中不可能被用来生成任何字符串的非终结符，分为两种情况：

• 不可达符号：从起始符号出发，无法到达的非终结符。
• 非生成符号：无法推导出终结符串的非终结符。

处理方法：

1. 找出能够推导出终结符串的非终结符（生成符号）。
2. 找出从起始符号可以到达的符号（可达符号）。
3. 移除所有既非生成又不可达的符号及相关产生式。

Step 2: 消除 $\epsilon$-产生式

$\epsilon$-产生式是指形如 $A \to \epsilon$ 的规则（$\epsilon$ 表示空串）。除非文法描述的语言中包含空串，应尽量消除这些规则。

处理方法：

1. 找出所有可以直接或间接推导出空串的非终结符（称为 $\epsilon$-可导符号）。
2. 对于每个包含 $\epsilon$-可导符号的产生式，生成所有可能的替代产生式（通过省略这些符号）。
3. 如果起始符号可以推导出空串，需增加新的起始符号：
   $$
   S’ \to S \ | \ \epsilon
   $$

Step 3: 消除单一产生式

单一产生式是指形如 $A \to B$ 的规则，其中 $A$ 和 $B$ 都是非终结符。它们会增加文法复杂性但不会增加语言的表达能力。

处理方法：

1. 找出所有的单一产生式。
2. 替换单一产生式 $A \to B$ 为 $A$ 直接生成 $B$ 的所有右部。

Step 4: 化简为规范形式（可选）

如果需要进一步化简，可将文法转化为以下特定的规范形式：

• 格雷巴赫范式（GNF）：每个产生式的右部以一个终结符开头，后跟若干非终结符。
• 乔姆斯基范式（CNF）：每个产生式要么是两个非终结符，要么是一个终结符。

$$
A \to BC
$$

$$
A \to a
$$

下面我们先了解一下文法化简的规范形式。

---

4.5.1 Chomsky Normal Form (CNF)

在形式语言与自动机理论中，Chomsky Normal Form（CNF） 是一种用于上下文无关文法（Context-Free Grammar，CFG）标准化的形式。通过将文法转换为 Chomsky 正常形式，很多算法（如 CYK 算法）可以变得更加高效。

Chomsky Normal Form 的定义:

一个上下文无关文法 $G = (V, \Sigma, R, S)$，其中 $V$ 是非终结符的集合，$\Sigma$ 是终结符的集合，$R$ 是产生式规则的集合，$S$ 是起始符号。若该文法满足以下条件，则称其为 Chomsky Normal Form：

1. 每个产生式 $A \rightarrow \alpha$ 满足以下之一：

   • $\alpha$ 是一个终结符，形式为 $A \rightarrow a$，其中 $a \in \Sigma$。
   • $\alpha$ 是两个非终结符的串，形式为 $A \rightarrow BC$，其中 $B, C \in V$，并且 $B$ 和 $C$ 不能是起始符号 $S$。

2. 如果文法包含空产生式（即 $S \rightarrow \epsilon$），则 $S$ 必须是唯一的起始符号，并且不能出现在右侧的产生式中。

3. 如果文法包含单位产生式（即 $A \rightarrow B$），则可以用合适的规则进行替换，消除单位产生式。

假设我们有一个上下文无关文法 $G$，想要将其转换为 Chomsky Normal Form，通常的步骤如下：

Step 1: 移除空产生式
首先，移除所有的空产生式（即产生式 $A \rightarrow \epsilon$）。如果文法包含这样的产生式，需要适当调整其他产生式，将空产生式的影响消除。

Step 2: 移除单位产生式
移除所有的单位产生式（即 $A \rightarrow B$ 形式的产生式）。这一步需要通过替换和合并产生式来完成。

Step 3: 替换长右边的产生式
将所有右边有两个以上符号的产生式替换为符合 CNF 的形式。如果存在一个产生式 $A \rightarrow X_1 X_2 \dots X_n$，其中 $n > 2$，则通过引入新的非终结符逐步将其拆分成二元产生式。

Step 4: 替换终结符的混合产生式
如果在某个产生式中，右边含有终结符和非终结符混合的情况（例如 $A \rightarrow aB$，其中 $a \in \Sigma$ 且 $B \in V$），则通过引入新的非终结符来替换终结符。

假设我们有以下文法：

• $S \rightarrow AB \mid a$
• $A \rightarrow SA \mid \epsilon$
• $B \rightarrow b$

我们将其转换为 Chomsky Normal Form：

1. 移除空产生式：由于 $A \rightarrow \epsilon$，我们需要将文法中可能依赖 $A$ 的规则调整为不包含 $A$ 的形式。

   • $S \rightarrow AB \mid a$ -> $S \rightarrow AB \mid a \mid B$
   • $A \rightarrow SA$ -> $A \rightarrow SA \mid S$
   • $B \rightarrow b$

2. 移除单位产生式：从 $A \rightarrow S$ 和 $S \rightarrow B$ 可以看出我们有单位产生式。我们将 $A \rightarrow S$ 和 $S \rightarrow B$ 替换成等效的产生式。

   • $S \rightarrow AB \mid a \mid b$
   • $A \rightarrow AB \mid a$
   • $B \rightarrow b$

3. 替换长右边的产生式：没有长右边的产生式，所有产生式都已经是符合 CNF 的。

最终结果可能会是：

• $S \rightarrow AB \mid a \mid b$
• $A \rightarrow AB \mid a$
• $B \rightarrow b$

---

4.5.2 Greibach Normal Form (GNF)

Greibach Normal Form（GNF） 是另一种上下文无关文法（Context-Free Grammar，CFG）的标准形式。与 Chomsky Normal Form 不同，GNF 强调了产生式的结构形式。特别是，每个产生式的右侧必须以一个终结符开始，其后跟随零个或多个非终结符。

Greibach Normal Form 的定义:

一个上下文无关文法 $G = (V, \Sigma, R, S)$，其中 $V$ 是非终结符的集合，$\Sigma$ 是终结符的集合，$R$ 是产生式规则的集合，$S$ 是起始符号。若该文法满足以下条件，则称其为 Greibach Normal Form：

1. 每个产生式 $A \rightarrow \alpha$ 都是以下形式之一：

   • $\alpha$ 以一个终结符开始，形式为 $A \rightarrow a \gamma$，其中 $a \in \Sigma$，且 $\gamma$ 是非终结符的串（包括空串）。

2. 文法中的每个产生式右边必须以一个终结符开头，后面可以跟任意数量的非终结符。

与 Chomsky Normal Form 不同，GNF 不要求右边的产生式是二元的，而是要求右边的第一个符号是终结符。

假设我们有一个上下文无关文法 $G$，想要将其转换为 Greibach Normal Form，通常的步骤如下：

Step 1: 移除空产生式
首先，移除所有的空产生式（即产生式 $A \rightarrow \epsilon$）。如果文法包含这样的产生式，需要调整文法中的其他产生式，以消除空产生式的影响。

Step 2: 移除单位产生式
移除所有的单位产生式（即 $A \rightarrow B$ 形式的产生式）。这一步需要通过替换单位产生式来完成。

Step 3: 替换长右边的产生式
如果产生式的右边有多个符号，则需要通过引入新的非终结符逐步将其转换为以终结符开始的形式。

• 例如，如果你有一个产生式 $A \rightarrow X_1 X_2 \dots X_n$，其中 $n > 1$，你需要分解该产生式，使其右边以终结符开始，并且后面跟着非终结符。

Step 4: 替换终结符的混合产生式
如果产生式的右边包含终结符与非终结符的混合（例如 $A \rightarrow aB$），则需要将终结符与非终结符分离，确保右边的产生式以终结符开头，后面跟随零个或多个非终结符。

假设我们有以下文法：

• $S \rightarrow AB \mid a$
• $A \rightarrow SA \mid \epsilon$
• $B \rightarrow b$

我们将其转换为 Greibach Normal Form：

1. 移除空产生式：首先，移除空产生式 $A \rightarrow \epsilon$，并调整其他规则。

   • $S \rightarrow AB \mid a \mid b$
   • $A \rightarrow SA \mid S$
   • $B \rightarrow b$

2. 移除单位产生式：从 $A \rightarrow S$ 和 $S \rightarrow B$ 可以看出我们有单位产生式。我们将其替换成等效的产生式。

   • $S \rightarrow AB \mid a \mid b$
   • $A \rightarrow AB \mid a$
   • $B \rightarrow b$

3. 替换长右边的产生式：没有长右边的产生式，所有产生式的右边已经以终结符开头。

最终文法可能是：

• $S \rightarrow a \mid b$
• $A \rightarrow aB \mid b$
• $B \rightarrow b$

---

4.5.3 CYK算法（Cocke-Younger-Kasami Algorithm）

CYK算法是一种用于上下文无关文法（CFG，Context-Free Grammar）分析的算法，主要用于确定一个给定的字符串是否能被某个上下文无关文法生成。CYK算法基于动态规划思想，通过构造一个三维表格来高效地判断一个字符串是否属于某个上下文无关文法所生成的语言。

假设我们有一个上下文无关文法 $G = (N, \Sigma, P, S)$，其中：

• $N$ 是非终结符的集合，
• $\Sigma$ 是终结符的集合，
• $P$ 是文法规则的集合，
• $S$ 是起始符号。

给定一个字符串 $w = w_1 w_2 \dots w_n$（长度为 $n$），我们通过 CYK 算法来判断 $w$ 是否能通过文法 $G$ 生成。

具体步骤如下：

1. 构造三维表格： 创建一个三维表格 $T$，其中 $T[i,j]$ 表示字符串 $w_i, w_{i+1}, \dots, w_j$（从第 $i$ 个字符到第 $j$ 个字符）是否可以由某个非终结符生成。表格的大小为 $n \times n$，其中 $n$ 是输入字符串的长度。每个表格项 $T[i,j]$ 都会包含一些非终结符，表示该子字符串可以由哪些非终结符生成。

2. 初始化： 对于长度为 1 的子串（即单个字符），检查该字符是否是文法中的终结符。如果是，填充对应的非终结符。

• 比如，对于每个 $w_i \in \Sigma$，我们查找规则 $A \to w_i$，如果存在，将 $A$ 加入到 $T[i,i]$ 中。

3. 填充表格： 对于长度大于 1 的子串，遍历所有可能的分割点 $k$（从 1 到 $n-1$），并检查是否可以通过文法规则将其分割为两个子串。对于每一对非终结符 $A \to BC$，如果 $B$ 能生成左边的子串（即 $T[i,k]$），$C$ 能生成右边的子串（即 $T[k+1,j]$），则将 $A$ 加入 $T[i,j]$。

4. 终止条件： 最终，检查起始符号 $S$ 是否在 $T[1,n]$ 中。如果是，说明字符串 $w$ 可以由文法 $G$ 生成；否则不能。

CYK算法的时间复杂度为 $O(n^3 \cdot |G|)$，其中：

• $n$ 是输入字符串的长度，
• $|G|$ 是文法规则的数量。

---

举个例子，给定一个乔姆斯基范式的上下文无关文法：

$$G = ({S, A, B, C}, {a, b}, S, P)$$

其中规则 $P$ 如下：

$S \to AB \mid BC$

$A \to BA \mid a$

$B \to CC \mid b$

$C \to AB \mid a$

问题：字符串 bbabaa 能不能通过该文法产生？

我们使用 CYK 算法来解决这个问题，CYK 算法通过构建一个表格来判断每个子串能由哪些非终结符生成。表格的第 $i$ 列和第 $j$ 行表示由哪些非终结符可以生成字字符串 $\sigma_i \dots \sigma_j$。

	1	2	3	4	5	6
i	a	b	b	a	b	a
j=1	{$B$}
j=2		{$B$}
j=3	{$A$}	{$S, A$}	{$A, C$}
j=4	{$S, C$}	{$S, C$}	{$S, C$}	{$B$}
j=5	{$B$}	{$B$}	{$B$}	{$A, S$}	{$A, C$}
j=6	{$A, S$}	{$A, S$}	{$A, S$}		{$B$}	{$A, C$}

判断过程如下：

• 初始化：对于每个字符 $w_i$（即 $a$, $b$ 等），填充对应的非终结符。

  • 对于 $w_1 = b$，由规则 $B \to b$，填充 $T[1, 1] = \{B\}$。
  • 对于 $w_2 = b$，同理填充 $T[2, 2] = \{B\}$。
  • 以此类推，对于其他字符填充。

• 递推填充：根据文法规则检查可能的组合，填充表格中的其他位置。例如：

  • $T[3, 3]$ 可以通过 $A \to a$ 填充为 $\{A\}$。
  • $T[2, 3]$ 可以通过 $S \to BC$ 或 $A \to BA$ 填充为 $\{S, A\}$
  • 如此继续填充整个表格。(比如生成bba这样的子串，那么就要考虑b + ba 或者bb+a这样的派生)

• 终止条件：最终检查 $T[1, 6]$ 是否包含文法的起始符号 $S$。如果包含，则说明该字符串可以由该文法生成。

由于 $T[1, 6]$ 中包含了文法的起始符号 $S$，我们可以得出结论：字符串 bbabaa 能由文法 $G$ 生成。

---

4.6 Pumping Lemma for CFLs

上下文无关语言（CFL）的泵引理指出，对于任何上下文无关语言 $L$，如果 $L$ 是无限的，那么存在一个常数 $p$（泵长），使得对于所有长度大于等于 $p$ 的字符串 $s \in L$，$s$ 可以分解为五个部分 $s = uvwxy$，满足以下条件：

1. 对于所有 $i \geq 0$，$uv^i w x^i y \in L$。
2. $|v| + |x| > 0$ （也就是说，$v$ 和 $x$ 不全为空）。
3. $|vwx| \leq p$ （即 $v$ 和 $x$ 的长度加起来不能超过泵长 $p$）。

我们假设 $L$ 是一个无限的上下文无关语言。由于 $L$ 是上下文无关语言，根据上下文无关文法的结构特性，它对应着一个下推自动机（PDA）。这个 PDA 需要满足一个条件：它可以“泵”字符串，即通过重复某些部分的字符串仍然保持在语言 $L$ 中。

根据泵引理的假设，存在一个泵长 $p$，使得对于所有长度大于等于 $p$ 的字符串 $s \in L$，该字符串 $s$ 可以分解为 $s = uvwxy$，且满足以下条件：

• $|vwx| \leq p$。
• $|v| + |x| > 0$。

上下文无关语言可以通过上下文无关文法（CFG）生成，也可以通过下推自动机（PDA）来接受。我们利用这些结构来展示泵引理。

• 对于一个长度大于等于 $p$ 的字符串 $s \in L$，它一定可以通过上下文无关文法的推导生成。
• 由于 $L$ 是无限的，存在某些部分的推导树，可以分解成五个部分 $uvwxy$，其中：
  • $v$ 和 $x$ 是可以被“泵”重复的部分。
  • $v$ 和 $x$ 的长度总和不超过 $p$。
  • 这意味着，对于某些合适的 $i$，$v$ 和 $x$ 可以重复而不破坏语言的结构。

这里的证明也会用到Pigeonhole Principal，就不细讲了

根据上下文无关语言的结构，字符串 $s$ 可以分解为 $s = uvwxy$，且满足以下条件：

• $|vwx| \leq p$，这意味着 $v$ 和 $x$ 的总长度不会超过泵长 $p$，它们的长度是有限的。
• $|v| + |x| > 0$，这表示 $v$ 和 $x$ 不能同时为空。

通过泵引理，我们知道，如果我们“泵”字符串 $s$ 中的部分 $v$ 和 $x$，即重复它们的次数，则得到的新字符串 $uv^i w x^i y$ 仍然属于语言 $L$，对于所有 $i \geq 0$。

根据泵引理的假设，对于所有 $i \geq 0$，$uv^i w x^i y \in L$。这意味着，通过增加 $v$ 和 $x$ 部分的数量，字符串依然保持在语言 $L$ 中。

该过程的关键在于，通过适当的分解和“泵”操作，语言的结构保持不变，因此可以通过上下文无关文法或下推自动机接受。

通过泵引理，我们可以证明某些语言不是上下文无关语言。例如，反证法通常用于证明一个语言不符合上下文无关语言的要求。通过选择一个合适的字符串，并假设它满足泵引理的条件，我们可以展示某些操作导致字符串不再属于该语言，从而得出该语言不是上下文无关语言的结论。

---

通过泵引理，我们可以用反证法证明某些语言不是上下文无关语言。假设我们要证明某个语言 $L$ 不是上下文无关语言，通常通过以下步骤：

1. 假设 $L$ 是上下文无关语言，并假设它满足泵引理。
2. 选择一个字符串 $s \in L$，其长度大于等于泵长 $p$，然后将其分解为 $s = uvwxy$，并使用泵引理。
3. 展开 $uv^i w x^i y$ 并证明对于某些值的 $i$，$uv^i w x^i y$ 不属于 $L$，从而得出矛盾。
4. 由此得出结论，$L$ 不是上下文无关语言。

例子：证明 $L = \{ a^n b^n c^n \mid n \geq 0 \}$ 不是上下文无关语言

我们使用上下文无关语言的泵引理来证明 $L = \{ a^n b^n c^n \mid n \geq 0 \}$ 不是上下文无关语言。

1. 假设 $L$ 是上下文无关语言：
   假设 $L$ 是上下文无关语言，且存在泵长 $p$。根据泵引理，任何长度大于或等于 $p$ 的字符串 $s$ 都可以分解为 $s = uvwxy$，其中 $|vwx| \leq p$ 且 $|v| + |x| > 0$。

2. 选择字符串 $s = a^p b^p c^p$：
   选择字符串 $s = a^p b^p c^p$，它显然属于语言 $L$，并且 $|s| = 3p \geq p$。

3. 分解字符串 $s$：
   根据泵引理，$s = uvwxy$，其中 $|vwx| \leq p$，并且 $|v| + |x| > 0$。由于 $|vwx| \leq p$，它只能覆盖字符串中的某一部分（即 $a^n$、$b^n$ 或 $c^n$）。而且，由于 $|v| + |x| > 0$，$v$ 和 $x$ 必定包含某些重复的字符。

4. 泵引理的应用：
   根据泵引理，对于所有的 $i \geq 0$，$uv^i w x^i y$ 应该仍然属于 $L$。但是，如果我们选择 $i > 1$，则会得到不匹配的字符串，如 $uv^2 w x^2 y$，这个字符串在 $a^n b^n c^n$ 结构中就无法保持相同数量的 a、b 和 c，从而不再属于 $L$。

5. 得出矛盾：
   因此，我们得出结论，$L$ 不可能是上下文无关语言，因为泵引理得出的结论与 $L$ 的定义矛盾。

上下文无关语言的泵引理是通过对语言字符串的分解和重复来证明语言的一些特性。它为我们提供了一个方法，可以通过反证法证明某些语言不是上下文无关语言。

---

4.7 上下文无关语言的封闭性

CFL（上下文无关语言，Context-Free Languages）的运算封闭性是指当对CFL进行一些特定的语言运算时，运算结果是否仍然是CFL。这里先给出结论：

• 封闭性的运算有：
  • 代换（Substitution）
  • 并（Union）
  • 连接（Concatenation）
  • 闭包（Kleene Star
  • 同态（Homomorphism）
  • 逆同态（Inverse Homomorphism）
  • 反转（Reversal）
• 不封闭的运算有：
  • 交（Intersection）
  • 补（Complement）

这里的证明也是修考的常考点，必须掌握得滚瓜烂熟

---

4.7.1 代换（Substitution）封闭

我们需要证明：如果$L$是一个上下文无关语言（CFL），并且每个符号$x$在$L$中都被替换成一个CFL语言$A_x$，那么代换后的语言也是CFL。

证明过程如下：

1. 定义代换运算：
   假设$L$是一个上下文无关语言，并且对于$L$中的每个符号$x$，我们定义一个CFL语言$A_x$。代换运算的结果$L’$是通过将$L$中的每个符号$x$替换为相应的语言$A_x$得到的，即
   $$ L’ = \{ w_1w_2 \cdots w_n \mid w_i \in A_{x_i} \text{，且} x_1x_2 \cdots x_n \in L \} $$
   其中$w_i$是符号$x_i$在语言$A_{x_i}$中的一个字符串。

2. 构造文法：
   由于$L$是一个CFL，假设$L$的文法是$G = (V, \Sigma, R, S)$，其中$V$是非终结符集，$\Sigma$是终结符集，$R$是产生式规则，$S$是开始符号。

   对于每个符号$x$，我们有一个CFL语言$A_x$，假设$A_x$的文法是$G_x = (V_x, \Sigma_x, R_x, S_x)$。

3. 构造代换后的文法：
   我们可以构造一个新文法$G’$来生成$L’$。文法$G’$的非终结符集合包括所有$G$中的非终结符以及所有$A_x$的非终结符。文法规则由以下部分构成：

   • 对于$G$中的每个产生式$A \to \alpha$，我们将其替换为：
     $$ A \to \alpha’ $$
     其中$\alpha’$是通过将$\alpha$中的每个符号$x_i$替换为$A_{x_i}$的开始符号$S_{x_i}$得到的。

   • 对于每个$A_x$中的产生式$S_x \to w$，我们加入产生式$S_x \to w$到$G’$中。

   通过这些规则，$G’$可以生成代换后的语言$L’$。

4. 结论：
   我们通过构造一个新的文法$G’$，使得$G’$生成代换后的语言$L’$。由于文法$G’$是上下文无关的（它是由上下文无关文法$G$和$A_x$的文法组合而成的），因此$L’$也是一个上下文无关语言。

因此，CFL对于代换运算是封闭的。

---

4.7.2 并（Union）封闭

我们需要证明：如果$L_1$和$L_2$都是上下文无关语言（CFL），那么$L_1 \cup L_2$也是上下文无关语言。

证明过程如下：

1. 假设：
   假设$L_1$和$L_2$都是上下文无关语言。根据定义，$L_1$和$L_2$分别可以由上下文无关文法$G_1 = (V_1, \Sigma, R_1, S_1)$和$G_2 = (V_2, \Sigma, R_2, S_2)$生成，其中$V_1$和$V_2$是非终结符集，$\Sigma$是终结符集，$R_1$和$R_2$是产生式规则，$S_1$和$S_2$是开始符号。

2. 构造新的文法：
   我们现在构造一个新的文法$G = (V, \Sigma, R, S)$，用来生成$L_1 \cup L_2$。新的文法$G$的组成如下：

   • 非终结符集：$V = V_1 \cup V_2 \cup \{S\}$，其中$S$是$L_1 \cup L_2$的开始符号。

   • 终结符集：$\Sigma$与$L_1$和$L_2$的终结符集相同，都是$\Sigma$。

   • 产生式规则集：$R$包括以下规则：

     1. $S \to S_1 \mid S_2$，其中$S_1$是$L_1$的开始符号，$S_2$是$L_2$的开始符号。
     2. 对于$G_1$中的每个产生式$A \to \alpha$，将其直接加入$R$。
     3. 对于$G_2$中的每个产生式$B \to \beta$，将其直接加入$R$。

   • 开始符号：$S$是新的开始符号。

3. 证明新文法生成的语言是$L_1 \cup L_2$：
   通过新的文法$G$，我们可以生成任意一个$L_1$中的字符串或$L_2$中的字符串。具体来说：

   • 如果$w \in L_1$，则$w$可以通过$S \to S_1$产生，然后根据$G_1$中的产生式生成$w$。
   • 如果$w \in L_2$，则$w$可以通过$S \to S_2$产生，然后根据$G_2$中的产生式生成$w$。

   因此，$L_1 \cup L_2$中的任意字符串都可以通过文法$G$生成。

4. 结论：
   由于我们通过构造一个上下文无关文法$G$来生成$L_1 \cup L_2$，并且文法$G$是上下文无关的（由$G_1$和$G_2$组合而成），因此$L_1 \cup L_2$也是上下文无关语言。

因此，CFL对于并运算是封闭的。

---

4.7.3 连接（Concatenation）封闭

我们需要证明：如果$L_1$和$L_2$都是上下文无关语言（CFL），那么$L_1 \cdot L_2$（即$L_1$和$L_2$的连接）也是上下文无关语言。

证明过程如下：

1. 假设：
   假设$L_1$和$L_2$都是上下文无关语言。根据定义，$L_1$和$L_2$分别可以由上下文无关文法$G_1 = (V_1, \Sigma, R_1, S_1)$和$G_2 = (V_2, \Sigma, R_2, S_2)$生成，其中$V_1$和$V_2$是非终结符集，$\Sigma$是终结符集，$R_1$和$R_2$是产生式规则，$S_1$和$S_2$是开始符号。

2. 构造新的文法：
   我们现在构造一个新的文法$G = (V, \Sigma, R, S)$，用来生成$L_1 \cdot L_2$。新的文法$G$的组成如下：

   • 非终结符集：$V = V_1 \cup V_2 \cup {S}$，其中$S$是$L_1 \cdot L_2$的开始符号。

   • 终结符集：$\Sigma$，与$L_1$和$L_2$的终结符集相同。

   • 产生式规则集：$R$包括以下规则：

     1. $S \to S_1 S_2$，其中$S_1$是$L_1$的开始符号，$S_2$是$L_2$的开始符号。
     2. 对于$G_1$中的每个产生式$A \to \alpha$，将其直接加入$R$。
     3. 对于$G_2$中的每个产生式$B \to \beta$，将其直接加入$R$。

   • 开始符号：$S$是新的开始符号。

3. 证明新文法生成的语言是$L_1 \cdot L_2$：
   通过新的文法$G$，我们可以生成$L_1 \cdot L_2$中的任意字符串。具体来说：

   • 如果$w = w_1w_2$，其中$w_1 \in L_1$且$w_2 \in L_2$，那么：
     • 首先通过$S \to S_1 S_2$产生$w_1w_2$。
     • 然后，$w_1$可以通过$S_1$的产生式根据$G_1$中的规则生成，$w_2$可以通过$S_2$的产生式根据$G_2$中的规则生成。

   因此，$L_1 \cdot L_2$中的每个字符串都可以通过文法$G$生成。

4. 结论：
   由于我们通过构造一个上下文无关文法$G$来生成$L_1 \cdot L_2$，并且文法$G$是上下文无关的（由$G_1$和$G_2$组合而成），因此$L_1 \cdot L_2$也是上下文无关语言。

因此，CFL对于连接运算是封闭的。

---

4.7.4 闭包（Kleene Star）封闭

我们需要证明：如果$L$是一个上下文无关语言（CFL），那么$L^*$（即$L$的闭包）也是上下文无关语言。

证明：

1. 假设：
   假设$L$是一个上下文无关语言。根据定义，$L$可以由一个上下文无关文法$G = (V, \Sigma, R, S)$生成，其中$V$是非终结符集，$\Sigma$是终结符集，$R$是产生式规则，$S$是开始符号。

2. 构造新的文法：
   我们现在构造一个新的文法$G^* = (V^*, \Sigma, R^*, S^*)$，用来生成$L^*$。新的文法$G^*$的组成如下：

   • 非终结符集：$V^* = V \cup \{S^* \}$，其中$S^*$是新的开始符号。

   • 终结符集：$\Sigma$，与$L$的终结符集相同。

   • 产生式规则集：$R^*$包括以下规则：

     1. $S^* \to \epsilon \mid S S^*$，这里$\epsilon$表示空串，$S$是$L$的开始符号。
     2. 对于$G$中的每个产生式$A \to \alpha$，将其直接加入$R^*$。

   • 开始符号：$S^*$是新的开始符号。

3. 证明新文法生成的语言是$L^*$：
   通过新的文法$G^*$，我们可以生成$L^*$中的任意字符串。具体来说：

   • 如果$w \in L^*$，那么$w$可以分解为若干个$L$中字符串的串联，假设$w = w_1w_2\cdots w_n$，其中每个$w_i \in L$。
   • 首先通过$S^* \to S S^*$规则生成前缀$w_1w_2 \cdots w_{n-1}$。
   • 然后通过$S^* \to \epsilon$规则生成空串，结束生成过程。
   • 对于每个$w_i \in L$，根据$G$中的产生式生成$w_i$。

   因此，$L^*$中的每个字符串都可以通过文法$G^*$生成。

4. 结论：
   由于我们通过构造一个上下文无关文法$G^*$来生成$L^*$，并且文法$G^*$是上下文无关的（由$G$和$S^*$的规则组合而成），因此$L^*$也是上下文无关语言。

因此，CFL对于Kleene闭包运算是封闭的。

---

4.7.5 同态（Homomorphism）封闭

我们需要证明：如果$L$是一个上下文无关语言（CFL），并且$h$是一个同态映射，那么$h(L)$也是上下文无关语言。

证明过程如下：

1. 假设：
   假设$L$是一个上下文无关语言，且$L$由文法$G = (V, \Sigma, R, S)$生成，其中$V$是非终结符集，$\Sigma$是终结符集，$R$是产生式规则，$S$是开始符号。$h$是一个同态映射，它将语言$\Sigma$中的每个符号映射到语言$\Sigma’$中的某个字符串。

2. 定义同态映射：
   同态映射$h$是一个函数，它将$\Sigma$中的每个符号映射为一个字符串，即对于每个符号$a \in \Sigma$，$h(a)$是一个字符串。为了简便起见，我们假设$h$将$\Sigma$中的每个符号映射为$\Sigma’$中的一个子串。

3. 构造新的文法：
   我们将构造一个新的文法$G_h = (V, \Sigma’, R_h, S_h)$来生成$h(L)$。新的文法$G_h$的组成如下：

   • 非终结符集：$V$，即与$L$相同的非终结符集。

   • 终结符集：$\Sigma’$，这是映射$h$后得到的新的终结符集。

   • 产生式规则集：$R_h$包括以下规则：

     1. 对于$G$中的每个产生式$A \to \alpha$，我们将其替换为$A \to h(\alpha)$，其中$h(\alpha)$表示将$\alpha$中的每个符号通过$h$映射到新的符号串上。
     2. 如果$A \to a_1 a_2 \cdots a_n$是$G$中的某个产生式，则$A \to h(a_1) h(a_2) \cdots h(a_n)$是$G_h$中的相应产生式。

   • 开始符号：$S_h = S$，即$L$的开始符号。

4. 证明新文法生成的语言是$h(L)$：
   通过新的文法$G_h$，我们可以生成$h(L)$中的每个字符串。具体来说：

   • 假设$w = w_1 w_2 \cdots w_n \in L$，其中每个$w_i \in \Sigma$。
   • 通过$G$中的产生式规则，我们可以生成$w$。
   • 在$G_h$中，$w$会被映射为$h(w_1) h(w_2) \cdots h(w_n)$，这正是$h(L)$中的一个字符串。

   因此，$h(L)$中的每个字符串都可以通过文法$G_h$生成。

5. 结论：
   由于我们通过构造一个上下文无关文法$G_h$来生成$h(L)$，并且文法$G_h$是上下文无关的（它仅仅是对$G$进行符号替换），因此$h(L)$也是上下文无关语言。

因此，CFL对于同态运算是封闭的。

---

4.7.6 逆同态（Inverse Homomorphism）封闭

我们需要证明：如果$L$是一个上下文无关语言（CFL），并且$h$是一个同态映射，那么$h^{-1}(L)$（即$L$的逆同态映射）也是上下文无关语言。

证明过程如下：

1. 假设：
   假设$L$是一个上下文无关语言，且$L$由文法$G = (V, \Sigma, R, S)$生成，其中$V$是非终结符集，$\Sigma$是终结符集，$R$是产生式规则，$S$是开始符号。$h$是一个同态映射，它将语言$\Sigma$中的每个符号映射到语言$\Sigma’$中的某个字符串。

2. 定义逆同态映射：
   同态映射$h$将$\Sigma$中的每个符号映射为一个字符串，而逆同态映射$h^{-1}$将$\Sigma’$中的每个字符串反向映射到$\Sigma$中的符号集合。对于每个符号$a \in \Sigma$，$h(a)$是一个字符串，那么$h^{-1}(w)$将字符串$w$映射回其对应的符号集合。例如，如果$h(a) = w$，那么$h^{-1}(w) = a$。

3. 构造新的文法：
   我们现在构造一个新的文法$G_{h^{-1}} = (V, \Sigma, R_{h^{-1}}, S_{h^{-1}})$，用来生成$h^{-1}(L)$。新的文法$G_{h^{-1}}$的组成如下：

   • 非终结符集：$V$，即与$L$相同的非终结符集。

   • 终结符集：$\Sigma$，与原语言$L$的终结符集相同。

   • 产生式规则集：$R_{h^{-1}}$包括以下规则：

     1. 对于$G$中的每个产生式$A \to \alpha$，我们将其替换为$A \to h^{-1}(\alpha)$，其中$h^{-1}(\alpha)$表示将$\alpha$中的每个符号通过$h^{-1}$映射回符号集上的串。
     2. 对于$G$中的每个产生式$A \to a_1 a_2 \cdots a_n$，我们加入产生式$A \to h^{-1}(a_1) h^{-1}(a_2) \cdots h^{-1}(a_n)$。

   • 开始符号：$S_{h^{-1}} = S$，即$L$的开始符号。

4. 证明新文法生成的语言是$h^{-1}(L)$：
   通过新的文法$G_{h^{-1}}$，我们可以生成$h^{-1}(L)$中的每个字符串。具体来说：

   • 假设$w = w_1 w_2 \cdots w_n \in L$，其中每个$w_i \in \Sigma$。
   • 在$G$中，$w$可以通过产生式规则生成。
   • 在$G_{h^{-1}}$中，通过将$w$中的每个符号$w_i$映射回原始符号，我们可以生成对应的字符串$h^{-1}(w_1) h^{-1}(w_2) \cdots h^{-1}(w_n)$。

   因此，$h^{-1}(L)$中的每个字符串都可以通过文法$G_{h^{-1}}$生成。

5. 结论：
   由于我们通过构造一个上下文无关文法$G_{h^{-1}}$来生成$h^{-1}(L)$，并且文法$G_{h^{-1}}$是上下文无关的（它仅仅是对$G$进行符号替换），因此$h^{-1}(L)$也是上下文无关语言。

因此，CFL对于逆同态运算是封闭的。

---

4.7.7 反转（Reversal）封闭

我们需要证明：如果$L$是一个上下文无关语言（CFL），那么$L^R$（即$L$的反转）也是上下文无关语言。

证明：

1. 假设：
   假设$L$是一个上下文无关语言，且$L$由文法$G = (V, \Sigma, R, S)$生成，其中$V$是非终结符集，$\Sigma$是终结符集，$R$是产生式规则，$S$是开始符号。我们需要证明$L^R$（即$L$中所有字符串的反转）也是上下文无关语言。

2. 构造新的文法：
   我们现在构造一个新的文法$G^R = (V, \Sigma, R^R, S^R)$，用来生成$L^R$。新的文法$G^R$的组成如下：

   • 非终结符集：$V$，即与$L$相同的非终结符集。

   • 终结符集：$\Sigma$，与$L$的终结符集相同。

   • 产生式规则集：$R^R$包括以下规则：

     1. 对于$G$中的每个产生式$A \to \alpha$，将其替换为$A \to \alpha^R$，其中$\alpha^R$表示字符串$\alpha$的反转。
     2. 例如，如果$A \to a_1 a_2 \cdots a_n$是$G$中的产生式，那么$A \to a_n a_{n-1} \cdots a_1$是$G^R$中的对应产生式。

   • 开始符号：$S^R = S$，即$L$的开始符号。

3. 证明新文法生成的语言是$L^R$：
   通过新的文法$G^R$，我们可以生成$L^R$中的每个字符串。具体来说：

   • 假设$w = w_1 w_2 \cdots w_n \in L$，其中每个$w_i \in \Sigma$。
   • 在$G$中，$w$可以通过产生式规则生成。
   • 在$G^R$中，$w$将被反转为$w_n w_{n-1} \cdots w_1$，即$w$中的每个符号都会在生成过程中被反转。

   因此，$L^R$中的每个字符串都可以通过文法$G^R$生成。

4. 结论：
   由于我们通过构造一个上下文无关文法$G^R$来生成$L^R$，并且文法$G^R$是上下文无关的（它仅仅是对$G$中的产生式规则进行了反转），因此$L^R$也是上下文无关语言。

因此，CFL对于反转运算是封闭的。

4.7.8 交（Intersection）不封闭

我们需要证明：上下文无关语言（CFL）对于交运算不封闭，即存在两个上下文无关语言$L_1$和$L_2$，使得它们的交集$L_1 \cap L_2$不是上下文无关语言。

证明：

1. 构造两个上下文无关语言$L_1$和$L_2$：
   我们选择以下两个上下文无关语言：

   • $L_1 = \{a^n b^n c^n \mid n \geq 0\}$，这是一个标准的上下文无关语言，它表示由$a$、$b$、$c$组成的字符串，其中每种字符的数量相同。
   • $L_2 = \{a^n b^m c^m \mid n \geq 0, m \geq 0\}$，这个语言包含任意数量的$a$，后面跟着相同数量的$b$，再后面跟着相同数量的$c$。

2. 求交集$L_1 \cap L_2$：
   现在，我们来求$L_1$和$L_2$的交集：

   • $L_1 \cap L_2 = \{a^n b^n c^n \mid n \geq 0\} \cap \{a^n b^m c^m \mid n \geq 0, m \geq 0\}$。
   • 交集的结果是$L_1 \cap L_2 = \{a^n b^n c^n \mid n \geq 0\}$，即所有$ a $、$ b $和$ c $的数量都相同的字符串。

   这个语言$L_1 \cap L_2$其实就是$L_1$，即$\{a^n b^n c^n \mid n \geq 0\}$。

3. $L_1 \cap L_2$是否是上下文无关语言：
   我们知道，语言$L_1 = {a^n b^n c^n \mid n \geq 0}$是非上下文无关的。原因是存在一个推理，可以证明使用上下文无关文法无法生成此语言：此问题可以通过泵引理等方法证明。

   因此，$L_1 \cap L_2$并不是上下文无关语言。

4. 结论：
   虽然$L_1$和$L_2$都是上下文无关语言，但它们的交集$L_1 \cap L_2 = \{a^n b^n c^n \mid n \geq 0\}$不是上下文无关语言。因此，CFL对于交运算是不封闭的。

4.7.9 补（Complement）不封闭

我们需要证明：上下文无关语言（CFL）对于补运算不封闭，即存在一个上下文无关语言$L$，使得$L$的补集$\overline{L}$不是上下文无关语言。

证明：

1. 构造上下文无关语言$L$：
   我们选择一个已知的上下文无关语言$L$：

   • $L = \{a^n b^n c^n \mid n \geq 0\}$，这是一个标准的上下文无关语言，它表示由$a$、$b$、$c$组成的字符串，其中每种字符的数量相同。

2. 构造$L$的补集$\overline{L}$：
   我们来求$L$的补集$\overline{L}$，即所有不属于$L$的字符串集合：

   • $L = \{a^n b^n c^n \mid n \geq 0\}$。
   • $\overline{L}$包含所有不是形如$a^n b^n c^n$的字符串。这意味着$\overline{L}$包含所有字符数量不相等或字符顺序不符合$a^n b^n c^n$模式的字符串。

3. 证明$\overline{L}$不是上下文无关语言：
   我们要证明$\overline{L}$不是上下文无关语言。考虑语言$L$中的字符串形态，它要求字符的数量严格匹配：$a$的数量、$b$的数量、$c$的数量相同。

   • 由于上下文无关文法无法在具有多个计数条件的语言中做出有效的限制（即无法处理像$a^n b^n c^n$这样的结构），$L$本身并不具备简单的反转特性。

   • 如果我们通过推理$L$的补集，会发现它的复杂度远远超过了上下文无关文法能够处理的范围。换句话说，$\overline{L}$包含了非常多的字符串，其中一些字符串无法用上下文无关文法来生成。例如，如果字符数量不匹配或顺序不符合，文法的设计会变得非常复杂且不可处理。

   • 我们这里可以用一个取巧的证明办法，根据德摩根律：$L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$, 因为交运算不封闭，并运算封闭，那么我们可以推出补运算是不封闭的

4. 结论：
   虽然$L$是一个上下文无关语言，但它的补集$\overline{L}$不是上下文无关语言。因此，CFL对于补运算是不封闭的。

5. Pushdown Automata

Pushdown Automata（PDA）是自动机的一种，它扩展了有限自动机（Finite Automaton, FA）的能力，引入了一个堆栈（Stack）作为额外的存储结构。PDA 特别适用于处理上下文无关语言（Context-Free Languages, CFLs），因为它能够在解析过程中记住之前的状态。

一个 Pushdown Automaton 可以通过五元组来表示：

$$PDA = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$$

其中：

• $Q$：状态集合，表示 PDA 的所有可能状态。
• $\Sigma$：输入字母表（也叫终结符）。
• $\Gamma$：堆栈字母表，表示堆栈中可能的符号。
• $\delta$：转移函数，定义了 PDA 在特定状态下如何根据输入符号和堆栈顶部符号转移到新的状态，以及如何改变堆栈的内容。
• $q_0$：初始状态，表示 PDA 开始的状态。
• $Z_0$：堆栈初始符号，通常是一个特殊的符号，用于标记堆栈的底部。
• $F$：接受状态的集合，PDA 只有进入一个接受状态时，才表示输入字符串被接受。

PDA 的工作过程可以简单描述为以下步骤：

1. 状态转移：PDA 根据当前状态、读取到的输入符号和堆栈顶部的符号来决定下一步的动作。PDA 的转移函数 $\delta$ 通常具有三个参数：

   • 当前状态 $q$。
   • 当前输入符号 $a$，如果当前没有输入符号可读取，则为空（即 $\epsilon$）。
   • 堆栈顶部符号 $X$，也可以是空的（即 $\epsilon$）。

   然后，PDA 会根据转移函数 $\delta$ 定义的规则来决定：

   • 转移到一个新状态。
   • 改变堆栈的内容（压入或弹出符号）。

2. 堆栈操作：堆栈是 PDA 的一个关键特性。它允许自动机记住状态信息，处理递归或嵌套结构（如括号匹配、算数表达式的解析等）。堆栈的操作包括：

   • Push：将一个符号压入堆栈。
   • Pop：将堆栈顶部的符号弹出。
   • No operation (NOP) ：不对堆栈进行任何操作。

3. 接受条件：PDA 的接受有两种方式：

   • 接受状态：当 PDA 进入一个接受状态 $q_f \in F$ 并且输入已经完全读取时，表示接受输入字符串。
   • 空堆栈：当 PDA 的堆栈为空且已经完全读取输入时，也可以接受输入字符串。

PDA 的重要特性是能够接受上下文无关语言。上下文无关语言（CFL）是指可以通过上下文无关文法（CFG）生成的语言。而 PDA 可以通过其堆栈的机制来模拟 CFG 生成语言的过程。

举一个简单的例子，考虑一个上下文无关文法生成的语言：

$$L = \{ a^n b^n \mid n \geq 0 \}$$

这个语言由所有长度相等的由 $a$ 和 $b$ 组成的字符串组成。PDA 可以通过以下方式接受该语言：

• 初始时，PDA 的堆栈为空。
• 每读取一个 $a$，PDA 就将一个符号（例如 $A$）压入堆栈。
• 每读取一个 $b$，PDA 就从堆栈中弹出一个符号。
• 如果堆栈最终为空，并且没有更多输入字符，则接受输入。

考虑一个简单的 PDA 来接受语言 $L = \{a^n b^n \mid n \geq 0 \}$：

• 状态集合 $Q = \{q_0, q_1, q_f\}$
• 输入字母表 $\Sigma = \{a, b\}$
• 堆栈字母表 $\Gamma = \{A, Z_0\}$（$Z_0$ 为堆栈底部符号）
• 初始状态 $q_0$
• 初始堆栈符号 $Z_0$
• 接受状态 $F = \{q_f\}$
• 转移函数：
  • $\delta(q_0, a, Z_0) = (q_0, a Z_0)$（读取 $a$ 时，将 $a$ 压入堆栈）
  • $\delta(q_0, a, a) = (q_0, aa)$（读取 $a$ 时，将 $a$ 压入堆栈）
  • $\delta(q_0, b, a) = (q_1, \epsilon)$（读取 $b$ 时，从堆栈弹出 $a$）
  • $\delta(q_1, b, a) = (q_1, \epsilon)$（读取 $b$ 时，从堆栈弹出 $a$）
  • $\delta(q_1, \epsilon, Z_0) = (q_f, Z_0)$（当堆栈为空时，进入接受状态）

Pushdown Automaton（PDA）是一种能够处理上下文无关语言的计算模型，它通过引入堆栈这一额外存储结构来增强有限自动机的能力。PDA 的应用广泛，包括编译器中的语法分析、程序解析以及一些递归语言的处理。它可以分为确定性 PDA（DPDA）和非确定性 PDA（NPDA），其中非确定性 PDA 是最强大的，能够处理所有的上下文无关语言。

---

5.1 PDA的状态转移

PDA 的状态转移函数 δ 描述了在特定的输入符号和栈顶符号下，PDA 会如何进行状态转移，以及是否需要对栈进行操作。它可以表示为：
$$
\delta(q, a, X) = \{(p, \gamma)\}
$$
其中：

• $q$ 是当前状态。
• $a$ 是当前的输入符号（如果为空，则是ε，表示没有输入）。
• $X$ 是栈顶符号。
• $p$ 是转移后的状态。
• $\gamma$是栈操作，表示栈顶符号 X 被替换为字符串 $\gamma$（也可以是空字符串，表示栈顶符号被弹出）。

PDA 的状态转移不仅可以改变自动机的状态，还可以对栈进行操作。栈操作有以下几种形式：

• 推入（Push）：将一个符号压入栈中。
• 弹出（Pop）：从栈顶移除一个符号。
• 保持不变：栈顶符号不发生变化。

例如，假设当前的状态为 q₀，栈顶符号为 X，输入符号为 a，PDA 的状态转移规则可能是：

• $\delta(q₀, a, X) = \{(q₁, YX)\}$，表示如果处于状态 q₀，读入符号 a，栈顶为 X，那么自动机转移到状态 q₁，并将 Y 压入栈顶，原有的 X 保留在栈中。
• $\delta(q₀, \epsilon, X) = \{(q₁, \epsilon)\}$，表示如果当前没有输入符号（ε），且栈顶是 X，自动机转移到状态 q₁，并弹出栈顶的符号 X。

假设我们有一个 PDA，它的任务是接受语言 $L = \{a^n b^n | n \geq 0\}$（即由相同数量的 a 和 b 组成的字符串）。该 PDA 可以通过以下状态转移来工作：

1. 初始状态 q₀，栈为空，读取到 a 时，PDA 将 a 推入栈中。
2. 当 PDA 读取到 b 时，它会与栈顶的 a 配对，弹出一个 a。
3. 如果字符串中的 a 和 b 数量相等，栈会空，自动机转到接受状态 q₁。

具体的转移规则可能是：

• $\delta(q₀, a, \epsilon) = \{(q₀, a)\}$，即在状态 q₀，读取 a，将 a 压入栈中。
• $\delta(q₀, b, a) = \{(q₀, \epsilon)\}$，即在状态 q₀，读取 b，弹出栈顶的 a。
• $\delta(q₀, \epsilon, \epsilon) = \{(q₁, \epsilon)\}$，当输入读完且栈为空时，转移到接受状态 q₁。

通过这种方式，PDA 使用栈来“记住”输入中的 a，并在读取到 b 时进行配对，从而确保 a 和 b 的数量相等。

PDA 的状态转移是由当前状态、输入符号和栈顶符号决定的，它允许自动机在每个转移步骤中操作栈，进而能够处理更复杂的语言，如上下文无关语言。通过推入和弹出栈顶符号，PDA 可以模拟许多计算过程，例如平衡括号或匹配括号对等任务。

---

5.2 下推自动机接受的语言

下推自动机（PDA, Pushdown Automaton）可以通过两种方式来接受语言：以终态（final state）接受和以空栈（empty stack）接受。

以终态方式接受的语言

当 PDA 使用终态接受语言时，它通过进入某个特定的终态来判断输入是否被接受。具体来说，如果 PDA 在输入字符串完全读取完毕后，进入了某个 接受状态（或终态），那么这个字符串就被认为是被 PDA 接受的。

• 输入字符串通过 PDA 的状态转移函数进行处理。
• 当输入字符串的所有符号都被读取完毕，PDA 必须进入某个 接受状态（或终态）。如果 PDA 达到了这个接受状态，并且已经没有更多的输入符号，那么该字符串就被认为是被接受的。

这种接受方式类似于有限自动机（DFA 或 NFA），唯一的不同之处在于 PDA 在计算过程中使用了栈来存储中间信息，而不仅仅依赖状态来进行转移。

假设我们有一个 PDA，任务是接受语言 $L = \{ a^n b^n | n \geq 0 \}$。该 PDA 的工作方式可能是：

1. 在状态 $q_0$，当读取到 $a$ 时，将 $a$ 压入栈。
2. 当读取到 $b$ 时，弹出一个 $a$。
3. 输入完全读完，并且 PDA 进入了终态 $q_1$，如果栈为空（所有 $a$ 都已经被匹配），则接受这个字符串。

以空栈方式接受的语言

当 PDA 使用空栈方式来接受语言时，它并不依赖于终态的存在，而是依赖于栈的状态来判断输入是否被接受。具体来说，输入字符串被接受的条件是，当输入字符串完全读取完毕时，PDA 的栈必须为空。

• 在读取输入字符串的过程中，PDA 根据当前输入符号和栈顶符号来进行状态转移。
• 当输入字符串完全读取完毕后，PDA 不要求进入特定的接受状态，而是检查栈是否为空。如果栈为空，则认为该字符串被接受。

使用空栈方式的优点在于它能够仅依赖栈的内容来判断语言是否符合某种规则，而不必考虑终态的存在。

假设我们有一个 PDA，任务是接受语言 $L = \{ a^n b^n | n \geq 0 \}$，此时 PDA 以空栈方式接受。可能的状态转移如下：

1. 在状态 $q_0$，当读取到 $a$ 时，将 $a$ 压入栈。
2. 当读取到 $b$ 时，弹出栈顶的 $a$。
3. 输入字符串读完后，栈应该为空。如果栈为空，则接受该字符串。

这种方法没有要求 PDA 进入一个特定的接受状态，而仅仅依赖栈的状态来判断输入是否被接受。

以终态方式接受 vs. 以空栈方式接受

• 接受条件：以终态方式接受时，PDA 需要进入某个特定的接受状态；而以空栈方式接受时，PDA 需要栈为空。
• 栈的作用：无论是终态方式还是空栈方式，栈都用来存储中间信息，以便处理更复杂的语言。不同的是，终态方式可能在栈中保留数据，而空栈方式则强调栈最终必须为空。

两种接受方式的差异：

• 终态接受的语言：通常来说，终态接受的语言可以通过转换成一个有穷状态机（比如 NFA 或 DFA）来描述，尽管下推自动机在转换过程中使用了栈。
• 空栈接受的语言：如果一个语言可以由一个 PDA 使用空栈方式接受，那么这个语言是上下文无关语言（CFL, Context-Free Language）。上下文无关语言在形式语言与自动机理论中是 PDA 的经典应用之一。

实际上，这两种接受方式并不等价：

• 空栈接受的语言：比终态接受的语言的表达能力更强，因为空栈接受的 PDA 可以模拟上下文无关文法（CFG）来生成语言。
• 终态接受的语言：虽然也可以描述某些上下文无关语言，但它通常只能描述一些较为简单的上下文无关语言，或者是某些有限的模式。

通常，空栈接受方式更为常见和强大，因为它能直接描述上下文无关语言，而终态接受方式则较为有限。

结论：如果PDA $P_N$以空栈方式接受语言$L$，那么一定存在PDA $P_F$以终态方式接受$L$

---

5.3 PDA与CFG的等价性证明

在形式语言与自动机理论中，PDA（下推自动机，Pushdown Automaton）和 CFG（上下文无关文法，Context-Free Grammar）是紧密相关的，事实上，它们是等价的。也就是说，对于每一个上下文无关语言，都可以存在一个 PDA 来接受它，同时对于每一个 PDA 接受的语言，都可以构造出一个上下文无关文法。

这意味着，我们可以通过下推自动机和上下文无关文法之间的转换来证明它们的等价性。下面我将详细讲解 PDA 和 CFG 的等价性证明，主要分为两个部分：

1. PDA 和 CFG 等价性证明：从 PDA 到 CFG 的构造
2. PDA 和 CFG 等价性证明：从 CFG 到 PDA 的构造

---

从 PDA 到 CFG 的构造

假设我们有一个 PDA，它接受某个上下文无关语言 $L$。我们需要构造一个上下文无关文法 $G$，使得 $G$ 生成的语言就是 $L$。下面是构造的基本思路。

1. 构建一个文法的非终结符：文法的非终结符是由 PDA 的状态和栈符号构成的。具体来说，文法中的每个非终结符都表示 PDA 在某一状态下，通过一系列的栈操作可以推导出某种字符串。

   假设 PDA 的状态集合为 $Q$，栈字母表为 $\Gamma$，则文法中的非终结符通常是形式为 $[q, X]$ 的符号，其中：

   • $q \in Q$，表示 PDA 的一个状态。
   • $X \in \Gamma$，表示栈上的一个符号。

2. 文法的产生式：文法的产生式是根据 PDA 的转移函数来构造的。PDA 的转移函数通常表示为 $\delta(q, a, X) = { (p, \gamma) }$，其中：

   • $q$ 和 $p$ 是 PDA 的状态。
   • $a$ 是输入符号。
   • $X$ 是栈顶符号。
   • $\gamma$ 是栈操作，可以是栈符号的一个串，表示将栈顶的 $X$ 替换为字符串 $\gamma$。

   对应的文法产生式有两种类型：

   1. 通过栈操作推出字符串：

      • 如果 $\delta(q, a, X) = \{ (p, \gamma) \}$，则可以有一个产生式：
        $$ [q, X] \rightarrow a[p, \gamma] $$
        这表示在状态 $q$，读取符号 $a$，栈顶是符号 $X$ 时，可以推导出字符串 $a$，然后转移到状态 $p$，栈操作替换成 $\gamma$

   2. 通过状态转移推导空符号：

      • 如果有一个 $\delta(q, \epsilon, X) = \{(p, \epsilon)\}$，表示没有输入符号并且弹出栈顶符号 $X$，则产生式为：
        $$ [q, X] \rightarrow [p, \epsilon] $$
        这表示在状态 $q$ 时，栈顶符号为 $X$，并且没有读取任何输入符号，可以通过弹出栈顶符号，转移到状态 $p$。

3. 文法的开始符号：文法的开始符号通常由 PDA 的初始状态和栈初始符号组成。例如，如果 PDA 的初始状态是 $q_0$，栈的初始符号是 $Z_0$，则文法的开始符号为 $[q_0, Z_0]$。

通过上述步骤，我们可以为每个 PDA 构造出一个等价的上下文无关文法 $G$，使得 $L(G)$ 等于 PDA 所接受的语言 $L(PDA)$。

---

从 CFG 到 PDA 的构造

接下来，我们要证明对于每一个上下文无关文法 $G$，都可以构造出一个等价的 PDA 来接受由该文法生成的语言。构造过程的基本思路是模拟文法的推导过程。

构造 PDA 的基本思路：

1. PDA 的状态集合：PDA 的状态集合包含两个状态：一个是初始状态 $q_0$，另一个是接受状态 $q_1$。

2. 栈操作的设计：栈用于模拟文法的推导过程。在文法中，每个非终结符都有一个产生式，而在 PDA 中，栈顶符号将被替换成对应的右侧部分。具体来说，当 PDA 读取输入符号时，它会根据当前栈顶符号（非终结符或终结符）和当前输入符号执行相应的栈操作。

   • 对于终结符：当 PDA 遇到一个终结符（比如文法的终结符 $a$）时，它会检查栈顶是否是该终结符。如果是，则弹出该符号并读取下一个输入符号。
   • 对于非终结符：当 PDA 遇到一个非终结符（比如文法的非终结符 $A$），它会将栈顶的 $A$ 替换为该非终结符的右侧产生式。

3. PDA 的状态转移：

   • 读取终结符：当 PDA 遇到输入符号 $a$，栈顶为 $a$ 时，执行操作：弹出 $a$，读取下一个输入符号。
   • 应用产生式：当 PDA 遇到栈顶是非终结符 $A$ 时，选择文法中的某个产生式 $A \rightarrow \alpha$，并将 $\alpha$ 推入栈中。

4. PDA 的接受条件：PDA 在输入字符串被完全读取完毕后，如果栈为空，则接受该字符串。

根据上述过程，我们可以为每个上下文无关文法 $G$ 构造一个等价的 PDA，使得 PDA 接受的语言恰好是 $L(G)$，即文法 $G$ 生成的语言。

通过从 PDA 到 CFG 的构造，我们可以证明每个 PDA 接受的语言是上下文无关语言。而通过从 CFG 到 PDA 的构造，我们可以证明每个上下文无关语言都可以被某个 PDA 接受。这样，我们就证明了 PDA 和 CFG 在语言的接受能力上是等价的。换句话说，它们都可以接受所有的上下文无关语言。

---

5.4 DPDA

DPDA（Deterministic Pushdown Automaton，确定性下推自动机）是下推自动机（PDA）的一种特殊类型。与普通的 PDA 不同，DPDA 的转移是确定性的，即在任何给定的时刻，状态和栈顶符号以及当前输入符号的组合只能导致一个确定的转移。这个特性使得 DPDA 相较于一般的 PDA 更加有限，并且在一些语言的接受能力上有所限制。

DPDA 与 PDA 的区别：

普通的 PDA 在处理状态转移时，可能存在多个可行的转移路径，这通常是因为在同一状态下、相同输入符号和栈顶符号的条件下，PDA 可以选择不同的栈操作（推入不同的栈符号或弹出栈符号）。这使得 PDA 是非确定性的。

而在 DPDA 中，给定一个输入符号、当前状态和栈顶符号的组合时，转移是唯一的，只有一种可能的状态和栈变换。这种确定性意味着在任何时刻，DPDA 都只能做出一个明确的选择，因此称为确定性下推自动机。

DPDA 是 PDA 的一种特殊类型，其定义如下：

• 状态集合 $Q$：有限的状态集合。

• 输入字母表 $\Sigma$：有限的输入符号集。

• 栈字母表 $\Gamma$：有限的栈符号集。

• 转移函数 $\delta$：转移函数 $\delta(q, a, X)$，其中 $q$ 是当前状态，$a$ 是当前输入符号（可以是空符号 $\epsilon$），$X$ 是栈顶符号。与普通 PDA 不同，对于每对 ($q, a, X$)，$\delta$ 中最多只有一个转移，这使得它是确定性的。

  $\delta: Q \times (\Sigma \cup {\epsilon}) \times \Gamma \rightarrow Q \times \Gamma^*$，意味着从某个状态 $q$，读取输入符号 $a$ 和栈顶符号 $X$，转移到新的状态并且修改栈的内容。

• 初始状态 $q_0$：自动机的起始状态。

• 初始栈符号 $Z_0$：栈的初始符号。

• 接受状态 $F$：一个接受状态的集合，可以是空集（即仅以栈为空来接受）。

DPDA 在读取输入符号的过程中，遵循以下步骤：

1. 读取输入：从输入字符串中逐个读取字符。

2. 栈操作：

   • 推入栈：在某些转移中，DPDA 会将符号压入栈。
   • 弹出栈：在其他转移中，DPDA 会从栈顶弹出符号。
   • 不操作：在某些情况下，DPDA 会保持栈不变。

   DPDA 的关键特点是，在每次状态转移时，必须有一个唯一的选择，不允许有多个转移选项。

3. 接受条件：

   • 终止状态：如果 DPDA 在读取完所有输入符号后进入某个接受状态（$q \in F$），那么该字符串被接受。
   • 空栈接受：如果 DPDA 在读取完所有输入符号后栈为空（即栈没有任何符号），则该字符串也被接受。

DPDA 能够接受的语言是确定性上下文无关语言（D-CFLs）。这些语言是上下文无关语言的一个子集，限制了语言的结构，使得它们可以被确定性下推自动机处理。虽然 PDA 可以接受所有上下文无关语言（CFLs），但 DPDA 只能接受其中的一部分。

确定性上下文无关语言相比一般的上下文无关语言有更严格的结构要求。例如，DPDA 无法处理某些语言，这些语言是上下文无关的，但由于其结构复杂（例如，需要“回溯”或存在“多重选择”），无法通过确定性方式来接受。

---

举个例子：

• 语言 $L = \{ a^n b^n | n \geq 0 \}$ 是一个典型的上下文无关语言，它可以被 DPDA 接受。DPDA 可以通过以下方式处理：

  1. 在栈中推入 $a$。
  2. 遇到 $b$ 时弹出栈中的 $a$，并继续。
  3. 输入完全结束时，如果栈为空，则接受该字符串。

• 语言 $L = \{ a^n b^n c^n | n \geq 0 \}$ 是一个上下文无关语言，但它不能被任何 DPDA 接受，因为它需要同时处理 $a$、$b$ 和 $c$ 的数量，这要求下推自动机能够在不同的符号之间进行回溯选择，而 DPDA 无法做到这一点。

特性	PDA（下推自动机）	DPDA（确定性下推自动机）
确定性	非确定性	确定性
语言类型	上下文无关语言（CFL）	确定性上下文无关语言（D-CFL）
转移函数	可能有多个转移	对每一组合，最多只有一个转移
栈操作	可以有多个栈操作	对每一输入符号和栈顶符号，栈操作唯一
接受条件	终态接受、空栈接受	终态接受、空栈接受

---

5.5 正则语言与DPDA

• 正则语言（Regular Languages）是最简单的语言类别，可以通过有限自动机（DFA 或 NFA）来接受，也可以通过正则表达式来描述。正则语言的特点是它们的结构非常简单，不需要栈来存储额外的信息，自动机可以在处理时通过状态转移来完成任务。

• 上下文无关语言（Context-Free Languages，简称 CFLs）是比正则语言更复杂的语言类别。它们可以通过上下文无关文法（CFG）来定义，并且通常需要栈来存储和操作语法信息。上下文无关语言的典型代表就是编程语言中的语法结构，如表达式解析、函数调用等。

• DPDA（Deterministic Pushdown Automaton，确定性下推自动机）是一种具有栈的自动机，用于接受上下文无关语言。DPDA 是 PDA（下推自动机）的一种特殊形式，区别在于 DPDA 的转移是确定性的，即在每一个状态和栈顶符号以及输入符号的组合下，DPDA 的行为是唯一的。

正则语言比上下文无关语言简单，通常不需要栈来处理。例如，正则语言可以通过 DFA 或 NFA 来接受，利用有限的状态和简单的转移规则即可完成。

• 正则语言 是上下文无关语言的子集，这意味着每个正则语言都可以是上下文无关的。
• 因为 DPDA 用来接受上下文无关语言，所以它能够接受所有的正则语言。实际上，正则语言的结构不需要栈，因此我们可以认为 DPDA 接受正则语言时，栈是“过度”的，它实际上不需要使用栈来完成这个任务。

为什么 DPDA 可以接受正则语言？

• 有限自动机（DFA 和 NFA）是最简单的自动机，它们仅使用状态来处理输入，而不需要栈。这些自动机能够接受正则语言。
• DPDA 比 DFA 更强大，因为它有栈可以使用。然而，对于正则语言来说，栈并没有实际的用途。DPDA 在接受正则语言时，仅仅依赖状态转移，而栈并没有被利用。因此，虽然正则语言可以被 DFA 接受，DPDA 也能接受它们，但 DPDA 是过度使用栈的，因为它实际上不需要栈的帮助。

总结：所有的 正则语言 都可以通过 DPDA 接受。对于正则语言来说，DPDA 不必使用栈，DPDA 是一种比 DFA 更强的模型，但它的栈功能在正则语言中是多余的。

DPDA 的限制

虽然 DPDA 可以接受 确定性上下文无关语言，但它的能力比一般的 PDA 强度要小。一个普通的 PDA 可以接受 所有的上下文无关语言（CFLs），而 DPDA 只能接受其中的一部分，通常是那些 结构较为简单且具有确定性的 上下文无关语言。某些上下文无关语言，由于它们的结构过于复杂，DPDA 无法接受。

• 正则语言 是 最简单 的语言，可以通过 有限自动机（DFA） 来接受。由于正则语言的简单性，DPDA 可以接受这些语言，但它的栈功能并没有被实际利用。
• DPDA 能接受 所有正则语言，但它的能力不仅仅局限于此，DPDA 可以接受一些更复杂的语言——确定性上下文无关语言（D-CFLs）。
• DPDA 不能接受 所有的上下文无关语言，它只能接受 确定性上下文无关语言。对于那些复杂的上下文无关语言，特别是需要非确定性栈操作的语言，DPDA 无法接受。

总结：正则语言可以被 DPDA 接受，因为正则语言的结构不需要栈，DPDA 的能力足以接受正则语言。然而，DPDA 并不只接受正则语言，它也可以接受一些更复杂的语言，但它的能力是有局限的，不能接受所有的上下文无关语言。

---

5.6 语言类的关系

全语言（Recursively Enumerable Languages，RE），也叫做 递归可枚举语言（RE），是形式语言理论中的一个非常宽泛的类别，几乎包含了所有可以被某种计算模型识别的语言。它是语言类中最广泛的一类。全语言包含了所有可以被 图灵机 识别的语言。（后面章节讲解）

在形式语言的分类中，语言类之间的关系可以通过包含关系来描述。具体来说：

• 正则语言（Regular Languages） 是最简单的语言类，所有正则语言都是上下文无关语言（CFL）的子集。正则语言不能表示复杂的嵌套结构。
• 上下文无关语言（CFL） 比正则语言更复杂，可以表示更多的语言结构。
• 确定性上下文无关语言（DCFL） 是上下文无关语言的一个子集。并非所有上下文无关语言都是确定性上下文无关语言。
• 全语言（RE） 是最广泛的语言类，包含了所有可以由图灵机识别的语言。它包含了上下文无关语言、正则语言等，但并不要求这些语言能够被判定。

语言类别	特征	示例
全语言（RE）	包含所有递归可枚举语言，可以被图灵机识别，但不一定是可判定的。	所有能够通过图灵机识别的语言。
上下文无关语言（CFL）	可以由上下文无关文法（CFG）生成，可以通过 PDA 识别。	括号匹配，$a^n b^n$， $S \to aSb | \varepsilon$
确定性上下文无关语言（DCFL）	可以由确定性下推自动机（DPDA）识别，是 CFL 的子集。	$a^n b^n$，$a^n b^n c^n$（非确定性上下文无关语言）
正则语言（Regular Languages）	可以由有限自动机（DFA 或 NFA）识别，最简单的语言。	$a^n b^n$，正则表达式 $a^* b^*$

• 正则语言 是 最简单 的语言，可以通过 有限自动机（DFA） 来接受。由于正则语言的简单性，DPDA 可以接受这些语言，但它的栈功能并没有被实际利用。
• 上下文无关语言 比正则语言更复杂，可以表示更多的语言结构。
• 确定性上下文无关语言 是上下文无关语言的一部分，它们比一般的上下文无关语言更容易处理。
• 全语言 是最广泛的语言类，包含了所有可以由图灵机识别的语言。

6. 图灵机（Turing Machine）

图灵机是由数学家艾伦·图灵（Alan Turing）于1936年提出的一个理论计算模型，旨在为“可计算性”提供一个精确的定义。图灵机本质上是一个抽象的机器，用来模拟任何形式的计算过程。它由以下几个部分组成：

1. 无限长的带子：带子被分为一格一格，每个格子可以存储一个符号，符号来自一个有限的字母表。带子可以在左右两个方向上移动，并且可以反复读取和修改。

2. 读/写头：在带子上移动并读取符号，或者写入符号。读写头每次只能操作一个格子。

3. 状态控制器：图灵机有一个有限的状态集，其中包括一个初始状态、若干个中间状态和一个或多个接受状态（终止状态）。每个状态都可能有不同的行为，包括：读取当前格子的符号，写入新符号，移动带子，或者转到下一个状态。

4. 转移函数：定义了图灵机的行为。它规定了在某个状态下，根据当前读取的符号，图灵机应当写入什么符号，移动到哪个方向，并转移到哪个状态。

图灵机的计算过程是通过状态控制器与带子上符号的交互来进行的。如果图灵机在某个状态下停下来且没有任何进一步的规则，或者进入一个终止状态，则计算结束。

图灵机是计算理论中的核心工具，它定义了“可计算性”的概念。图灵机不仅可以模拟任何形式的计算过程，也可以用来定义不同类型的语言（如正规语言、上下文无关语言、递归可枚举语言等）。以下是一些图灵机与其他语言之间的关系：

1. 正规语言（Regular Languages）：正规语言可以由有限自动机（DFA/NFA）识别，而图灵机能够识别更广泛的语言。事实上，所有正规语言都可以通过图灵机识别，但并非所有图灵机能识别的语言都是正规语言。

2. 上下文无关语言（Context-Free Languages, CFLs）：上下文无关语言可以由上下文无关文法生成，而图灵机的能力远超上下文无关文法。每个上下文无关语言都可以由图灵机识别，但图灵机可以识别更多类型的语言，包括无法由上下文无关文法生成的语言。

3. 递归可枚举语言（Recursively Enumerable Languages）：这些是所有可以被图灵机识别的语言。图灵机不仅能识别这些语言，还能生成它们的所有字符串，但不能保证总是能在有限的时间内做出决定。递归可枚举语言的一个例子是图灵机的输出语言。

4. 递归语言（Recursive Languages）：递归语言是那些能够由图灵机在有限时间内决定的语言。这些语言不仅可以被图灵机识别，还可以保证图灵机总是在有限时间内做出决定，即图灵机总是停机。

图灵机是计算理论中的核心概念，它是一种抽象的计算模型，用来定义“可计算性”。它的强大之处在于能够识别递归可枚举语言，而在更小的类别中（如正规语言、上下文无关语言）有专门的机器来识别。图灵机的理论研究帮助我们理解了哪些问题是可以计算的，哪些是不可计算的。

7. 偷偷说

费了很大力气，终于把形式语言与自动机这门课的内容更完了。这门课的笔记的字数竟然超过了操作系统😂我觉得自动机的学习还是在关注几个模型上面还有正则语言和上下文无关语言性质的理解上。刷题的话，还是从九州大学的自动机过去问开始入手是最合适的，当然Sisper的课后书的例题也非常值得去做。

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio