形式语言与自动机理论 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