形式语言与自动机.pptxVIP

课程名称形式语言与自动机教师姓名杨娟（计算机学院软件工程中心）电话62283779信箱yangjuan@bupt.edu.cn程信息为什么学习形式语言与自动机形式语言与自动机概述及应用课程内容及要求

上世纪60年代末、70年代初，研究的高峰之后，向应用领域渗透，研究生课程近几年，本科阶段的专业基础课专业基础课01计算模型计算机（不）能够做什么问题分类计算的复杂性，算法分析形式系统建模工具（状态机?）抽象描述形式文法、形式表达式专业工作者必须的理论素养02

相关课程42025/4/15CollegeofComputerScienceTechnology,BUPT先修课程《离散数学》（《数理逻辑》，《集合论》）计算机导论与程序设计、数据结构后续课程《编译原理》其它相关课程《模式识别》、《算法分析》?

教材：52025/4/15CollegeofComputerScienceTechnology,BUPT北京邮电大学出版社2003.103王柏杨娟编著02形式语言与自动机01

书名IntroductiontoAutomataTheory,Languages,andComputation（SecondEdition）作者JohnE.Hopcroft（Cornell）RajeevMotwani（Stanford）JeffereyD.Ullman（Stanford）出版社AddisonWesley（2001）清华大学出版社（影印版）FirstEdition中译本《自动机理论、语言和计算导引》徐美瑞等译科学出版社，1990John.E.Hopcroft,theTuringAwardwinnerin1986.

蒋宗礼，姜守旭.清华大学出版社，2003《形式语言与自动机理论》04王兵山，吴兵编国防工业大学出版社，1988《形式语言》03美A.V.阿霍等科学出版社1987《形式语言及其句法分析》02何成武科学出版社1990《自动机理论及其应用》01陈有祺编著机械工业出版社，2008《形式语言与自动机》05

形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。在人工智能、电信领域等有广泛的应用。通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基础。

对客观世界的科学研究：目的在于把抽象数学的形式化体系发展成为与现实生活相似的理论模型，从而提供一种通用结构来描述、理解和解决问题。计算机科学：是关于计算知识的有系统的整体。算机科学的两个主要部分：构成计算基础的一些基本概念和模型；设计计算系统(软件和硬件)的工程技术（设计理论的应用）本课程着重介绍第一部分（涉及到一些第二部分的应用），通过形式化技术对大家进行思维训练，为今后的学习打好理论基础。

4种基本的专业能力1计算思维能力2算法的设计与分析能力3程序设计和实现能力4计算机软硬件系统的认知、分析、设计与应用能力5计算思维能力6逻辑思维能力和抽象思维能力7构造模型对问题进行形式化描述8理解和处理形式模型9

能力培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。010302

本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。核心内容有限状态自动机，正规语言，正规表达式上下文无关文法，上下文无关语言，下推自动机图灵机，计算问题分类

1什么是形式语言3字母表：字符的有限集合。2形式语言:形式化描述的字母表上的字符串的集合。4e.g.：26个英文字母构成的字母表。5字符串：字母表中的字符构成的有限序列。6e.g.hello,afjhkfyu

通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之分。自然语言：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。形式语言形式语言是某个字母表上的字符串的集合，有一定的描述范围。

例1：汉语：主谓宾――用数字、符号等形式化的东西来描述语言我吃饭――语法正确我饭吃――语法错误饭吃我――语