课程详情
课程评价
spContent=为了探索“计算”的本质，需要使用和构造什么样的计算模型，就是计算理论入门课程“形式语言与自动机理论”的主要内容。这些模型都是高度抽象化的计算装置，简单明确但功能强大，不但便于在理论分析中进行推导和证明，在很多实际问题中也有非常直接的应用。
—— 课程团队
课程概述

计算理论是关于计算知识的有系统的整体，本是数学的一个研究领域，诞生于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的算术 (Calculation)，而是指一种以 “机械而有效的” 方式获取问题答案的过程。随着计算理论的发展最终促使了计算机的发明，计算理论的重心也从数学转到了计算机科学，而计算理论关心的核心问题是：


计算（机）的基本能力和限制究竟是什么?


这个问题中包含了两个内容，分别对应计算理论的两个研究方向：可计算性理论和计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究方向的理论基础。


为了能够严谨的研究这种机械而有效的计算过程，我们需要严格定义的概念去描述它，需要严谨的计算模型去分析它。这个概念，其实就是已经被我们大家所熟知的“算法”(Algorithm)；而这些模型呢，就是我们将要在课程中主要学习的自动机理论，包括有穷自动机、下推自动机和图灵机等几种自动机装置，还包括一些与自动机形式上不相似但能力上却完全相同的模型，如正则表达式和文法等。

授课目标

形式语言与自动机理论是计算机科学与技术领域基本的思想和方法，它不仅是编译技术的基础，在诸如计算机网络协议、文件搜索、数字电路设计和验证等诸多领域也发挥着重要作用。本课程旨在培养学生形式化描述和抽象思维能力,掌握“问题——形式化描述——自动化（计算机求解）”的思想和方法，并用于解决实际问题。


课程目标1：掌握正则语言与上下文无关语言等语言的形式化描述方法和识别方法，能够设计与之相应的文法和自动机，培养学生的抽象思维能力和逻辑思维能力。


课程目标2：分类研究语言的性质，培养针对不同语言的模型描述能力和模型计算能力（包括模型的等价变换、推理等），能够在更高的抽象层面处理复杂工程问题，进而尝试探讨问题的可计算性及其计算的复杂性。


课程目标3：掌握由问题到形式化描述、再到计算机化的问题求解方法，能够对实际问题进行抽象、形式化，构建计算模型，进而用计算机予以解决。

课程大纲
预备知识

集合论与图论

参考资料
  1. Introduction to Automata Theory, Languages, and Computation - 3rd Edition
  2. 作者 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
  3. 国内影印版
  4. 《自动机理论、语言和计算导论》(英文版·第3版)
  5. 机械工业出版社，ISBN: 9787111223924
  6. Introduction to the Theory of Computation
  7. 作者 Michael Sipser
  8. 中文译版《计算理论导引》机械工业出版社
  9. An Introduction to Formal Languages and Automata
  10. 作者 Peter Linz & Susan H. Rodger