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