形式语言与自动机
陈文宇
电子科技大学计算机科学与工程学院
cwy@uestc.edu.cn
教材,
形式语言与自动机
(陈文宇 欧齐 程炼）
人民邮电出版社
参考书：
形式语言与自动机理论
（蒋宗礼 清华大学出版社）
形式语言与自动机
（陈有祺 南开大学出版社）
?形式语言和自动机的理论是计算机科
学的理论基础 。 这些理论来源于
(1) Chomsky对自然语言的研究；
(2) ALGOL 60语言的语法描述方式；
(3)Kleene对自动机的研究；
? 早在 20世纪五十年代, 在研究如何使, 自然语
言, 符号化 （ 即形式化 ） 的过程中, 产生并发
展了, 形式语言与自动机, 的理论 。 不久, 人
们就发现该理论与计算机科学中所创立和使用
的程序设计语言具有密切的关系 （ 比如, 可以
用于描述程序设计语言的词法和语法规则 ） 。
从此以后, 形式语言与自动机的理论和方法的
研究, 受到了越来越多科学家的重视 。
? 形式语言和自动机的理论已经成为计算机
科学的理论基础, 其应用范围已被扩展到生
物工程, 自动控制系统, 图象处理与模式识别
等许多领域 。
? 实际上,, 形式语言与自动机, 的理论除了在
计算机科学领域中的直接应用外, 对于 计算机
科学人才的计算思维能力的培养, 具
有重要作用 。
?形式化描述和抽象思维能力，
逻辑思维方法。这种能力就是
计算思维能力或计算机思维能
力。
第 1章 绪论
?本章将对形式语言和有限自动机理论
中所需的数学基础知识作扼要的介绍。
内容包括 集合及其运算、关系、证明
的方法、图与树 的概念；以及一些 常
用术语 和 形式语言与自动机的发展 。
第 1章 绪论
? 1.1集合及其运算
? 1.2 关系
? 1.3 证明和证明的方法
? 1.4 图与树
? 1.5 语言
? 1.6 常用术语
? 1.7 形式语言与自动机的发展
1.1集合及其运算
?一些没有重复的对象的全体称为 集
合 (set),而这些被包含的对象称为
该集合的 元素 (element)。
?集合中元素可以按 任意的顺序 进行
排列。一般，使用大写英文字母表
示一个集合。
列举法
?对于元素个数较少的集合，可以采
用列举法，即将集合的所有元素全
部列出，并放在一对花括号中。例
如集合 A ={0,1,2,3,4,5,6，
7,8,9},表示集合 A由 0,1,2，
3,4,5,6,7,8,9共 10个元素
组成。
命题法
? 对于集合元素较多的或者是由无穷多个元素
组成的集合，可以使用集合形成模式 {x |
P(x)}进行描述，其中,x表示集合中的任一
元素,P(x)是一个谓词，对 x进行限定,{x |
P(x)}表示由满足 P(x)的一切 x构成的集合。
可以使用自然语言，或者数学表示法来描述
谓词 P(x)。
? 例如,{n | n是偶数 }，或者 {n | n mod 2 = 0}，
都表明了一个由所有偶数组成的集合。
集合的基数
? 如果集合 A包含元素 x（ 也称元素 x在集合 A
中），记为 x ? A。 否则 x ? A。
? 对于任意的有穷集合 A,使用 |A|表示该集合
包含的元素的 个数,也称 基数 或 势 。显然，
|A| = 0 ? A = ? 。
? 如果一个集合中的元素个数是有限的，称该
集合为 有穷集合 。如果一个集合包含的元素
是无限的，称该集合为 无穷集合 。无穷集合
又分为可数集 (如自然数集，有理数集 )和不
可数集 (如实数集 )。
定义 1-1 子集
? 设 A,B是两个集合，如果集合 A中的每
个元素都是集合 B的元素，则称集合 A
是集合 B的子集，集合 B是集合 A的包集。
记作 A? B,或 B? A。
? 设 A,B是两个集合，如果 A ? B, 且 ?x
? B,但 x? A,则称 A是 B的真子集，
记作 A? B。
定义 1-2 集合的运算
? 并，交,注意多个集合并、交的写法
? 差,注意它不要求两个集合存在子集
关系
? 补集,论域的概念
Ai
n
i 1?
?
几个结论
? A = B iff A ? B且 B ? A。
? 如果 A是有穷集，且 A ? B, 则 |A| < |B|。
? 对于无穷集，这个结论并不适用。如奇
数集是自然数集的真子集，自然数集与
奇数集之间存在一一对应关系，即它们
的基数相等。该映射可表示为：
f(x) = 2x-1
定义 1-3 幂集
? 设 A为一个集合，那么 A的 幂集 为 A的所
有子集 组成的集合，记为 2A,即 2A={B |
B ? A}。
?例如，集合 A={1,2,3},则 A的幂集为,
2A={?,{1},{2},{3},{1,2},{1，
3},{2,3},{1,2,3}}。
? 当集合 A为有穷集时，如果集合 A包含的元素
个数为 n,那么集合 2A的元素个数 (集合 A的所
有子集的个数 )为 2n,这就是称 2A为集合 A的
幂集的原因。
定义 1-4 笛卡儿积
? 集合 A和 B的笛卡儿乘积使用 A ? B表示
（也简记为 AB）
? A ? B = {(a,b) | a ? A 且 b ? B}。
例
? 设 A = {a,b,c},B = {0,1},
则 A ? B ={(a,0),(a,1),(b,0),(b,1),(c,0),
(c,1)}.
? 也可根据约定记为：
A ? B={a0,a1,b0,b1,c0,c1}
而 B ? A={(0,a),(0,b),(0,c),(1,a),(1,b),
(1,c)}
思考
?什么情况下,A ? B = B ? A?
?1） A = B
?2） A = ?或 B = ?
?3） …
练习 (见习题 )
?1(2)(3)(4)
?2(1)(3) (5) (6) (10)
习题评讲
1(2) 2{1,2,3,4} ={?,{1},{2},{3},{4},{1,2},{1,
3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,
2,4},{2,3,4},{1,2,3,4}}
(3) { 1,2,3,4,5,6,7,8,9,10}
{4} {{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,
6},{1,4,5},{2,3,5},{1,2,3,4}}
注意：没有 {5,5}
习题评讲 (续 )
2(1) {x | x ? N且 1 ? x ? 100}
(3) 2{1,2,3,4}={B | B ? {1,2,3,4}}
(5) {x | x > 0且 x mod 2 = 1}
习题评讲 (续 )
2(6) {(x,y) | x,y ? [4,9]且 x + y = 10}
即 {(4,6),(6,4),(5,5)}
(10) {B | B ? {1,2,...,10}且 ?x = 10,x
? B}
1.2 关系
?1.2.1 二元关系
?1.2.2 等价关系与等价类
?1.2.3 关系的合成
1.2.1 二元关系
? 设 A和 B为两个集合，则 A到 B的关系是
A ? B的 任何子集 。
? 若 A = B, 则称为 A上 的关系。
? 若 R为 A到 B的关系，当 (a,b) ? R时，
可记为 aRb。
例 1-7
? 例如，设 A为整数集合，则 A上的关系
,<”是集合
{(a,b) | a,b ? A,且 a < b}
= {(1,2),(1,3),(1,4),...
(2,3),(2,4),(2,5),...
...}
设 R是 A上的二元关系，有
? (1) 如果对 ?a? A,都有 (a,a) ? R,则
称 R是自反的。
? (2) 如果对 ?a? A,都有 (a,a) ? R, 则
称 R是反自反的。
? (3) 如果对 ?a,b ? A,(a,b) ? R ? (b,
a) ? R,则称 R是对称的。
? (4) 如果对 ?a,b ? A,(a,b) ? R且 (b,a)
? R ? a = b,则称 R是反对称的。
? (5) 如果对 ?a,b,c ? A,(a,b) ? R且 (b,
c) ? R ? (a,c) ? R, 则称 R为传递的。
1.2.2 等价关系与等价类
? 定义 1-6如果集合 A上的二元关系 R是自反
的、对称的和传递的，则称 R为等价关系。
? 等价关系的一个重要性质为：集合 A上的
一个等价关系 R可以将集合 A划分为若干
个互不相交的子集，称为等价类。对 A中
的每个元素 a,使用 [a]表示 a的等价类，即
[a]={b | aRb}。 等价关系 R将集合 A划分成
的等价类的数目，称为该等价关系的 指数 。
例 1-9
非负整数集合 N上的模 3同余关系 R,
R={(a,b)| a,b ? N,且 a mod 3 = b mod
3}。
{0,3,6,…,3 n,…} 形成一个等价类；
{1,4,7,…,3 n+1,…} 形成一个等价类；
{2,5,8,…,3 n+2,…} 形成一个等价类；
分别记为 [0],[1]和 [2]。
1.2.3 关系的合成
?定义 1-7 设 R1 ? A ? B是 A到 B的关系，
R2 ? B ? C是 B到 C 的关系，则 R1与
R2的合成是 A到 C的关系
R1 R2 ={(a,c)| ? (a,b) ? R1且 (b,c) ? R2 }
例 1-11
? 设 R1和 R2的是集合 {1,2,3,4}上的关
系：
R1 ={(1,1),(1,2),(2,3),(3,4)}
R2 ={(2,4),(4,1),(4,3),(3,1),(3,4)}
则 R1R2 ={(1,4),(2,1),(2,4),(3,1),(3,3)}
R2R1 ={(4,1),(4,2),(4,4),(3,1),(3,2)}
定义 1-8 关系的 n次幂
?设 R是 S上的二元关系，则 Rn如下
递归定义：
?(1) R0 = {(a,a) | a ? S}
?(2) Ri = Ri-1 R (i = 1,2,3,…)
定义 1-9 关系的闭包
? 设 R是 S上的二元关系,R的正闭包 R+定义为
(1) R ? R+ ；
(2) 如果 (a,b),(b,c) ? R+,则 (a,c) ? R+ ；
(3) 除 (1),(2)外,R+不再含有其他任何元素。
R+ = R ? R2 ? R3 ?…
且当 S为有穷集时，有
R+ = R ? R2 ? R3 ?… R|s|
关系的克林闭包
R* = R0 ? R+
例 1-14
设 R1= {(a,b),(c,d),(b,d),(b,b),(d,e)}
R2= {(a,a),(b,c),(d,c),(e,d),(c,a)}
则 R1R2 ={ (a,c),(c,c),(b,c),(d,d)}
R1+ = {(a,b),(c,d),(b,d),(b,b),(d,e),
(a,d),(a,e),(c,e),(b,e)}
R1* = {(a,a),(b,b),(c,c),(d,d),(e,e)}?
R1+
1.3 证明和证明的方法
?1.3.1 反证法
?1.3.2 归纳法
?1.3.3 递归定义与归纳证明
1.3.1反证法
?反证法 也称为 归谬法 。利用反证法
证明一个命题时，一般的步骤为：
(1) 假设该命题不成立；
(2) 进行一系列的推理；
(3) 在推理的过程中如果出现了下列
情况之一：
? 与已知条件矛盾；
? 与公理矛盾；
? 与已证过的定理矛盾；
? 与临时的假定矛盾；
? 自相矛盾；
反证法 (续 )
(4) 由于上述矛盾的出现, 可以断言
,假设该命题不成立, 的假设不正确；
(5) 肯定原命题正确 。
反证法 (续 )
? 有牛, 羊和猪三种动物共 10头, 证明：在这
三种动物中至少有一种动物不会少于 4头 。
? 证明, 假设该命题不成立, 即在这三种动物
中没有一种动物多于 4头；那么, 每种动物最
多只有 3头, 则三种动物总数 ? 9,而三种动
物共 10头, 矛盾, 所以, 假设不成立, 在这
三种动物中至少有一种动物不会少于 4头 。 证
毕 。
? (本例实际上为鸽笼原理的一般形式 )
例子
1.3.2 归纳法
? (归纳法就是从特殊到一般的推理方法。
?分为完全归纳法和不完全归纳法两种形
式 。
?完全归纳法是根据一切情况的分析而作
出的推理 。 由于必须考虑所有的情况,
所以得出的结论是完全可靠的 。
?不完全归纳法是根据一部分情况作出
的推理, 因此, 不能作为严格的证明
方法 。
?在形式语言与有限自动机理论中, 大
量使用数学归纳法证明某个命题 。
?数学归纳法可以使用, 有限, 步骤来
解决, 无限, 的问题 。
?数学归纳法的原理为：
?假定对于一切非负整数 n,有一个命题
M(n),假设证明了：
?(1) M(0)为真；
?(2) 设对于任意的 k>=0,M(k)为真；
?如果能够推出 M(k+1)为真, 则对一切 n>=0，
M(n)为真 。
?因此, 在使用数学归纳法证明某个关
于非负整数 n的命题 P(n)时, 只需要
证明 (1),(2)两点即可 。 第 (1)步称
为归纳基础, 第 (2) 步称为归纳步骤 。
第 (2)步中, 设对于任意的 k>=0,M(k)
为真,, 称为归纳假设 。
1.3.3 递归定义与归纳证明
?递归定义
?(1) 基础
?(2) 归纳
?(3) 极小性限定 (有限性 )
?递归定义提供了一种集合的良好的定
义方式, 使得集合中的元素的构造规
律较明显, 同时给集合性质的归纳证
明提供了良好的基础 。
?
? 归纳方法证明递归定义集合性质步骤：
? （ 1） 基础：证明该集合中的最基本元素
具有性质 P； 而且使得该集合非空 。
? （ 2） 归纳：证明如果该集合的元素 x1,x2，
x3,…,具有性质 P,则使用某种运算, 函
数或组合方法对这些元素进行处理后所得
的元素也具有性质 P；
? （ 3） 由归纳法原理, 集合中的所有元素
也具有性质 P。
例 1-17 Fibonacci数
Fibonacci数组成的集合为,{0,1,1,
2,3,5,8,13,21,34,55,… }
(1)基础,0和 1是该集合的最基本的两
个元素；
(2)归纳：若 m是第 i(i?1)个元素, n是
第 i+1个元素, 则第 i+2个元素为 n+m
(3)只有满足 (1)和 (2)的串, 才是集合
的元素 。
?括号匹配的串构成的集合的定义。
1.4 图与树
?1.3.1 无向图
?1.3.2 有向图
?1.3.3 树
图
?现实世界中, 许多现象可以抽象成
图来表示 。
?直观地, 图是由一些 点 和连接两点
的 边 组成的 。
定义 1-10无向图
? 设 V是一个非空的有穷集合, E ? V ? V，
称 G = (V,E)为一个无向图 。
?其中, V称为顶点集, V中的元素称为
顶点； E称为无向边集, E中的元素称
为 无向边 。
?无向图中的边都 没有方向, (vi,vj)和 (vj,
vi)表示的是同一条边
?无向图顶点的度
例
? V = {v1,v2,v3,v4,v5}
? E = {(v1,v2),(v1,v3),
(v1,v4),(v2,v3),(v2,
v5),(v3,v4),(v3,v5),
(v4,v5)}
? deg(v1) = deg(v2) =
deg(v4) = deg(v5) = 3
? deg(v3) = 4
v1 v2
v3
v4 v
5
有向图
? (vi,vj)表示的是从顶点 vi（ 前导 ） 出发,
到达顶点 vj（ 后继 ） 的一条边 。
? 其中,vi称为 vj的前导, vj称为 vi的后继 。
显然, (vi,vj)和 (vj,vi)表示的是不同边
? 有向图顶点的度：入度与出度
思考
?有向图和无向图, 哪种更特殊？
无向图
每条边可以看作是两条弧
例
? G2
? V = {v1,v2,v3,v4,v5}
? E = {(v1,v2),(v1,v3),(v2,
v3),(v3,v4),(v3,v5),(v4,
v1),(v4,v5),(v5,v2),(v5,v4)}
? ideg(v1)= 1,odeg (v1)= 2
? ideg(v2) =2,odeg(v2) =1
v1 v2
v3
v4 v
5
定义 1-12 有向回路
? 设 G = (V,E)为一个有向图 。 如果对于
0 ? i ? k – 1,均有 (vi,vi+1) ? E,则称 v0，
v1,…, vk是 G的一条有向路 。 当 v0 = vk
时, 称 v0,v1,…, vk是一条 有向回路 。
思考
?从 v1到 v4有多少条路？
?无穷条, 因为有圈 v4,v5,v4 。
定义 1-13 树
? 设 G = (V,E)为一个有向图 。 当 G满足如
下条件时, 称 G为一棵 (有向 )树：
? (1) ?v ? V,v没有前导, 且 v到树中的
其他顶点都有一条有向路, 该顶点称为
树 G的根；
? (2) 每一个非根顶点有且仅有一个前导；
? (3) 每个顶点的后继按其拓扑关系从左
到右排序 。
练习
? 设 G = (V,E)为一个无向图，则
||2)d e g ( Ev
Vv
??
?
习题评讲
证明,(1)基础。当图 |E|=0时，图中各结点
的度均为 0，因此
(2)归纳。假设 |E|=n时结论成立,|E|=n+1的
图可以看作是该图添加一条边，不妨令为
(vi,vj)。则新图中 deg(vi),deg(vj)均增加 1,
而其它结点的度保持不变，因此在新图中
仍有
(3)由归纳法原理，结论对任意无向图成立。
0||2)d e g ( ???
?
Ev
Vv
||2)d e g ( Ev
Vv
??
?
1.5 语言
?任意字符的集合就是一个字母表, 最
常用的字母表是大小写 26个英文字母
表, 10个阿拉伯数字字母表, 24个希
腊字母表以及 0和 1的二进制字母表 。
?字母表具有非空性, 有穷性 。 一般使
用 ∑ 表示字母表 。
?字母表中的字母按照某种顺序一个接
一个地排列起来, 形成的字符的序列,
称为一个字符串 。
?一般使用 ε 代表空串 。
?定义：语言的定义
?形式语言和自动机理论中的语言是一
个广泛的概念, 一个字母表上的语言
就是该字母表的某些字符串 （ 也称为
句子 ） 的集合 。
? 字母表中的字母是语言的句子的最基本元
素, 字母表中的字母必须具有两个特点：
? 整体性 （ 不可分性 ） ；例如字母表 {aa,ab}
中的 aa和 ab都是单个字符, 不能被拆分为
a,a,和 a,b。
? 可辨认性 （ 可区分性 ） ；即字母表中任意
两个字符都是不同的, 是可以区分的, 也
就是说, 字母表中的元素是不能重复的
? 对于语言的研究, 实际上包括三个方面：
? 首先, 如何给出一个语言的表示 。 如果该
语言是有穷语言, 那么, 可以使用列举法
列举出语言中所包含的所有字符串即可；
而如果该语言是无穷语言, 对该语言的表
示, 就成了问题, 需要考虑语言的有穷描
述 。
?第二个问题, 对于一个给定的语言是
否存在有穷描述 。 并不是所有的语言
都存在有穷描述, 即对于某些语言,
并不存在有穷表示 。
?第三个问题是具有有穷表示的语言的
结构以及结构的特性问题 。
1.6 常用术语
?(1) 用 ε 代表空串, {ε }代表仅含有
空串的集合 。
?(2) 用 Ф代表空集, 表示一个元素都
不包含的集合 。
?(3) 用 ?代表一个符号的非空有限集
合, 称之为字母表, 其中的元素称为
字母 。
? (4) 用 αβ代表两个字符串 α 与 β 的连接
（ 并置 ） 。
? 若 α =a1a2a3… an,β =b1b2b3… bm； m,n>=0,
则 αβ= a1a2a3… anb1b2b3… bm。
? 显然, αε=εα=α
? (5) 用 AB代表两个集合 A与 B的连接 。
A={a1,a2,a3,…,an},B={b1,b2,b3,…,bm}；
? AB=
{ a1b1,a1b2,a1b3,…, a1bm，
a2b1,a2b2,a2b3,…, a2bm，
a3b1,a3b2,a3b3,…, a3bm，
…
anb1,anb2,anb3,…, anbm }
注意：
? AФ=ФA=Ф。
?一般, AB与 BA是不相等的 。
?AB与 BA在什么情况下相等?
?1)当 A=B；
?2)A 或 B 中 有 一 个 为 { ε },则
A{ε }={ε }A=A；
?3)A 和 B 中 有 一 个 为 Ф,则
AФ=ФA=Ф；
?6)用 An代表集合 A的 n次连接 （ n次
幂 ）,
?设 A是一个集合,A的 n次 幂 定义为：
?(1) A0 = {?}
?(2) An = An-1A n ? 1（ 或 An = AAn-1）
A0={ε }
A1= A
A2= AA
A3= A2A
…
An= An-1A
? 7)用 A*代表集合 A上所有字符串的集合 。
即表示集合 A中的所有字符串进行任
意次连接而形成的串的集合, 也称 A*
为集合 A的闭包 （ 克林 闭包 ） 。
?A* = A0 ∪ A1 ∪ A2 ∪ … ∪ An
? 例如,A={0,1}；
? 则 A0={ε } 即长度为 0的 0和 1组成的串的集合
? A1=A={0,1} 即长度为 1的 0和 1组成的串的集合
? A2=AA={00,01,10,11}
即长度为 2的 0和 1组成的串集合
?
? A3=AA2
? ={000,001,010,011,100,101,110,111}
即长度为 3的 0和 1组成的串的集合
? …
? A* = A0 ∪ A1 ∪ A2 ∪ … ∪ An
={0和 1 组成的所有的串 }
={w|w是 0和 1 组成的串 }
?如果一个串 ω是一个集合 A的闭包
中的串, 也称 ω是集合 A上的串 。
?对于任何集合 A,有 (A*)*= A*。
?8)用 A+代表一个集合, 称为 A的正
闭包,
?A+=A∪A 2∪A 3∪ … ∪A n 。
注意：
? 由于 A0={ε } 因此 Ф *={ε }
? {ε }*={ε }
? {ε }+={ε }
? Ф +=Ф
思考,
?是否对于任意的集合 A,都有
? A+= A*-{ε }
?成立？
?因为 {ε }*={ε } {ε }+={ε }
?所以, 对于任意的集合 A,如果 A不是
{ε },则都有 A+= A*-{ε }成立 。
?9） 给定字母表 ∑, 则 ∑ *的任意
子集 L称为字母表 ∑ 上的一个语言,
既 L是字母表 ∑ 上的字符串的集合 。
? 10)给定字母表 ∑, L是字母表 ∑ 上的一
个语言, ω是 L的一个字符串 （ 称为 L的一
个 句子 ）, 用 |ω|表示句子 ω的长度, 即
ω中包含的字母的个数 。
? |ε |=0；
? |ω|= n； 若 ω=a1a2a3… an；
其中,ai∈, n>0；
? 11)前缀和后缀：
? 设 ∑ 是一个字母表, x,y,z∈∑ *,且 x=yz，
? 称 y是 x的前缀；如果 z！ =ε, 则称 y是 x的
真前缀；
? 称 z是 x的后缀；如果 y！ =ε, 则称 z是 x的
真后缀；
? 例如：
? 串 abcde的前缀, 真前缀, 后缀和真后缀
如下：
? 前缀,ε, a,ab,abc,abcd,abcde
? 真前缀,ε, a,ab,abc,abcd
? 后缀,ε, e,de,cde,bcde,abcde
? 真后缀,ε, e,de,cde,bcde
?对于任何字符串 x,x的任意前缀 y有
惟一的一个后缀 z与之对应, 使得
x=yz,反之亦然；
?对于任何字符串 x,x的任意真前缀 y
有惟一的一个真后缀 z与之对应, 使
得 x=yz,反之亦然 （ 除了 ε 以外 ） ；
? 对于任何字符串 x！ =ε,
x是自身的前缀, 但不是自身的真前缀；
x是自身的后缀, 但不是自身的真后缀；
? 对于任何字符串 x！ =ε,
ε 是 x的前缀, 且是真前缀；
ε 是 x的后缀, 且是真后缀；
? 对于任何字符串 x,x的前缀共有 |x|+1个 。
?12)语言的前缀性质
?设 L是某个字母表上的一个语言, 如 L
中的任何字符串都是另一个字符串的
真前缀, 则称语言 L具有前缀性质 。
?例如：
?字母表 {0,1}上的语言
?L1={0n|n>=0}
具有前缀性质；
?语言 L2={0n1|n>=0}
不具有前缀性质。
关于语言与句子
?设 ?是一个字母表,?L ??*,L称为
字母表 ?上的一个 语言 (language),?x
? L,x叫做 L的一个 句子 。
?可按语言的基数分为 有穷语言 与 无穷
语言 。
语言的乘积
?设 ?1,?2是二个字母表,L1??1*,L2
??2*,语言 L1与 L2的乘积是一个语言：
L1L2={xy | x ? L1,y ? L2}
该语言是字母表 ?1 ??2 上的语言。
例
? 字母表 {0,1}上的一些语言：
? {00,11}
? {0,1,00,11}
? {0}{0,1}*{1}
? {0,1}*{111}{0,1}*
例
? 令 ?= {0,1}，下面是 ?上语言的例子：
L = {0,1}
L = {0,1,00,01,10,11,…}= ?+
L = {?,0,1,00,01,10,11,…}= ?*
L = {0n1n | n ? 1}
L = {0n1m0k | n,m,k ? 1}
语言的 n次幂
?设 ?是一个字母表,?L ??*,L的 n次
幂是一个语言
(1) 当 n = 0时,Ln = {?}
(2) 当 n ? 1时,Ln = Ln-1 L
语言的闭包
?L的正闭包 L+是一个语言：
L+ = L? L2 ?L3 ?…
?L的克林闭包 L*是一个语言：
L* = L0 ? L+
1.7形式语言与自动机的发展
? 语言学家 Chomsky(乔姆斯基 )最早从产生
语言的角度研究语言 。 1956年, 通过抽象,
Chomsky将语言形式地定义为由一个字母
表的字母组成的一些串的集合：对于任意
语言 L,有一个字母表, 使得 LC∑ *。 可以
在字母表上按照一定的形成规则定义一个
文法, 该文法产生的所有的句子组成的集
合就是该文法产生的语言 。
? 1959年, Chomsky根据产生语言的文法的
产生式的不同特点, 将文法和对应产生的
语言分为三大类 。
? 数学家 Kleene（ 克林 ） 在 1951~1956年间,
从识别语言的角度来研究语言, 给出了语
言的另一种描述方式 。 Kleene在研究神经
细胞时建立了自动机模型, Kleene使用该
模型来识别 （ 接收 ） 一个语言：按照某种
识别规则构造自动机, 该自动机就定义了
一个语言, 该语言由自动机能够识别的所
有字符串构成 。
? 语言的两种不同的定义方式进一步引起了
人们的研究兴趣 。 一个语言, 可以采取不
同的描述方式：文法产生语言和自动机识
别语言 。 由于是同一个语言, 两种方式应
该是等价的, 也就存在两种方式之间的等
价的相互转换方法 。
? Chomsky于 1959年, 将他本人的形式语言
的研究成果和 Kleene的自动机的研究成果
结合起来, 不仅确定了文法和自动机分别
从产生和识别角度定义语言, 而且证明了
文法与自动机的等价性 。 此时, 形式语言
与自动机理论才真正诞生 。 并被置于数学
的光芒之下 。
? 形式语言与自动机理论出现后, 迅速在计算机
科学技术领域得到了应用 。 使用巴科斯 -诺尔范
式 （ BNF--Backus-Naur Form） 成功地对高级程
序设计语言 ALGOL-60的词法和语法规则进行了
形式化的描述 （ 实际上, 巴科斯 -诺尔范式就是
上下文无关文法的产生式另一种表示方式 ） 。
这一成功, 使得形式语言与自动机理论得到了
进一步的发展 。
? 尤其是上下文无关文法, 被作为计算机程
序设计语言语法的最佳近似描述得到了较
为深入的研究 。 后来, 人们又将上下文无
关文法应用到了模式匹配和模型化处理等
方面, 而这些内容都是算法描述和分析,
计算复杂性理论和可计算性理论的研究基
础 。
? 形式语言理论的研究对象与以前的所有语
言研究不同, 不止自然语言, 而是人类一
切语言：既有自然语言, 也有人工语言,
包括计算机编程的高级语言 。 乔姆斯基的
形式语言理论得到了多重验证, 于是才为
语言学界和计算机科学界所折服,, 引发
了语言学中伽利略式的科学革命的开端 。,
? 乔姆斯基的形式语言理论得到过计算机科
学的三种验证 。
? 验证一：乔氏 4型文法与 4种语言自动机一
一对应 。
? 验证二：计算机所使用的各种高级语言, 如
ALGOL,FORTRAN,PASCAL,C,LISP等, 都遵循
一种程序语言文法描述的范式, 即巴科斯 —瑙
尔范式 。 计算机科学家发现, 巴科斯 —瑙尔范
式等价于乔姆斯基的 2型文法, 即与上下文无关
文法 。 而乔姆斯基的 3型文法 ——正则文法, 在
研究文字的计算机模式识别时, 也被有效应用 。
于是, 乔氏的 4种类型文法被计算机科学界称作
乔姆斯基分类 。
? 验证三：乔姆斯基用形式语言理论的思想证明
了计算机科学的一个重大理论问题：计算机程
序语言是否有歧义性是不可判定的 。
? 20世纪中期, 程序语言 ALGOL60问世不久, 人们
发现它有歧义性 。 当计算机科学家绞尽脑汁寻
找办法来判断一种程序语言是否有歧义性时,
乔姆斯基用形式语言理论的思想证明, 一个任
意的上下文无关文法是否有歧义性是不可判定
的, 因此, 属于上下文无关文法的程序语言是
否有歧义性也是不可判定的 。 乔姆斯基的论证
令计算机科学界折服 。
?实际上, 形式语言与自动机理论除了
在计算机科学与技术领域的直接应用
外, 更在计算机计算机科学与技术领
域的人才的计算思维能力的培养中占
有极其重要的地位 。
? 计算机科学与技术学科强调 4个方面的专
业能力：计算思维能力、算法设计与分析
能力、程序设计与实现能力、计算机系统
的认知、分析、设计和运用能力。这也是
计算机科学与其他学科的重要区别。相关
的理论是计算机学科的基础。
? 理论方面的知识是计算机的真正灵魂。
?在本科阶段的学习过程中，学生以观
察、描述、比较、分类、推断、应用、
创造思维等科学思维过程为主，强调
自学的能力 在培养；
?研究生阶段，需要对学生进一步进行
抽象思维、逻辑思维、创造思维能力
的培养。
?建立物理符号系统并对起实施等价变
换是计算机学科进行问题描述和求解
的重要手段 。, 可行性, 所要求的
,形式化, 及其, 离散特征, 使得数
学成为重要的工具, 而计算模型无论
从方法还是从工具等方面, 都表现出
它在计算机上科学中的重要作用 。
?计算机科学与技术学科要求学生具有
形式化描述和抽象思维能力, 要求掌
握逻辑思维方法 。 这种能力就是计算
思维能力或计算机思维能力 。
?计算机学科系统地研究信息描述和变
换算法, 重要包括信息描述和变换算
法的理论, 分析, 效率, 实现和运用 。
学科的根本问题在于：什么能被 （ 有
效地 ） 自动化？ 学科的重要内容之一
是研究计算领域中的一些普遍规律,
描述算法的基本概念与模型 。
?计算思维能力的培养主要是通过基础
理论系列课程实现的，该系列是由数
学和抽象度较高的理论课程组成，包
括数学分析、集合和图论、形式语言
与自动机、近世代数、数学建模等课
程。
练习 (见习题 )
?1(1)
?4
?5(12)
?7(6)
?9
习题评讲
?1(1)
?{?,a,b,aa,ab,ba,bb,aaa,aab,
aba,abb,baa,bab,bba,bbb}
?4
习题评讲 (续 )
? 5(12)证明：
因为 A? B,并且 B ? C,则对任意 x? A,x
? B且 x ? C,因此 A ? C
由于 A? B,存在 y ? B,y ? A,而 B ? C,有
y ? C
因此 A? C
...
7(6)
? 对于任意 x ??*,
(1) 如果 |x| = 0,则 xT = x
(2)如果 |x| = 1,则 xT = x
(3)如果 |x| > 1,令 x = ya，其中 y ?
?*,a ??，则 xT = ayT
习题评讲 (续 )
?9
(1) {0}{0,1}*
(2) {0}{0,1}* {1}
(3) {11}{0,1}*{11}?{111} ?{11}
(4)
习题评讲 (续 )
(5) {{0,1}{0,1}}*
(6) ({0,1}{0,1})* {0,1}
(7) {0,1}*{01011} {0,1}*
(8) {0,1}*{000}{0,1}*
习题评讲 (续 )
(9) {0,1}9 {0}{0,1}*
(10) {0,1}* {0} {0,1}9
小结
?本章内容：
?复习 集合、关系、图 等相关知识
?引入 形式语言
?重点,掌握形式语言的基本定义
陈文宇
电子科技大学计算机科学与工程学院
cwy@uestc.edu.cn
教材,
形式语言与自动机
(陈文宇 欧齐 程炼）
人民邮电出版社
参考书：
形式语言与自动机理论
（蒋宗礼 清华大学出版社）
形式语言与自动机
（陈有祺 南开大学出版社）
?形式语言和自动机的理论是计算机科
学的理论基础 。 这些理论来源于
(1) Chomsky对自然语言的研究；
(2) ALGOL 60语言的语法描述方式；
(3)Kleene对自动机的研究；
? 早在 20世纪五十年代, 在研究如何使, 自然语
言, 符号化 （ 即形式化 ） 的过程中, 产生并发
展了, 形式语言与自动机, 的理论 。 不久, 人
们就发现该理论与计算机科学中所创立和使用
的程序设计语言具有密切的关系 （ 比如, 可以
用于描述程序设计语言的词法和语法规则 ） 。
从此以后, 形式语言与自动机的理论和方法的
研究, 受到了越来越多科学家的重视 。
? 形式语言和自动机的理论已经成为计算机
科学的理论基础, 其应用范围已被扩展到生
物工程, 自动控制系统, 图象处理与模式识别
等许多领域 。
? 实际上,, 形式语言与自动机, 的理论除了在
计算机科学领域中的直接应用外, 对于 计算机
科学人才的计算思维能力的培养, 具
有重要作用 。
?形式化描述和抽象思维能力，
逻辑思维方法。这种能力就是
计算思维能力或计算机思维能
力。
第 1章 绪论
?本章将对形式语言和有限自动机理论
中所需的数学基础知识作扼要的介绍。
内容包括 集合及其运算、关系、证明
的方法、图与树 的概念；以及一些 常
用术语 和 形式语言与自动机的发展 。
第 1章 绪论
? 1.1集合及其运算
? 1.2 关系
? 1.3 证明和证明的方法
? 1.4 图与树
? 1.5 语言
? 1.6 常用术语
? 1.7 形式语言与自动机的发展
1.1集合及其运算
?一些没有重复的对象的全体称为 集
合 (set),而这些被包含的对象称为
该集合的 元素 (element)。
?集合中元素可以按 任意的顺序 进行
排列。一般，使用大写英文字母表
示一个集合。
列举法
?对于元素个数较少的集合，可以采
用列举法，即将集合的所有元素全
部列出，并放在一对花括号中。例
如集合 A ={0,1,2,3,4,5,6，
7,8,9},表示集合 A由 0,1,2，
3,4,5,6,7,8,9共 10个元素
组成。
命题法
? 对于集合元素较多的或者是由无穷多个元素
组成的集合，可以使用集合形成模式 {x |
P(x)}进行描述，其中,x表示集合中的任一
元素,P(x)是一个谓词，对 x进行限定,{x |
P(x)}表示由满足 P(x)的一切 x构成的集合。
可以使用自然语言，或者数学表示法来描述
谓词 P(x)。
? 例如,{n | n是偶数 }，或者 {n | n mod 2 = 0}，
都表明了一个由所有偶数组成的集合。
集合的基数
? 如果集合 A包含元素 x（ 也称元素 x在集合 A
中），记为 x ? A。 否则 x ? A。
? 对于任意的有穷集合 A,使用 |A|表示该集合
包含的元素的 个数,也称 基数 或 势 。显然，
|A| = 0 ? A = ? 。
? 如果一个集合中的元素个数是有限的，称该
集合为 有穷集合 。如果一个集合包含的元素
是无限的，称该集合为 无穷集合 。无穷集合
又分为可数集 (如自然数集，有理数集 )和不
可数集 (如实数集 )。
定义 1-1 子集
? 设 A,B是两个集合，如果集合 A中的每
个元素都是集合 B的元素，则称集合 A
是集合 B的子集，集合 B是集合 A的包集。
记作 A? B,或 B? A。
? 设 A,B是两个集合，如果 A ? B, 且 ?x
? B,但 x? A,则称 A是 B的真子集，
记作 A? B。
定义 1-2 集合的运算
? 并，交,注意多个集合并、交的写法
? 差,注意它不要求两个集合存在子集
关系
? 补集,论域的概念
Ai
n
i 1?
?
几个结论
? A = B iff A ? B且 B ? A。
? 如果 A是有穷集，且 A ? B, 则 |A| < |B|。
? 对于无穷集，这个结论并不适用。如奇
数集是自然数集的真子集，自然数集与
奇数集之间存在一一对应关系，即它们
的基数相等。该映射可表示为：
f(x) = 2x-1
定义 1-3 幂集
? 设 A为一个集合，那么 A的 幂集 为 A的所
有子集 组成的集合，记为 2A,即 2A={B |
B ? A}。
?例如，集合 A={1,2,3},则 A的幂集为,
2A={?,{1},{2},{3},{1,2},{1，
3},{2,3},{1,2,3}}。
? 当集合 A为有穷集时，如果集合 A包含的元素
个数为 n,那么集合 2A的元素个数 (集合 A的所
有子集的个数 )为 2n,这就是称 2A为集合 A的
幂集的原因。
定义 1-4 笛卡儿积
? 集合 A和 B的笛卡儿乘积使用 A ? B表示
（也简记为 AB）
? A ? B = {(a,b) | a ? A 且 b ? B}。
例
? 设 A = {a,b,c},B = {0,1},
则 A ? B ={(a,0),(a,1),(b,0),(b,1),(c,0),
(c,1)}.
? 也可根据约定记为：
A ? B={a0,a1,b0,b1,c0,c1}
而 B ? A={(0,a),(0,b),(0,c),(1,a),(1,b),
(1,c)}
思考
?什么情况下,A ? B = B ? A?
?1） A = B
?2） A = ?或 B = ?
?3） …
练习 (见习题 )
?1(2)(3)(4)
?2(1)(3) (5) (6) (10)
习题评讲
1(2) 2{1,2,3,4} ={?,{1},{2},{3},{4},{1,2},{1,
3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,
2,4},{2,3,4},{1,2,3,4}}
(3) { 1,2,3,4,5,6,7,8,9,10}
{4} {{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,
6},{1,4,5},{2,3,5},{1,2,3,4}}
注意：没有 {5,5}
习题评讲 (续 )
2(1) {x | x ? N且 1 ? x ? 100}
(3) 2{1,2,3,4}={B | B ? {1,2,3,4}}
(5) {x | x > 0且 x mod 2 = 1}
习题评讲 (续 )
2(6) {(x,y) | x,y ? [4,9]且 x + y = 10}
即 {(4,6),(6,4),(5,5)}
(10) {B | B ? {1,2,...,10}且 ?x = 10,x
? B}
1.2 关系
?1.2.1 二元关系
?1.2.2 等价关系与等价类
?1.2.3 关系的合成
1.2.1 二元关系
? 设 A和 B为两个集合，则 A到 B的关系是
A ? B的 任何子集 。
? 若 A = B, 则称为 A上 的关系。
? 若 R为 A到 B的关系，当 (a,b) ? R时，
可记为 aRb。
例 1-7
? 例如，设 A为整数集合，则 A上的关系
,<”是集合
{(a,b) | a,b ? A,且 a < b}
= {(1,2),(1,3),(1,4),...
(2,3),(2,4),(2,5),...
...}
设 R是 A上的二元关系，有
? (1) 如果对 ?a? A,都有 (a,a) ? R,则
称 R是自反的。
? (2) 如果对 ?a? A,都有 (a,a) ? R, 则
称 R是反自反的。
? (3) 如果对 ?a,b ? A,(a,b) ? R ? (b,
a) ? R,则称 R是对称的。
? (4) 如果对 ?a,b ? A,(a,b) ? R且 (b,a)
? R ? a = b,则称 R是反对称的。
? (5) 如果对 ?a,b,c ? A,(a,b) ? R且 (b,
c) ? R ? (a,c) ? R, 则称 R为传递的。
1.2.2 等价关系与等价类
? 定义 1-6如果集合 A上的二元关系 R是自反
的、对称的和传递的，则称 R为等价关系。
? 等价关系的一个重要性质为：集合 A上的
一个等价关系 R可以将集合 A划分为若干
个互不相交的子集，称为等价类。对 A中
的每个元素 a,使用 [a]表示 a的等价类，即
[a]={b | aRb}。 等价关系 R将集合 A划分成
的等价类的数目，称为该等价关系的 指数 。
例 1-9
非负整数集合 N上的模 3同余关系 R,
R={(a,b)| a,b ? N,且 a mod 3 = b mod
3}。
{0,3,6,…,3 n,…} 形成一个等价类；
{1,4,7,…,3 n+1,…} 形成一个等价类；
{2,5,8,…,3 n+2,…} 形成一个等价类；
分别记为 [0],[1]和 [2]。
1.2.3 关系的合成
?定义 1-7 设 R1 ? A ? B是 A到 B的关系，
R2 ? B ? C是 B到 C 的关系，则 R1与
R2的合成是 A到 C的关系
R1 R2 ={(a,c)| ? (a,b) ? R1且 (b,c) ? R2 }
例 1-11
? 设 R1和 R2的是集合 {1,2,3,4}上的关
系：
R1 ={(1,1),(1,2),(2,3),(3,4)}
R2 ={(2,4),(4,1),(4,3),(3,1),(3,4)}
则 R1R2 ={(1,4),(2,1),(2,4),(3,1),(3,3)}
R2R1 ={(4,1),(4,2),(4,4),(3,1),(3,2)}
定义 1-8 关系的 n次幂
?设 R是 S上的二元关系，则 Rn如下
递归定义：
?(1) R0 = {(a,a) | a ? S}
?(2) Ri = Ri-1 R (i = 1,2,3,…)
定义 1-9 关系的闭包
? 设 R是 S上的二元关系,R的正闭包 R+定义为
(1) R ? R+ ；
(2) 如果 (a,b),(b,c) ? R+,则 (a,c) ? R+ ；
(3) 除 (1),(2)外,R+不再含有其他任何元素。
R+ = R ? R2 ? R3 ?…
且当 S为有穷集时，有
R+ = R ? R2 ? R3 ?… R|s|
关系的克林闭包
R* = R0 ? R+
例 1-14
设 R1= {(a,b),(c,d),(b,d),(b,b),(d,e)}
R2= {(a,a),(b,c),(d,c),(e,d),(c,a)}
则 R1R2 ={ (a,c),(c,c),(b,c),(d,d)}
R1+ = {(a,b),(c,d),(b,d),(b,b),(d,e),
(a,d),(a,e),(c,e),(b,e)}
R1* = {(a,a),(b,b),(c,c),(d,d),(e,e)}?
R1+
1.3 证明和证明的方法
?1.3.1 反证法
?1.3.2 归纳法
?1.3.3 递归定义与归纳证明
1.3.1反证法
?反证法 也称为 归谬法 。利用反证法
证明一个命题时，一般的步骤为：
(1) 假设该命题不成立；
(2) 进行一系列的推理；
(3) 在推理的过程中如果出现了下列
情况之一：
? 与已知条件矛盾；
? 与公理矛盾；
? 与已证过的定理矛盾；
? 与临时的假定矛盾；
? 自相矛盾；
反证法 (续 )
(4) 由于上述矛盾的出现, 可以断言
,假设该命题不成立, 的假设不正确；
(5) 肯定原命题正确 。
反证法 (续 )
? 有牛, 羊和猪三种动物共 10头, 证明：在这
三种动物中至少有一种动物不会少于 4头 。
? 证明, 假设该命题不成立, 即在这三种动物
中没有一种动物多于 4头；那么, 每种动物最
多只有 3头, 则三种动物总数 ? 9,而三种动
物共 10头, 矛盾, 所以, 假设不成立, 在这
三种动物中至少有一种动物不会少于 4头 。 证
毕 。
? (本例实际上为鸽笼原理的一般形式 )
例子
1.3.2 归纳法
? (归纳法就是从特殊到一般的推理方法。
?分为完全归纳法和不完全归纳法两种形
式 。
?完全归纳法是根据一切情况的分析而作
出的推理 。 由于必须考虑所有的情况,
所以得出的结论是完全可靠的 。
?不完全归纳法是根据一部分情况作出
的推理, 因此, 不能作为严格的证明
方法 。
?在形式语言与有限自动机理论中, 大
量使用数学归纳法证明某个命题 。
?数学归纳法可以使用, 有限, 步骤来
解决, 无限, 的问题 。
?数学归纳法的原理为：
?假定对于一切非负整数 n,有一个命题
M(n),假设证明了：
?(1) M(0)为真；
?(2) 设对于任意的 k>=0,M(k)为真；
?如果能够推出 M(k+1)为真, 则对一切 n>=0，
M(n)为真 。
?因此, 在使用数学归纳法证明某个关
于非负整数 n的命题 P(n)时, 只需要
证明 (1),(2)两点即可 。 第 (1)步称
为归纳基础, 第 (2) 步称为归纳步骤 。
第 (2)步中, 设对于任意的 k>=0,M(k)
为真,, 称为归纳假设 。
1.3.3 递归定义与归纳证明
?递归定义
?(1) 基础
?(2) 归纳
?(3) 极小性限定 (有限性 )
?递归定义提供了一种集合的良好的定
义方式, 使得集合中的元素的构造规
律较明显, 同时给集合性质的归纳证
明提供了良好的基础 。
?
? 归纳方法证明递归定义集合性质步骤：
? （ 1） 基础：证明该集合中的最基本元素
具有性质 P； 而且使得该集合非空 。
? （ 2） 归纳：证明如果该集合的元素 x1,x2，
x3,…,具有性质 P,则使用某种运算, 函
数或组合方法对这些元素进行处理后所得
的元素也具有性质 P；
? （ 3） 由归纳法原理, 集合中的所有元素
也具有性质 P。
例 1-17 Fibonacci数
Fibonacci数组成的集合为,{0,1,1,
2,3,5,8,13,21,34,55,… }
(1)基础,0和 1是该集合的最基本的两
个元素；
(2)归纳：若 m是第 i(i?1)个元素, n是
第 i+1个元素, 则第 i+2个元素为 n+m
(3)只有满足 (1)和 (2)的串, 才是集合
的元素 。
?括号匹配的串构成的集合的定义。
1.4 图与树
?1.3.1 无向图
?1.3.2 有向图
?1.3.3 树
图
?现实世界中, 许多现象可以抽象成
图来表示 。
?直观地, 图是由一些 点 和连接两点
的 边 组成的 。
定义 1-10无向图
? 设 V是一个非空的有穷集合, E ? V ? V，
称 G = (V,E)为一个无向图 。
?其中, V称为顶点集, V中的元素称为
顶点； E称为无向边集, E中的元素称
为 无向边 。
?无向图中的边都 没有方向, (vi,vj)和 (vj,
vi)表示的是同一条边
?无向图顶点的度
例
? V = {v1,v2,v3,v4,v5}
? E = {(v1,v2),(v1,v3),
(v1,v4),(v2,v3),(v2,
v5),(v3,v4),(v3,v5),
(v4,v5)}
? deg(v1) = deg(v2) =
deg(v4) = deg(v5) = 3
? deg(v3) = 4
v1 v2
v3
v4 v
5
有向图
? (vi,vj)表示的是从顶点 vi（ 前导 ） 出发,
到达顶点 vj（ 后继 ） 的一条边 。
? 其中,vi称为 vj的前导, vj称为 vi的后继 。
显然, (vi,vj)和 (vj,vi)表示的是不同边
? 有向图顶点的度：入度与出度
思考
?有向图和无向图, 哪种更特殊？
无向图
每条边可以看作是两条弧
例
? G2
? V = {v1,v2,v3,v4,v5}
? E = {(v1,v2),(v1,v3),(v2,
v3),(v3,v4),(v3,v5),(v4,
v1),(v4,v5),(v5,v2),(v5,v4)}
? ideg(v1)= 1,odeg (v1)= 2
? ideg(v2) =2,odeg(v2) =1
v1 v2
v3
v4 v
5
定义 1-12 有向回路
? 设 G = (V,E)为一个有向图 。 如果对于
0 ? i ? k – 1,均有 (vi,vi+1) ? E,则称 v0，
v1,…, vk是 G的一条有向路 。 当 v0 = vk
时, 称 v0,v1,…, vk是一条 有向回路 。
思考
?从 v1到 v4有多少条路？
?无穷条, 因为有圈 v4,v5,v4 。
定义 1-13 树
? 设 G = (V,E)为一个有向图 。 当 G满足如
下条件时, 称 G为一棵 (有向 )树：
? (1) ?v ? V,v没有前导, 且 v到树中的
其他顶点都有一条有向路, 该顶点称为
树 G的根；
? (2) 每一个非根顶点有且仅有一个前导；
? (3) 每个顶点的后继按其拓扑关系从左
到右排序 。
练习
? 设 G = (V,E)为一个无向图，则
||2)d e g ( Ev
Vv
??
?
习题评讲
证明,(1)基础。当图 |E|=0时，图中各结点
的度均为 0，因此
(2)归纳。假设 |E|=n时结论成立,|E|=n+1的
图可以看作是该图添加一条边，不妨令为
(vi,vj)。则新图中 deg(vi),deg(vj)均增加 1,
而其它结点的度保持不变，因此在新图中
仍有
(3)由归纳法原理，结论对任意无向图成立。
0||2)d e g ( ???
?
Ev
Vv
||2)d e g ( Ev
Vv
??
?
1.5 语言
?任意字符的集合就是一个字母表, 最
常用的字母表是大小写 26个英文字母
表, 10个阿拉伯数字字母表, 24个希
腊字母表以及 0和 1的二进制字母表 。
?字母表具有非空性, 有穷性 。 一般使
用 ∑ 表示字母表 。
?字母表中的字母按照某种顺序一个接
一个地排列起来, 形成的字符的序列,
称为一个字符串 。
?一般使用 ε 代表空串 。
?定义：语言的定义
?形式语言和自动机理论中的语言是一
个广泛的概念, 一个字母表上的语言
就是该字母表的某些字符串 （ 也称为
句子 ） 的集合 。
? 字母表中的字母是语言的句子的最基本元
素, 字母表中的字母必须具有两个特点：
? 整体性 （ 不可分性 ） ；例如字母表 {aa,ab}
中的 aa和 ab都是单个字符, 不能被拆分为
a,a,和 a,b。
? 可辨认性 （ 可区分性 ） ；即字母表中任意
两个字符都是不同的, 是可以区分的, 也
就是说, 字母表中的元素是不能重复的
? 对于语言的研究, 实际上包括三个方面：
? 首先, 如何给出一个语言的表示 。 如果该
语言是有穷语言, 那么, 可以使用列举法
列举出语言中所包含的所有字符串即可；
而如果该语言是无穷语言, 对该语言的表
示, 就成了问题, 需要考虑语言的有穷描
述 。
?第二个问题, 对于一个给定的语言是
否存在有穷描述 。 并不是所有的语言
都存在有穷描述, 即对于某些语言,
并不存在有穷表示 。
?第三个问题是具有有穷表示的语言的
结构以及结构的特性问题 。
1.6 常用术语
?(1) 用 ε 代表空串, {ε }代表仅含有
空串的集合 。
?(2) 用 Ф代表空集, 表示一个元素都
不包含的集合 。
?(3) 用 ?代表一个符号的非空有限集
合, 称之为字母表, 其中的元素称为
字母 。
? (4) 用 αβ代表两个字符串 α 与 β 的连接
（ 并置 ） 。
? 若 α =a1a2a3… an,β =b1b2b3… bm； m,n>=0,
则 αβ= a1a2a3… anb1b2b3… bm。
? 显然, αε=εα=α
? (5) 用 AB代表两个集合 A与 B的连接 。
A={a1,a2,a3,…,an},B={b1,b2,b3,…,bm}；
? AB=
{ a1b1,a1b2,a1b3,…, a1bm，
a2b1,a2b2,a2b3,…, a2bm，
a3b1,a3b2,a3b3,…, a3bm，
…
anb1,anb2,anb3,…, anbm }
注意：
? AФ=ФA=Ф。
?一般, AB与 BA是不相等的 。
?AB与 BA在什么情况下相等?
?1)当 A=B；
?2)A 或 B 中 有 一 个 为 { ε },则
A{ε }={ε }A=A；
?3)A 和 B 中 有 一 个 为 Ф,则
AФ=ФA=Ф；
?6)用 An代表集合 A的 n次连接 （ n次
幂 ）,
?设 A是一个集合,A的 n次 幂 定义为：
?(1) A0 = {?}
?(2) An = An-1A n ? 1（ 或 An = AAn-1）
A0={ε }
A1= A
A2= AA
A3= A2A
…
An= An-1A
? 7)用 A*代表集合 A上所有字符串的集合 。
即表示集合 A中的所有字符串进行任
意次连接而形成的串的集合, 也称 A*
为集合 A的闭包 （ 克林 闭包 ） 。
?A* = A0 ∪ A1 ∪ A2 ∪ … ∪ An
? 例如,A={0,1}；
? 则 A0={ε } 即长度为 0的 0和 1组成的串的集合
? A1=A={0,1} 即长度为 1的 0和 1组成的串的集合
? A2=AA={00,01,10,11}
即长度为 2的 0和 1组成的串集合
?
? A3=AA2
? ={000,001,010,011,100,101,110,111}
即长度为 3的 0和 1组成的串的集合
? …
? A* = A0 ∪ A1 ∪ A2 ∪ … ∪ An
={0和 1 组成的所有的串 }
={w|w是 0和 1 组成的串 }
?如果一个串 ω是一个集合 A的闭包
中的串, 也称 ω是集合 A上的串 。
?对于任何集合 A,有 (A*)*= A*。
?8)用 A+代表一个集合, 称为 A的正
闭包,
?A+=A∪A 2∪A 3∪ … ∪A n 。
注意：
? 由于 A0={ε } 因此 Ф *={ε }
? {ε }*={ε }
? {ε }+={ε }
? Ф +=Ф
思考,
?是否对于任意的集合 A,都有
? A+= A*-{ε }
?成立？
?因为 {ε }*={ε } {ε }+={ε }
?所以, 对于任意的集合 A,如果 A不是
{ε },则都有 A+= A*-{ε }成立 。
?9） 给定字母表 ∑, 则 ∑ *的任意
子集 L称为字母表 ∑ 上的一个语言,
既 L是字母表 ∑ 上的字符串的集合 。
? 10)给定字母表 ∑, L是字母表 ∑ 上的一
个语言, ω是 L的一个字符串 （ 称为 L的一
个 句子 ）, 用 |ω|表示句子 ω的长度, 即
ω中包含的字母的个数 。
? |ε |=0；
? |ω|= n； 若 ω=a1a2a3… an；
其中,ai∈, n>0；
? 11)前缀和后缀：
? 设 ∑ 是一个字母表, x,y,z∈∑ *,且 x=yz，
? 称 y是 x的前缀；如果 z！ =ε, 则称 y是 x的
真前缀；
? 称 z是 x的后缀；如果 y！ =ε, 则称 z是 x的
真后缀；
? 例如：
? 串 abcde的前缀, 真前缀, 后缀和真后缀
如下：
? 前缀,ε, a,ab,abc,abcd,abcde
? 真前缀,ε, a,ab,abc,abcd
? 后缀,ε, e,de,cde,bcde,abcde
? 真后缀,ε, e,de,cde,bcde
?对于任何字符串 x,x的任意前缀 y有
惟一的一个后缀 z与之对应, 使得
x=yz,反之亦然；
?对于任何字符串 x,x的任意真前缀 y
有惟一的一个真后缀 z与之对应, 使
得 x=yz,反之亦然 （ 除了 ε 以外 ） ；
? 对于任何字符串 x！ =ε,
x是自身的前缀, 但不是自身的真前缀；
x是自身的后缀, 但不是自身的真后缀；
? 对于任何字符串 x！ =ε,
ε 是 x的前缀, 且是真前缀；
ε 是 x的后缀, 且是真后缀；
? 对于任何字符串 x,x的前缀共有 |x|+1个 。
?12)语言的前缀性质
?设 L是某个字母表上的一个语言, 如 L
中的任何字符串都是另一个字符串的
真前缀, 则称语言 L具有前缀性质 。
?例如：
?字母表 {0,1}上的语言
?L1={0n|n>=0}
具有前缀性质；
?语言 L2={0n1|n>=0}
不具有前缀性质。
关于语言与句子
?设 ?是一个字母表,?L ??*,L称为
字母表 ?上的一个 语言 (language),?x
? L,x叫做 L的一个 句子 。
?可按语言的基数分为 有穷语言 与 无穷
语言 。
语言的乘积
?设 ?1,?2是二个字母表,L1??1*,L2
??2*,语言 L1与 L2的乘积是一个语言：
L1L2={xy | x ? L1,y ? L2}
该语言是字母表 ?1 ??2 上的语言。
例
? 字母表 {0,1}上的一些语言：
? {00,11}
? {0,1,00,11}
? {0}{0,1}*{1}
? {0,1}*{111}{0,1}*
例
? 令 ?= {0,1}，下面是 ?上语言的例子：
L = {0,1}
L = {0,1,00,01,10,11,…}= ?+
L = {?,0,1,00,01,10,11,…}= ?*
L = {0n1n | n ? 1}
L = {0n1m0k | n,m,k ? 1}
语言的 n次幂
?设 ?是一个字母表,?L ??*,L的 n次
幂是一个语言
(1) 当 n = 0时,Ln = {?}
(2) 当 n ? 1时,Ln = Ln-1 L
语言的闭包
?L的正闭包 L+是一个语言：
L+ = L? L2 ?L3 ?…
?L的克林闭包 L*是一个语言：
L* = L0 ? L+
1.7形式语言与自动机的发展
? 语言学家 Chomsky(乔姆斯基 )最早从产生
语言的角度研究语言 。 1956年, 通过抽象,
Chomsky将语言形式地定义为由一个字母
表的字母组成的一些串的集合：对于任意
语言 L,有一个字母表, 使得 LC∑ *。 可以
在字母表上按照一定的形成规则定义一个
文法, 该文法产生的所有的句子组成的集
合就是该文法产生的语言 。
? 1959年, Chomsky根据产生语言的文法的
产生式的不同特点, 将文法和对应产生的
语言分为三大类 。
? 数学家 Kleene（ 克林 ） 在 1951~1956年间,
从识别语言的角度来研究语言, 给出了语
言的另一种描述方式 。 Kleene在研究神经
细胞时建立了自动机模型, Kleene使用该
模型来识别 （ 接收 ） 一个语言：按照某种
识别规则构造自动机, 该自动机就定义了
一个语言, 该语言由自动机能够识别的所
有字符串构成 。
? 语言的两种不同的定义方式进一步引起了
人们的研究兴趣 。 一个语言, 可以采取不
同的描述方式：文法产生语言和自动机识
别语言 。 由于是同一个语言, 两种方式应
该是等价的, 也就存在两种方式之间的等
价的相互转换方法 。
? Chomsky于 1959年, 将他本人的形式语言
的研究成果和 Kleene的自动机的研究成果
结合起来, 不仅确定了文法和自动机分别
从产生和识别角度定义语言, 而且证明了
文法与自动机的等价性 。 此时, 形式语言
与自动机理论才真正诞生 。 并被置于数学
的光芒之下 。
? 形式语言与自动机理论出现后, 迅速在计算机
科学技术领域得到了应用 。 使用巴科斯 -诺尔范
式 （ BNF--Backus-Naur Form） 成功地对高级程
序设计语言 ALGOL-60的词法和语法规则进行了
形式化的描述 （ 实际上, 巴科斯 -诺尔范式就是
上下文无关文法的产生式另一种表示方式 ） 。
这一成功, 使得形式语言与自动机理论得到了
进一步的发展 。
? 尤其是上下文无关文法, 被作为计算机程
序设计语言语法的最佳近似描述得到了较
为深入的研究 。 后来, 人们又将上下文无
关文法应用到了模式匹配和模型化处理等
方面, 而这些内容都是算法描述和分析,
计算复杂性理论和可计算性理论的研究基
础 。
? 形式语言理论的研究对象与以前的所有语
言研究不同, 不止自然语言, 而是人类一
切语言：既有自然语言, 也有人工语言,
包括计算机编程的高级语言 。 乔姆斯基的
形式语言理论得到了多重验证, 于是才为
语言学界和计算机科学界所折服,, 引发
了语言学中伽利略式的科学革命的开端 。,
? 乔姆斯基的形式语言理论得到过计算机科
学的三种验证 。
? 验证一：乔氏 4型文法与 4种语言自动机一
一对应 。
? 验证二：计算机所使用的各种高级语言, 如
ALGOL,FORTRAN,PASCAL,C,LISP等, 都遵循
一种程序语言文法描述的范式, 即巴科斯 —瑙
尔范式 。 计算机科学家发现, 巴科斯 —瑙尔范
式等价于乔姆斯基的 2型文法, 即与上下文无关
文法 。 而乔姆斯基的 3型文法 ——正则文法, 在
研究文字的计算机模式识别时, 也被有效应用 。
于是, 乔氏的 4种类型文法被计算机科学界称作
乔姆斯基分类 。
? 验证三：乔姆斯基用形式语言理论的思想证明
了计算机科学的一个重大理论问题：计算机程
序语言是否有歧义性是不可判定的 。
? 20世纪中期, 程序语言 ALGOL60问世不久, 人们
发现它有歧义性 。 当计算机科学家绞尽脑汁寻
找办法来判断一种程序语言是否有歧义性时,
乔姆斯基用形式语言理论的思想证明, 一个任
意的上下文无关文法是否有歧义性是不可判定
的, 因此, 属于上下文无关文法的程序语言是
否有歧义性也是不可判定的 。 乔姆斯基的论证
令计算机科学界折服 。
?实际上, 形式语言与自动机理论除了
在计算机科学与技术领域的直接应用
外, 更在计算机计算机科学与技术领
域的人才的计算思维能力的培养中占
有极其重要的地位 。
? 计算机科学与技术学科强调 4个方面的专
业能力：计算思维能力、算法设计与分析
能力、程序设计与实现能力、计算机系统
的认知、分析、设计和运用能力。这也是
计算机科学与其他学科的重要区别。相关
的理论是计算机学科的基础。
? 理论方面的知识是计算机的真正灵魂。
?在本科阶段的学习过程中，学生以观
察、描述、比较、分类、推断、应用、
创造思维等科学思维过程为主，强调
自学的能力 在培养；
?研究生阶段，需要对学生进一步进行
抽象思维、逻辑思维、创造思维能力
的培养。
?建立物理符号系统并对起实施等价变
换是计算机学科进行问题描述和求解
的重要手段 。, 可行性, 所要求的
,形式化, 及其, 离散特征, 使得数
学成为重要的工具, 而计算模型无论
从方法还是从工具等方面, 都表现出
它在计算机上科学中的重要作用 。
?计算机科学与技术学科要求学生具有
形式化描述和抽象思维能力, 要求掌
握逻辑思维方法 。 这种能力就是计算
思维能力或计算机思维能力 。
?计算机学科系统地研究信息描述和变
换算法, 重要包括信息描述和变换算
法的理论, 分析, 效率, 实现和运用 。
学科的根本问题在于：什么能被 （ 有
效地 ） 自动化？ 学科的重要内容之一
是研究计算领域中的一些普遍规律,
描述算法的基本概念与模型 。
?计算思维能力的培养主要是通过基础
理论系列课程实现的，该系列是由数
学和抽象度较高的理论课程组成，包
括数学分析、集合和图论、形式语言
与自动机、近世代数、数学建模等课
程。
练习 (见习题 )
?1(1)
?4
?5(12)
?7(6)
?9
习题评讲
?1(1)
?{?,a,b,aa,ab,ba,bb,aaa,aab,
aba,abb,baa,bab,bba,bbb}
?4
习题评讲 (续 )
? 5(12)证明：
因为 A? B,并且 B ? C,则对任意 x? A,x
? B且 x ? C,因此 A ? C
由于 A? B,存在 y ? B,y ? A,而 B ? C,有
y ? C
因此 A? C
...
7(6)
? 对于任意 x ??*,
(1) 如果 |x| = 0,则 xT = x
(2)如果 |x| = 1,则 xT = x
(3)如果 |x| > 1,令 x = ya，其中 y ?
?*,a ??，则 xT = ayT
习题评讲 (续 )
?9
(1) {0}{0,1}*
(2) {0}{0,1}* {1}
(3) {11}{0,1}*{11}?{111} ?{11}
(4)
习题评讲 (续 )
(5) {{0,1}{0,1}}*
(6) ({0,1}{0,1})* {0,1}
(7) {0,1}*{01011} {0,1}*
(8) {0,1}*{000}{0,1}*
习题评讲 (续 )
(9) {0,1}9 {0}{0,1}*
(10) {0,1}* {0} {0,1}9
小结
?本章内容：
?复习 集合、关系、图 等相关知识
?引入 形式语言
?重点,掌握形式语言的基本定义
