1College of Computer Science & Technology
绪论
课程信息
为什么学习形式语言与自动机
形式语言与自动机概述及应用
课程内容及要求
2College of Computer Science & Technology
专业基础课
上世纪 60 年代末,70年代初,研究的高峰
之后，向应用领域渗透,研究生课程
近几年,本科阶段的专业基础课
专业工作者必须的理论素养
计算模型 计算机（不）能够做什么
问题分类 计算的复杂性，算法分析
形式系统 建模工具（状态机?）
抽象描述 形式文法、形式表达式课 程 性 质
3College of Computer Science & Technology
相 关 课 程
先修课程
,离散数学,（《数理逻辑》，《集合论》）
计算机导论与程序设计、数据结构
后续课程
,编译原理》
其它相关课程
《模式识别》、《算法分析,?
4College of Computer Science & Technology
参考教材,
形式语言与自动机王柏 杨娟 编著北京邮电大学出版社 2003.1
5College of Computer Science & Technology
经 典 参 考 书
书名 Introduction to Automata Theory,
Languages,and Computation
（ Second Edition）
作者 John E,Hopcroft （ Cornell）
Rajeev Motwani （ Stanford）
Jefferey D,Ullman （ Stanford）
出版社 Addison Wesley （ 2001）
清华大学出版社 （影印版）
First Edition 中译本,自动机理论、语言和计算导引,徐美瑞 等译 科学出版社,1990
John.E.Hopcroft,
the Turing Award
winner in 1986.
6College of Computer Science & Technology
其它参 考 书
《自动机理论及其应用》
何成武 科学出版社 1990
《形式语言及其句法分析》
美 A.V,阿霍 等 科学出版社 1987
《形式语言》
王兵山，吴兵 编 国防工业大学出版社,1988
《形式语言与自动机》
陈有祺 编著 南开大学出版社，天津,1999
7College of Computer Science & Technology
为什么学习形式语言与自动机
形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。
在人工智能、电信领域等有广泛的应用。
通过一些定理的证明和应用,对大家进行思维训练,从而为今后学习通信软件,协议工程,编译技术,人工智能等内容提供理论基础 。
8College of Computer Science & Technology
对客观世界的科学研究：目的在于把抽象数学的形式化体系发展成为与现实生活相似的理论模型，从而提供一种通用结构来描述、
理解和解决问题。
计算机科学：是关于计算知识的有系统的整体。
9College of Computer Science & Technology
计算机科学的两个主要部分：
构成计算基础的一些基本概念和模型；
设计计算系统 (软件和硬件 )的工程技术（设计理论的应用）
本课程着重介绍第一部分 （ 涉及到一些第二部分的应用 ）,通过形式化技术对大家进行思维训练,为今后的学习打好理论基础 。
10College of Computer Science & Technology
形式语言与自动机概述及应用
本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述 。
核心内容
有限状态自动机，正规语言，正规表达式
上下文无关文法，上下文无关语言，下推自动机
图灵机，计算问题分类
11College of Computer Science & Technology
1,形式语言
什么是形式语言
形式语言,形式化描述的字母表上的字符串的集合 。
字母表,字符的有限集合 。
e.g.,26个英文字母构成的字母表 。
字符串,字母表中的字符构成的有限序列 。
e.g,hello,afjhkfyu
12College of Computer Science & Technology
为什么用形式语言
自然语言,人们平时说话时所使用的一种语言,不同的国家和民族有着不同的语言 。
形式语言
通过人们公认的符号,表达方式所描述的一种语言,是一种通用语言,没有国籍之分 。
形式语言是某个字母表上的字符串的集合,
有一定的描述范围 。
13College of Computer Science & Technology
例 1,汉语,<主 > <谓 > <宾 > ―― 用数字,符号等形式化的东西来描述语言
我吃饭 ―― 语法正确
我饭吃 ―― 语法错误
饭吃我 ―― 语法正确,语义错误
14College of Computer Science & Technology
例 2,T为 PASCAL语言所用的全部符号的集合 。
正确的 PASCAL程序就是 T上的语言 。
例 3：在字母表 T={a}上,L= {a 2n+1 | n >=0 }
表示任意一对 aa (包括 0对 ) 后跟一个 a的字符串 。 （ 即含有奇数个 a的字符串 。 ）
15College of Computer Science & Technology
形式语言的最初起因,语言学家 （ Chomsky）
想用一套形式化方法来描述语言 。
形式语言在自然语言研究中起步,在计算机科学中得到广泛应用 。
最初的应用：编译 ―― 让计算机按照语法规则将高级语言方便地翻译成机器语言 。
16College of Computer Science & Technology
现在,已广泛应用在人工智能、图象处理、
通信协议、通信软件等多个领域
在计算机理论科学方面：
是可计算理论（算法 ― 在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。
17College of Computer Science & Technology
比尔,盖茨：人类计算的未来是让计算机能够看、听、学，能用自然语言与人类交流
形式化非常重要
18College of Computer Science & Technology
2,自动机
什么是自动机？
具有离散输入输出的数学模型 。
大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。
19College of Computer Science & Technology
自动机接受一定的输入，执行一定的动作，
产生一定的结果。使用状态迁移描述整个工作过程。
状态,一个标识,能区分自动机在不同时刻的状况 。 有限状态系统具有任意有限数目的内部,状态,
自动机的本质,根据状态,输入和规则决定下一个状态状态 ＋ 输入 （ 激励 ） ＋ 规则 ―> 状态迁移
20College of Computer Science & Technology
为什么叫自动机？
可能的状态、运行的规则都是事先确定的。
一旦开始运行，就按照事先确定的规则工作，
因此叫“自动机”。
有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。
21College of Computer Science & Technology
例 1：打电话 (自动机在通信领域的应用 )。
在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用四个状态来表示。
q0
q1 q2
q3
q4
摘机收到拨号音拨号收应答信号挂机
q0:空闲状态
q1:等待拨号状态
q2:可以拨号状态
q3:等待应答状态
q4:通话状态
22College of Computer Science & Technology
例 2：串口通信两台微机通过串口通信,需在两台机器间建立好连接后,
才可以传递数据,可以使用有限状态自动机,描述串口通信的状态 。
传输数据收到应答断开连接连接请求q
0 q1
q2
23College of Computer Science & Technology
根据结构不同，自动机又可分为有限自动机，
下推自动机，图灵机等。
下推自动机可以看作是由一条输入带,一个有限控制器和一个下推栈组成 。
基本图灵机由一个具有读写头的有限控制器和一条无限带组成 。
使用自动机,可以形式化的描述现实世界中的一些问题 。
24College of Computer Science & Technology
3．形式语言与自动机的关系
形式语言和自动机是密切相关的 。
形式语言 ―― 字符串
自动机 ―― 字符串的识别系统
根据复杂程度可将形式语言分类,根据自动机的接受能力,处理能力的不同也将自动机分类 。 二者之间具有较好的对应关系 。
25College of Computer Science & Technology
26College of Computer Science & Technology
语言与有限自动机 （ Finite Automata）
设? =? 0,1?,L =? w? w 中至少有一个 0?，
如 0011,10,110111? L,而 11,?,1111? L。
下图是一个可接受该语言的有限状态自动机?
1 2
S t a r t 0,1
0
1
27College of Computer Science & Technology
小结
文法是定义语言的一个数学模型,而自动机可看作是语言的识别系统 。
通过对一些定理的证明,说明对于一个文法产生的语言,可以构造相应自动机接受该语言：
一个自动机接受的语言,可以构造对应的文法产生该语言 。 一定类型的自动机和某种类型的文法具有等价性 。
28College of Computer Science & Technology
课程内容及要求
课程内容,书上二,三,四,五,六章 。
要求：通过本课学习,要求同学们掌握形式化描述方法,建立起形式语言与自动机的概念,并能在实际中加以应用 。
通过对定理的证明,对同学们进行思维训练,
并掌握一定的证明方法 。
29College of Computer Science & Technology
证 明 技 术 *
基本证明方法
归纳证明技术
* 引自清华大学计算机系软件技术研究所王生原老师课件
30College of Computer Science & Technology
演 绎 证 明
概念 一个 证明 （ proof） 是命题的序列，
其中的每一个命题或者是已知的命题，或者是由前面出现过的命题使用逻辑公理和规则得出,
已知的命题集合称为 假设 （ hypothesis） 或 前提 （ premise）,最后一个命 题称为该前提的结论 （ conclusion）,
31College of Computer Science & Technology
,If – Then”命题
证明方法把 If 部分作为已知的命题，把 Then 部分作为结论,
举例 如果 x+y=1,那么 x2-y2=x-y.
证明,
1 x2-y2 = (x+y)(x-y) // 数学 公理
2 (x+y) = 1 // 已知
3 x2-y2 = x-y // 由 1,2 和算术性质推出
32College of Computer Science & Technology
,If - And - Only - If,命题
欲证 A if and only if B，
可分别证明如下两个命题：
1 if A then B，
2 if B then A.
33College of Computer Science & Technology
有关集合的命题设 R,S 为集合,
欲证 R? S，
可证明如下命题：
if x?R then x?S
欲证 R = S，
可分别证明如下两个命题：
1 if x?R then x?S
2 if x?S then x?R
34College of Computer Science & Technology
原命题的逆否命题有时，证明原命题的逆否 (contrapositive)
命题更加方便,
欲证 if A then B,
可证明如下命题：
if not B then not A
35College of Computer Science & Technology
反证法
反证（ proof by contradiction）
欲证 if H then C,可以把 H 和 not C
都作为已知的命题，把任何一个矛盾 ( contradiction )
命题作为新的结论,
36College of Computer Science & Technology
举例证明或否证
举例证明存在量化的命题如命题：存在整数 a,满足 a2 = 2a.
证明,取 a = 2.,满足 a2 = 2a,
举反例否定全称量化的命题如命题：所有整数 a,都满足 a2=2a.
否证,取 a = 1.,不满足 a2 = 2a,
37College of Computer Science & Technology
集合的归纳定义由 3 部分构成：
1 基础 （ basis） // 直接定义集合中的元素（至少 1个）
2 归纳 （ induction） // 从已知元素生成新元素的规则
3 极小性限制 // 申明集合中的元素只能由 1,2 生成
结构归纳法对于归纳定义的集合 S,欲证对于任意 x?S,满足性质 P(x).
1 基础 （ basis） // 若有直接定义 a?S,则证明 P(a)
2 归纳 （ induction） // 若归纳定义中有规则
if a1,a2,?,an? S then f (a1,a2,?,an )? S,则证明
if P( a1 ),P( a2 ),?,P( an )? S then P( f (a1,a2,?,an ) )
归 纳 定 义 与 结 构 归 纳 法
38College of Computer Science & Technology
归纳定义 合法括号串的集合 S
1 基础 空串S
2 归纳 若 x?S,则 (x)?S ；
若 x,y? S,则 xy? S,
3 极小性限制 S 中的元素只能由 1,2 生成
(或,S是满足 1,2的最小集合 )
命题：合法括号串集合 S 中每个括号串的,(”与,)”数目相等证明,
1 基础 空串? 的,(”与,)”数目相等，都为 0；
2 归纳 设 x,y 的,(”与,)”数目相等，前者为 m,后者为 n ；
(x) 的,(”与,)”数目都为 m+1；
xy 的,(”与,)”数目都为 m+n,
归纳定义与结构归纳证明（ 例 ）
39College of Computer Science & Technology
自然数 自然数集合 N是满足如下条件的最小集合：
(1) 0? N; (2) 若 n? N,则 n的后继 n+1? N
数学归纳法 欲证对任意自然数 n,P(n)成立,(1) 先证
P(0) 成立 ; (2) 再证若 P(n)成立,则 P(n+1 )成立
另一种形式 (1) 先证 P(0) 成立 ; (2) 再证若对任意 k<n，
P(k) 成立,则 P(n)成立
对任何良序集合，都可以有这两种形式基于自然数的归纳 — 一般数学归纳法
绪论
课程信息
为什么学习形式语言与自动机
形式语言与自动机概述及应用
课程内容及要求
2College of Computer Science & Technology
专业基础课
上世纪 60 年代末,70年代初,研究的高峰
之后，向应用领域渗透,研究生课程
近几年,本科阶段的专业基础课
专业工作者必须的理论素养
计算模型 计算机（不）能够做什么
问题分类 计算的复杂性，算法分析
形式系统 建模工具（状态机?）
抽象描述 形式文法、形式表达式课 程 性 质
3College of Computer Science & Technology
相 关 课 程
先修课程
,离散数学,（《数理逻辑》，《集合论》）
计算机导论与程序设计、数据结构
后续课程
,编译原理》
其它相关课程
《模式识别》、《算法分析,?
4College of Computer Science & Technology
参考教材,
形式语言与自动机王柏 杨娟 编著北京邮电大学出版社 2003.1
5College of Computer Science & Technology
经 典 参 考 书
书名 Introduction to Automata Theory,
Languages,and Computation
（ Second Edition）
作者 John E,Hopcroft （ Cornell）
Rajeev Motwani （ Stanford）
Jefferey D,Ullman （ Stanford）
出版社 Addison Wesley （ 2001）
清华大学出版社 （影印版）
First Edition 中译本,自动机理论、语言和计算导引,徐美瑞 等译 科学出版社,1990
John.E.Hopcroft,
the Turing Award
winner in 1986.
6College of Computer Science & Technology
其它参 考 书
《自动机理论及其应用》
何成武 科学出版社 1990
《形式语言及其句法分析》
美 A.V,阿霍 等 科学出版社 1987
《形式语言》
王兵山，吴兵 编 国防工业大学出版社,1988
《形式语言与自动机》
陈有祺 编著 南开大学出版社，天津,1999
7College of Computer Science & Technology
为什么学习形式语言与自动机
形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。
在人工智能、电信领域等有广泛的应用。
通过一些定理的证明和应用,对大家进行思维训练,从而为今后学习通信软件,协议工程,编译技术,人工智能等内容提供理论基础 。
8College of Computer Science & Technology
对客观世界的科学研究：目的在于把抽象数学的形式化体系发展成为与现实生活相似的理论模型，从而提供一种通用结构来描述、
理解和解决问题。
计算机科学：是关于计算知识的有系统的整体。
9College of Computer Science & Technology
计算机科学的两个主要部分：
构成计算基础的一些基本概念和模型；
设计计算系统 (软件和硬件 )的工程技术（设计理论的应用）
本课程着重介绍第一部分 （ 涉及到一些第二部分的应用 ）,通过形式化技术对大家进行思维训练,为今后的学习打好理论基础 。
10College of Computer Science & Technology
形式语言与自动机概述及应用
本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述 。
核心内容
有限状态自动机，正规语言，正规表达式
上下文无关文法，上下文无关语言，下推自动机
图灵机，计算问题分类
11College of Computer Science & Technology
1,形式语言
什么是形式语言
形式语言,形式化描述的字母表上的字符串的集合 。
字母表,字符的有限集合 。
e.g.,26个英文字母构成的字母表 。
字符串,字母表中的字符构成的有限序列 。
e.g,hello,afjhkfyu
12College of Computer Science & Technology
为什么用形式语言
自然语言,人们平时说话时所使用的一种语言,不同的国家和民族有着不同的语言 。
形式语言
通过人们公认的符号,表达方式所描述的一种语言,是一种通用语言,没有国籍之分 。
形式语言是某个字母表上的字符串的集合,
有一定的描述范围 。
13College of Computer Science & Technology
例 1,汉语,<主 > <谓 > <宾 > ―― 用数字,符号等形式化的东西来描述语言
我吃饭 ―― 语法正确
我饭吃 ―― 语法错误
饭吃我 ―― 语法正确,语义错误
14College of Computer Science & Technology
例 2,T为 PASCAL语言所用的全部符号的集合 。
正确的 PASCAL程序就是 T上的语言 。
例 3：在字母表 T={a}上,L= {a 2n+1 | n >=0 }
表示任意一对 aa (包括 0对 ) 后跟一个 a的字符串 。 （ 即含有奇数个 a的字符串 。 ）
15College of Computer Science & Technology
形式语言的最初起因,语言学家 （ Chomsky）
想用一套形式化方法来描述语言 。
形式语言在自然语言研究中起步,在计算机科学中得到广泛应用 。
最初的应用：编译 ―― 让计算机按照语法规则将高级语言方便地翻译成机器语言 。
16College of Computer Science & Technology
现在,已广泛应用在人工智能、图象处理、
通信协议、通信软件等多个领域
在计算机理论科学方面：
是可计算理论（算法 ― 在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。
17College of Computer Science & Technology
比尔,盖茨：人类计算的未来是让计算机能够看、听、学，能用自然语言与人类交流
形式化非常重要
18College of Computer Science & Technology
2,自动机
什么是自动机？
具有离散输入输出的数学模型 。
大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。
19College of Computer Science & Technology
自动机接受一定的输入，执行一定的动作，
产生一定的结果。使用状态迁移描述整个工作过程。
状态,一个标识,能区分自动机在不同时刻的状况 。 有限状态系统具有任意有限数目的内部,状态,
自动机的本质,根据状态,输入和规则决定下一个状态状态 ＋ 输入 （ 激励 ） ＋ 规则 ―> 状态迁移
20College of Computer Science & Technology
为什么叫自动机？
可能的状态、运行的规则都是事先确定的。
一旦开始运行，就按照事先确定的规则工作，
因此叫“自动机”。
有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。
21College of Computer Science & Technology
例 1：打电话 (自动机在通信领域的应用 )。
在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用四个状态来表示。
q0
q1 q2
q3
q4
摘机收到拨号音拨号收应答信号挂机
q0:空闲状态
q1:等待拨号状态
q2:可以拨号状态
q3:等待应答状态
q4:通话状态
22College of Computer Science & Technology
例 2：串口通信两台微机通过串口通信,需在两台机器间建立好连接后,
才可以传递数据,可以使用有限状态自动机,描述串口通信的状态 。
传输数据收到应答断开连接连接请求q
0 q1
q2
23College of Computer Science & Technology
根据结构不同，自动机又可分为有限自动机，
下推自动机，图灵机等。
下推自动机可以看作是由一条输入带,一个有限控制器和一个下推栈组成 。
基本图灵机由一个具有读写头的有限控制器和一条无限带组成 。
使用自动机,可以形式化的描述现实世界中的一些问题 。
24College of Computer Science & Technology
3．形式语言与自动机的关系
形式语言和自动机是密切相关的 。
形式语言 ―― 字符串
自动机 ―― 字符串的识别系统
根据复杂程度可将形式语言分类,根据自动机的接受能力,处理能力的不同也将自动机分类 。 二者之间具有较好的对应关系 。
25College of Computer Science & Technology
26College of Computer Science & Technology
语言与有限自动机 （ Finite Automata）
设? =? 0,1?,L =? w? w 中至少有一个 0?，
如 0011,10,110111? L,而 11,?,1111? L。
下图是一个可接受该语言的有限状态自动机?
1 2
S t a r t 0,1
0
1
27College of Computer Science & Technology
小结
文法是定义语言的一个数学模型,而自动机可看作是语言的识别系统 。
通过对一些定理的证明,说明对于一个文法产生的语言,可以构造相应自动机接受该语言：
一个自动机接受的语言,可以构造对应的文法产生该语言 。 一定类型的自动机和某种类型的文法具有等价性 。
28College of Computer Science & Technology
课程内容及要求
课程内容,书上二,三,四,五,六章 。
要求：通过本课学习,要求同学们掌握形式化描述方法,建立起形式语言与自动机的概念,并能在实际中加以应用 。
通过对定理的证明,对同学们进行思维训练,
并掌握一定的证明方法 。
29College of Computer Science & Technology
证 明 技 术 *
基本证明方法
归纳证明技术
* 引自清华大学计算机系软件技术研究所王生原老师课件
30College of Computer Science & Technology
演 绎 证 明
概念 一个 证明 （ proof） 是命题的序列，
其中的每一个命题或者是已知的命题，或者是由前面出现过的命题使用逻辑公理和规则得出,
已知的命题集合称为 假设 （ hypothesis） 或 前提 （ premise）,最后一个命 题称为该前提的结论 （ conclusion）,
31College of Computer Science & Technology
,If – Then”命题
证明方法把 If 部分作为已知的命题，把 Then 部分作为结论,
举例 如果 x+y=1,那么 x2-y2=x-y.
证明,
1 x2-y2 = (x+y)(x-y) // 数学 公理
2 (x+y) = 1 // 已知
3 x2-y2 = x-y // 由 1,2 和算术性质推出
32College of Computer Science & Technology
,If - And - Only - If,命题
欲证 A if and only if B，
可分别证明如下两个命题：
1 if A then B，
2 if B then A.
33College of Computer Science & Technology
有关集合的命题设 R,S 为集合,
欲证 R? S，
可证明如下命题：
if x?R then x?S
欲证 R = S，
可分别证明如下两个命题：
1 if x?R then x?S
2 if x?S then x?R
34College of Computer Science & Technology
原命题的逆否命题有时，证明原命题的逆否 (contrapositive)
命题更加方便,
欲证 if A then B,
可证明如下命题：
if not B then not A
35College of Computer Science & Technology
反证法
反证（ proof by contradiction）
欲证 if H then C,可以把 H 和 not C
都作为已知的命题，把任何一个矛盾 ( contradiction )
命题作为新的结论,
36College of Computer Science & Technology
举例证明或否证
举例证明存在量化的命题如命题：存在整数 a,满足 a2 = 2a.
证明,取 a = 2.,满足 a2 = 2a,
举反例否定全称量化的命题如命题：所有整数 a,都满足 a2=2a.
否证,取 a = 1.,不满足 a2 = 2a,
37College of Computer Science & Technology
集合的归纳定义由 3 部分构成：
1 基础 （ basis） // 直接定义集合中的元素（至少 1个）
2 归纳 （ induction） // 从已知元素生成新元素的规则
3 极小性限制 // 申明集合中的元素只能由 1,2 生成
结构归纳法对于归纳定义的集合 S,欲证对于任意 x?S,满足性质 P(x).
1 基础 （ basis） // 若有直接定义 a?S,则证明 P(a)
2 归纳 （ induction） // 若归纳定义中有规则
if a1,a2,?,an? S then f (a1,a2,?,an )? S,则证明
if P( a1 ),P( a2 ),?,P( an )? S then P( f (a1,a2,?,an ) )
归 纳 定 义 与 结 构 归 纳 法
38College of Computer Science & Technology
归纳定义 合法括号串的集合 S
1 基础 空串S
2 归纳 若 x?S,则 (x)?S ；
若 x,y? S,则 xy? S,
3 极小性限制 S 中的元素只能由 1,2 生成
(或,S是满足 1,2的最小集合 )
命题：合法括号串集合 S 中每个括号串的,(”与,)”数目相等证明,
1 基础 空串? 的,(”与,)”数目相等，都为 0；
2 归纳 设 x,y 的,(”与,)”数目相等，前者为 m,后者为 n ；
(x) 的,(”与,)”数目都为 m+1；
xy 的,(”与,)”数目都为 m+n,
归纳定义与结构归纳证明（ 例 ）
39College of Computer Science & Technology
自然数 自然数集合 N是满足如下条件的最小集合：
(1) 0? N; (2) 若 n? N,则 n的后继 n+1? N
数学归纳法 欲证对任意自然数 n,P(n)成立,(1) 先证
P(0) 成立 ; (2) 再证若 P(n)成立,则 P(n+1 )成立
另一种形式 (1) 先证 P(0) 成立 ; (2) 再证若对任意 k<n，
P(k) 成立,则 P(n)成立
对任何良序集合，都可以有这两种形式基于自然数的归纳 — 一般数学归纳法
