哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）24 形式语言与自动机介绍

绪论 课程信息 为什么学习形式语言与自动机 形式语言与自动机概述及应用 课程内容及要求 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 形式语言与自动机概述及应用 ◼ 本门课程将围绕着什么是形式语言、什么是 自动机、以及形式语言和自动机的相互关系 进行阐述。 ◼ 核心内容 − 有限状态自动机，正规语言，正规表达式 − 上下文无关文法，上下文无关语言，下推 自动机 − 图灵机，计算问题分类