形式语言与自动机理论(哈工大)学习笔记Day01
作为计算机科学的核心,计算理论的重心经历了从数学转移到计算机科学的过程。
计算机科学关心的核心问题:计算机的基本能力和限制是什么?
这个问题包含了两个内容,分别对应计算理论的两个重要研究方向。一个是可计算性理论,一个是计算复杂性理论,形式语言与自动机理论正是这两个重要研究方向的理论基础。
可计算性理论:究竟哪些问题,可通过计算解决?
计算作为一种能力,是否有边界?是不是任何问题都可以通过计算来解决?为什么?
为了能够严谨的研究这种机械而又有效的计算过程,我们需要严格定义的概念去描述它,需要严谨的计算模型去分析它。这些模型就是自动机理论,而这个概念就是算法。
欧几里得发明的辗转相除法是古老的算法之一。人类最新的知识表明,计算不是万能的,确实存在一些问题无法通过计算解决,或者说,这些问题是不存在算法的。
计算复杂性理论:解决可计算的问题,究竟需要多少资源?
计算一个问题时,需要消耗的计算时间和占用的存储空间会达到什么样的程度?
在分析各种有效计算模型的过程中,人们发现了一个按照难度给问题分类的完美体系,如同元素周期表对化学元素的性质分类一样。有了这个体系,我们就可以将未知的问题按照难易程度分类,再选择使用什么样的对策去解决。
形式语言与自动机理论:为了研究计算,要使用哪些计算模型?
自动机理论:研究抽象机器及其所能解决问题的理论。
- 图灵机 - 具有现在各种实际的计算机的所有能力,是计算机的理论模型。
- 有限状态机 - 在数字电路,通讯协议的设计等实际问题中,有重要的应用。
- 文法,下推自动机 - 在计算机程序设计语言的设计和编译器的实现上,发挥了重要的作用。
形式语言:经数学定义的语言,即以数学方法来描述问题,这种描述就是形式语言。
自然语言 形式语言
本课程的主要内容
正则语言
- 有穷自动机
- 正则表达式
- 正则语言的性质
上下文无关语言
- 上下文无关文法
- 下推自动机
- 上下文无关语言的性质
计算导论
- 图灵机及其扩展
- 不可判定性
参考资料
- Introduction to Automata Theory, Languages, and Computation. John E. Hopcroft 《自动机理论、语言和计算导论 (英文版)》机械工业出版社
- Introduction to the Theory of Computation. Michael Sipser 《计算理论导引》机械工业出版社
免责声明
本篇学习笔记及后续学习笔记是本人在中国大学Mooc的课程《形式语言与自动机理论》学习过程中形成的,若有侵权,请联系我删除。