前言

这是一个关于计算机与计算的抽象模型的教程。在计算机领域如此注重实践的情况下，为什么我们还要学习理论呢？

理论为硬件和软件都提供了基本的概念和原理，能够帮助我们更一般地理解这个领域的本质。

在斯坦福大学对于毕业五年的学生的调查中，让已经工作的毕业生们选择它们在大学中学过的课程中，有哪些在工作中用到的最多。

毋庸置疑的是，基础的编程导入课程是最多的，但是，令人感到惊奇的结果是，在所有的选修课当中，形式语言与自动机排在了非常靠前的位置。

这是为什么呢？可能有如下一些原因：

• 正则表达式在很多系统中都会用到；

• 有限自动机是协议与电路建模的常用方法；

• 上下文无关文法被用来描述几乎所有编程语言的语法；

• 当解决实际问题的时候，我们总是会触碰到软件的极限，而自动机理论是我们判断某个解决方案是否超出了计算机处理的能力范围。

  • 无法确定(undecidable)的事情：没有程序能够解决；

  • 顽固(intractable)的事情：有程序能解决，但是没有快速的程序能够解决。