ch3-4

数学基础

1. 字母表和字符串
   语言（language） 是一个 字符串（string） 的集合，例如：{ cat, dog, … }，字符串是由 字母表（alphabet） 中的字母组成的序列。一个语言是字母表中所有字符串的子集。字母表示例：𝚺 = { a, b, c, d, …, z }
   字符串示例：cat, dog, …
2. 字符串操作
   连接：例如，𝑤1 = 𝑎𝑎𝑏𝑏， 𝑤2 = 𝑏𝑏𝑎𝑎
   连接结果：𝑤1𝑤2 = 𝑎𝑎𝑏𝑏𝑏𝑏𝑎𝑎
   反转：例如，𝑤 = 𝑎1𝑎2𝑎3𝑎4
   反转结果：= 𝑎4𝑎3𝑎2𝑎1
   长度：例如，𝑤 = 𝑎1𝑎2𝑎3𝑎4
   字符串长度：|𝑤| = 4
3. 空字符串与子字符串
   空字符串：𝜖
   |𝜖| = 0，𝜖𝑎𝑎𝑏𝑏 = 𝑎𝑎𝑏𝜖𝜖𝑏 = 𝑎𝑎𝑏𝑏𝜖 = 𝑎𝑎𝑏𝑏
   子字符串：连续字符的子序列例如：𝑎𝑏𝑏𝑎𝑏, 𝑎𝑏𝑏𝑎𝑏, 𝑎𝑏𝑏𝑎𝑏, 𝑎𝑏𝑏𝑎𝑏
4. 前缀 prefix 和后缀 suffix：例如，𝑤 = 𝑢𝑣，其中 𝑢 是前缀，𝑣 是后缀
   𝑎𝑏𝑏 的前缀包括：𝜖, 𝑎, 𝑎𝑏, 𝑎𝑏𝑏
   𝑎𝑏𝑏 的后缀包括：𝑎𝑏𝑏, 𝑏𝑏, 𝑏, 𝜖
5. Power
   = 𝑤𝑤…𝑤（n个）
   = 𝜖
6. Kleene Star
   给定字母表 𝚺 = { 𝑎, 𝑏 }，则 𝚺 = { 𝜖, 𝑎, 𝑏, 𝑎𝑏, 𝑎𝑏𝑏, 𝑎𝑎𝑏, … }
7. Plus：𝚺+ = 𝚺 − {𝜖}
8. 一个语言是 𝚺∗ 的任意子集，例如：{𝜖}, {𝜖, 𝑎, 𝑏}, …
9. 对于 ， 有以下运算：
   
   
   
   
   
   
   ，
   Star-Closure:

DFA

一个 DFA 是一个五元组：

• ：状态的有限集合

• ：输入字符的有限集合（字母表）

• ：状态转移函数，，例如

• ：起始状态

• ：终止状态的有限子集

DFA 最小化

最小化 DFA 的步骤：

1. 分辨最终状态（图例为两个圈）和非最终状态，分为两组。

2. 判断状态之间的转移关系，是否属于同一组，进行进一步的分组，直到无法再分。

步骤	分组	注解
Step 1		分辨最终状态和非最终状态
Step 2		和 在同组, 不在
Step 3		没有可以再分的组

最小化结果如右图所示：

DFA Bi-Simulation

检查两个 DFA 是否等价，即
步骤：给定输入字符串，分别让 和 同时评估该字符串，只有当两个 DFA 都到达终态时，两个 DFA 才被认为等价。

NFA

NFA 允许在某些状态下有多个转移选择。 例如，给定字符串 aa，第一个转移有两个选择。如果一个选择失败，则尝试其他选择。 NFA也允许 **-转移** ，即可以在没有读取任何输入的情况下通过 转移到下一个状态。

DFA 和 NFA 转换

每个 NFA 都有一个等价的 DFA，但并不是每个 DFA 都有等价的 NFA。通过子集构造法，可以将 NFA 转换为等价的 DFA。

子集构造法

**子集构造法是一种用于将 NFA 转换为 DFA 的方法。**该方法通过创建 NFA 状态的集合来形成 DFA 的状态，并重新定义转移规则。在子集构造法中，DFA 的每个状态对应着 NFA 状态集的一个子集。通过这种方法，NFA 可以被转换成一个确定性的 DFA。
如果任意 是终止状态，那么其所在的 S 也是 DFA 的终止状态。

例如：

🌟由于 DFA 的状态由 NFA 状态的集合组成，因此一个具有 个状态的 NFA 可以被转换为至多 个状态的 DFA。

正则语言

给定一个DFA：，由 DFA 接受的语言可表示为：

给定一个NFA：，由 DFA 接受的语言可表示为：

如果存在一个DFA/NFA 使得 ，则称语言 为正则语言（Regular Language）。

闭包性质（Closure Properties）

给定两个正则语言 和 ，则以下运算的结果仍是正则语言：

1. 并（Union）：
   

2. 连接（Concatenation）：
   

3. 反转：
   

4. Kleene Star：
   

5. 补（Complement）：
   

6. 交（Intersection）：
   
   以上都可以通过画出 DFA/NFA 来证明是正则语言。而有了以上性质基础，可直接通过 来证明交集运算同样是正则语言。

正则表达式

基本正则表达式（Primitive Regex）：空集 ，空字符串 ，单个字符 。

如果两个正则表达式表示相同的语言，那么它们是等价的。换句话说，对于任意输入字符串，如果它被第一个正则表达式接受，那么它也会被第二个正则表达式接受，反之亦然。

Thompson 构造法

Thompson 构造法将一个正则表达式转化为一个与之等价的非确定有限状态机（NFA）。 过程如上小节一系列图和下图所示。

正则表达式与正则语言的等价性

1. 任何正则表达式都表示一个正则语言（== DFA/NFA）证明是正则表达式：可以表示为正则语言，即一定被 DFA/NFA 接收，也就是能把图画出来
   

2. 任何正则语言(== DFA)都可以由正则表达式表示
   

Pumping Lemma 泵引理

如果 是一个无限正则语言，则必定存在一个整数 ，使得：对于任何字符串 ，且 ，可以将 分解为：

满足以下条件：

3. 对于任意 ，字符串

使用泵引理证明 不是正则语言

假设 是正则语言，则存在一个整数 ，对于任意字符串 ，可分解为：

则令 ，有：

这与 为正则语言的假设矛盾，因此 不是正则语言。

上下文无关文法

上下文无关文法（Context-Free Grammar, CFG）是一个四元组：
其中：

• ：有限的非终结符（non-terminals）集合。

• ：有限的终结符（terminals）集合，满足 。

• ：起始非终结符（start non-terminal）。

• ：产生式规则（production rules），其形式为 ，其中 ，。

推导（Derivation, ）
假设，则 。若文法是明确的，可以简写为。
*上下文无关：A的替换与它邻近的元素无关。

多步推导（）
示例:
文法规则：
推导过程：
详细步骤：

上下文无关语言
定义：
例如正则表达式 的文法规则：
，，

最左推导（Left-Most Derivation, ）
在每一步的推导中，我们替换最左边的非终结符。

最右推导（Right-Most Derivation, ）
在每一步的推导中，我们替换最右边的非终结符。

语法分析树
推导是构建语法分析树（parse tree）的过程。

文法的歧义性（Ambiguity）
如果一个字符串有两个不同的推导树，则该文法是歧义的。

习题课

ch3

ch4.1

写出下面语言的CFG：

L = { w ∣ w is a string of balanced parentheses } （括号匹配）

且 或
注：可表示为 或

且

---

• ← Previous Post
• Next Post →

---