形式语言与自动机理论学习笔记1

计算理论

核心问题：

计算机的基本能力和限制是什么？

1. 究竟哪些问题，可通过计算解决？（或者说计算作为一种能力是否有边界？）——可计算理论
2. 解决可计算的问题，究竟需要多少资源？（也就是计算所用时间和所占的空间会达到怎样的程度？）——可计算性理论
3. 为了研究计算，要用到哪些计算模型？（这些模型都是高度抽象出来的）——形式语言与自动机理论

什么是自动机理论？

自动机理论：研究抽象机器及其所能解决问题的理论.（以这些抽象的计算装置为研究对象，分析这些装置所能解决问题的理论）

• 图灵机（最重要，具有现在实际的计算机所有的能力，是计算机的理论模型，它区分了哪些问题是可以计算的，哪些问题是不能计算的。在多项式时间内，图灵机以确定的方式和非确定的方式所解决的问题的问题类是否相同，即是否等于仍然是计算机科学领域悬而未决的问题。）
• 有限状态机（有穷计算机，相对而言稍简单，在数字电路、通信协议的设计等实际的问题中，有重要的应用。）
• 文法，下推自动机（在计算机程序语言的设计和编译器的实现上发挥了较大的作用。）

什么是形式语言?

形式语言: 经数学定义的语言.

课程内容

• 正则语言

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

• 上下文无关语言

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

• 计算导论

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

参考书

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