绪论 课程信息 为什么学习形式语言与自动机 形式语言与自动机概述及应用 课程内容及要求 College of Computer Science Technology
College of Computer Science & Technology 1 绪论 ◼ 课程信息 ◼ 为什么学习形式语言与自动机 ◼ 形式语言与自动机概述及应用 ◼ 课程内容及要求
课程性质 ◇专业基础课 上世纪60年代末、70年代初,研究的高峰 之后,向应用领域渗透,研究生课程 近几年,本科阶段的专业基础课 ◇专业工作者必须的理论素养 计算模型计算机(不)能够做什么 问题分类计算的复杂性,算法分析 形式系统建模工具(状态机…) 抽象描述形式文法、形式表达式 College of Computer Science Technology
College of Computer Science & Technology 2 专业基础课 − 上世纪 60 年代末、70年代初，研究的高峰 − 之后，向应用领域渗透，研究生课程 − 近几年，本科阶段的专业基础课 专业工作者必须的理论素养 − 计算模型 计算机（不）能够做什么 − 问题分类 计算的复杂性，算法分析 − 形式系统 建模工具（状态机 ） − 抽象描述 形式文法、形式表达式 课 程 性 质
相关嫘程 ◇先修课程 《离散数学》(《数理逻辑》,《集合论》) 计算机导论与程序设计、数据结构 ◇后续课程 《编译原理》 ◇其它相关课程 《模式识别》、《算法分析》 College of Computer Science Technology
College of Computer Science & Technology 3 相 关 课 程 先修课程 − 《离散数学》（《数理逻辑》，《集合论》） − 计算机导论与程序设计、数据结构 后续课程 − 《编译原理》 其它相关课程 《模式识别》、《算法分析》
参考教材: 形式语言与自动机 王柏杨娟编著 北京邮电大学出版社20031 College of Computer Science Technology
College of Computer Science & Technology 4 ◼ 参考教材： 形式语言与自动机 王柏 杨娟 编著 北京邮电大学出版社 2003.1
经典参考书 ◇书名 Introduction to Automata Theory Languages, and computation Second Edition ◇作者 John e. Hopcroft( Cornell Rajeev Motwani( Stanford) John E Hopcroft, Jefferey D. Ullman Stanford) the turing Award ◇出版社 Addison Wesley(2001) 清华大学出版社(影印版) ◇ First Edition中铎本《自酌机理论、语言和计 算导引》徐瑞等铎斛学出版牡,1990 College of Computer Science Technology
College of Computer Science & Technology 5 经 典 参 考 书 书名 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
其它参考书 ◇《自动机理论及其应用》 何成武科学出版社1990 ◇《形式语言及其句法分析》 美A..阿霍等科学出版社1987 ◇《形式语言》 王兵山,吴兵编国防工业大学出版社,1988 ◇《形式语言与自动机》 陈有祺编著南开大学出版社,天津,1999 College of Computer Science Technology
College of Computer Science & Technology 6 其它参 考 书 《自动机理论及其应用》 何成武 科学出版社1990 《形式语言及其句法分析》 美A.V. 阿霍 等 科学出版社1987 《形式语言》 王兵山，吴兵 编 国防工业大学出版社，1988 《形式语言与自动机》 陈有祺 编著 南开大学出版社，天津，1999
为什么学习形式语言与自动机 ■形式语言与自动机是计算机科学的基础理论 之一,是计算机学科的专业基础课 在人工智能、电信领垃等有广泛的应用。 通过一些定理的证明和应用,对大家进行思 维训练,从而为今后学习通信软件,协议工 程,编译技术,人工智能等内容提供理论基 础 College of Computer Science Technology
College of Computer Science & Technology 7 为什么学习形式语言与自动机 ◼ 形式语言与自动机是计算机科学的基础理论 之一，是计算机学科的专业基础课。 ◼ 在人工智能、电信领域等有广泛的应用。 ◼ 通过一些定理的证明和应用，对大家进行思 维训练，从而为今后学习通信软件，协议工 程，编译技术，人工智能等内容提供理论基 础
对客观世界的科学研究:目的在于把抽象数 学的形式化体系发展成为与现实生活相似的 理论模型,从而提供一种通用结构来描述、 理解和解决问题。 计算机科学:是关于计算知识的有系统的整 College of Computer Science Technology
College of Computer Science & Technology 8 ◼ 对客观世界的科学研究：目的在于把抽象数 学的形式化体系发展成为与现实生活相似的 理论模型，从而提供一种通用结构来描述、 理解和解决问题。 ◼ 计算机科学：是关于计算知识的有系统的整 体
计算机科学的两个主要部分 a构成计算基础的一些基本概念和模型; 设计计算系统(软件和硬件)的工程技 术(设计理论的应用) 本课程着重介绍第一部分(涉及到一些 第二部分的应用),通过形式化技术对 大家进行思维训练,为今后的学习打好 理论基础。 College of Computer Science Technology
College of Computer Science & Technology 9 ◼ 计算机科学的两个主要部分： ◼ 构成计算基础的一些基本概念和模型； ◼ 设计计算系统(软件和硬件)的工程技 术（设计理论的应用） ◼ 本课程着重介绍第一部分（涉及到一些 第二部分的应用），通过形式化技术对 大家进行思维训练，为今后的学习打好 理论基础
形式语言与自动机概述及应用 本门课程将围绕着什么是形式语言、什么是 自动机、以及形式语言和自动机的相互关系 进行阐述。 核心内容 有限状态自动机,正规语言,正规表达式 上下文无关文法,上下文无关语言,下推 自动机 图灵机,计算问题分类 College of Computer Science Technology
College of Computer Science & Technology 10 形式语言与自动机概述及应用 ◼ 本门课程将围绕着什么是形式语言、什么是 自动机、以及形式语言和自动机的相互关系 进行阐述。 ◼ 核心内容 − 有限状态自动机，正规语言，正规表达式 − 上下文无关文法，上下文无关语言，下推 自动机 − 图灵机，计算问题分类