文档介绍：形式语言与自动机理论Formal Languages and Automata Theory
蒋宗礼
11/10/2017
1
课程目的和基本要求
课程性质
技术基础
基础知识要求
数学分析(或者高等数学),离散数学
主要特点
抽象和形式化
理论证明和构造性
基本模型的建立与性质
11/10/2017
2
课程目的和基本要求
本专业人员4种基本的专业能力
计算思维能力
算法的设计与分析能力
程序设计和实现能力
计算机软硬件系统的认知、分析、设计与应用能力
计算思维能力
逻辑思维能力和抽象思维能力
构造模型对问题进行形式化描述
理解和处理形式模型
11/10/2017
3
课程目的和基本要求
知识
掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。
能力
培养学生的形式化描述和抽象思维能力。
使学生了解和初步掌握“问题、形式化描述、自动化(计算机化)”这一最典型的计算机问题求解思路。
11/10/2017
4
主要内容
语言的文法描述。
RL
RG、 FA、RE、RL的性质。
CFL
F、GNF)、PDA、CFL的性质。
TM
基本TM、构造技术、TM的修改。
CSL
CSG、LBA。
11/10/2017
5
教材及主要参考书目
蒋宗礼,姜守旭. 形式语言与自动机理论. 北京:清华大学出版社,2003年
John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, putation (2nd Edition). Addison-Wesley pany, 2001
John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, putation. Addison-Wesley pany, 1979
11/10/2017
6
第1章  绪论
集合的基础知识
集合及其表示
集合:一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set),简称为集(set)。
元素:集合的成员为该集合的元素(element)。
集合描述形式。
基数。
集合的分类。
11/10/2017
7
集合之间的关系
子集
如果集合A中的每个元素都是集合B的元素,则称集合A是集合B的子集(subset),集合B是集合A的包集(container)。记作AB。也可记作BA。AB读作集合A包含在集合B中;BA读作集合B包含集合A。
如果AB,且x∈B,但xA,则称A是B的真子集(proper subset),记作AB
11/10/2017
8
集合之间的关系
集合相等
如果集合A,B含有的元素完全相同,则称集合A与集合B相等(equivalence),记作A=B。
对任意集合A、B、C:
⑴ A=B iff AB且BA。
⑵如果AB,则|A|≤|B|。
⑶如果AB,则|A|≤|B|。
⑷如果A是有穷集,且AB,则|B|>|A|。
11/10/2017
9
集合之间的关系
⑸如果AB,则对x∈A,有x∈B。
⑹如果AB,则对x∈A,有x∈B并且x∈B,但xA。
⑺如果AB且BC,则AC。
⑻如果AB且BC,或者AB且BC,或者AB且BC,则AC。
⑼如果A=B,则|A|=|B|。
11/10/2017
10