形式语言与自动机理论（哈工大）学习笔记Day01

作为计算机科学的核心，计算理论的重心经历了从数学转移到计算机科学的过程。

计算机科学关心的核心问题：计算机的基本能力和限制是什么？

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

可计算性理论：究竟哪些问题，可通过计算解决？

计算作为一种能力，是否有边界？是不是任何问题都可以通过计算来解决？为什么？

为了能够严谨的研究这种机械而又有效的计算过程，我们需要严格定义的概念去描述它，需要严谨的计算模型去分析它。这些模型就是自动机理论，而这个概念就是算法。

欧几里得发明的辗转相除法是古老的算法之一。人类最新的知识表明，计算不是万能的，确实存在一些问题无法通过计算解决，或者说，这些问题是不存在算法的。

计算复杂性理论：解决可计算的问题，究竟需要多少资源？

计算一个问题时，需要消耗的计算时间和占用的存储空间会达到什么样的程度？

在分析各种有效计算模型的过程中，人们发现了一个按照难度给问题分类的完美体系，如同元素周期表对化学元素的性质分类一样。有了这个体系，我们就可以将未知的问题按照难易程度分类，再选择使用什么样的对策去解决。

形式语言与自动机理论：为了研究计算，要使用哪些计算模型？

自动机理论：研究抽象机器及其所能解决问题的理论。

• 图灵机 - 具有现在各种实际的计算机的所有能力，是计算机的理论模型。
• 有限状态机 - 在数字电路，通讯协议的设计等实际问题中，有重要的应用。
• 文法，下推自动机 - 在计算机程序设计语言的设计和编译器的实现上，发挥了重要的作用。

形式语言：经数学定义的语言，即以数学方法来描述问题，这种描述就是形式语言。

自然语言 形式语言

本课程的主要内容

正则语言

• 有穷自动机
• 正则表达式
• 正则语言的性质

上下文无关语言

• 上下文无关文法
• 下推自动机
• 上下文无关语言的性质

计算导论

• 图灵机及其扩展
• 不可判定性

参考资料

• Introduction to Automata Theory, Languages, and Computation. John E. Hopcroft 《自动机理论、语言和计算导论 (英文版)》机械工业出版社
• Introduction to the Theory of Computation. Michael Sipser 《计算理论导引》机械工业出版社

免责声明

本篇学习笔记及后续学习笔记是本人在中国大学Mooc的课程《形式语言与自动机理论》学习过程中形成的，若有侵权，请联系我删除。