计算理论导引

第一部分 自动机与语言

---

第一章 正则语言

1.1有穷自动机

1.1.1 有穷自动机的形式化定义

有穷自动机是一个5元组（Q，Σ，δ，q0，F）

1. Q是一个有穷集合，称为状态集

2. Σ是一个有穷集合，称为字母表

3. δ：Q×Σ->Q，是转移函数

4. q0∈Q，是起始状态

5. F含于Q，是接受状态集

1.1.2 计算的形式化定义

设M = （Q，Σ，δ，q0，F）是一台有穷自动机，W = W1W2W3…Wn是一个字符串并且其中任意wi是字母表Σ的成员。如果存在Q中的状态序列r0,r1,…,rn,满足下述条件：

1. r0 = q0 机器从开始状态开始
2. δ（ri,W(i + 1)） = r(i + 1),i = 0,…,n - 1 机器按照转移函数从一个状态到一个状态
3. rn∈F 如果机器结束在接受状态，则接受它的输入

则M接受串W

如果A = {W | M接受W}，则称M识别语言A

如果一个语言被一台有穷自动机识别，则称它为正则语言。

1.1.3 设计有穷自动机

1. 给每一种可能的字符串信息设计一个状态
2. 通过观察如何根据读到的符号从一种可能性到另一种可能性来设计转移
3. 接下来，把起始状态设置为对应于到现在为止还没有看到与任何符号（空串ε）相关联的可能性的状态

1.1.4 正则运算

设A和B是两个语言，定义正则运算并、连接和星号如下：

• 并：A∪B = {x | x∈A或x∈B}
• 连接：A▪B = {xy | x∈A且y∈B}
• 星号：A* = {x1x2x3…xk | k >= 0 且每一个xi∈A} ——>一元运算

一般来说，如果把某种运算应用于一个对象集合的成员得到的对象仍在这个集合中，则称这个对象集合在该运算下封闭。

1.2 非确定性

非确定性是确定性的推广-> 因此每一台确定性有穷自动机自动地是一台非确定性有穷自动机

NFA与DFA的不同点：

1. 在NFA中，一个状态对应于字母表中的每一个符号可能有0个、1个或多个射出的箭头
2. 在DFA上，转移箭头上的标号是取自字母表中的符号；NFA中则可以取自ε
3. 一般来说，NFA的箭头可以标记字母表中的符号或ε。从一个状态可能射出0个、1个或多个带有标号ε的箭头

可以把非确定性看做是若干独立的“过程”或“线程”，即能同时运行的一类**并行运算**，如果这些子过程至少有一个接受，那么整个计算接受。

1.2.1 非确定性有穷自动机的形式化定义

非确定性有穷自动机是一个5元组（Q，Σ，δ，q0，F）

1. Q是一个有穷集合，称为状态集
2. Σ是一个有穷集合，称为字母表
3. δ：Q×（Σ∪{ε}）->（Q的幂集），是转移函数
4. q0∈Q，是起始状态

1.2.1 NFA与DFA的等价性