我们为什么要学习有限自动机

这一主题不仅仅针对想进入复杂性理论领域的同学，不过以此为目标的同学也可以把这门课当作一个良好的开始。这门课真正重点强调的是，实践中人们用到的那些理论。有限自动机、正则表 达式、上下文无关语法是经得起实践检验的一些概念，对于编译器而言，它们是必不可少的工具。更重要的是，很多系统所需要的输入远远没有完整编程语言那么复杂，但又比按一个键要复杂很 多，这些概念还被用于很多这样的系统中。

不可判定问题和难解问题这些概念则服务于不同目的。不可判定问题是计算机解不可能存在的问题，而难解问题则是有强烈证据证明计算机解存在、但解起来效率很差的有用实践问题。理 解这一理论，特别是获得证明问题属于哪类的能力，将让你能够采取下一步方法化简问题或是写代码逼近问题的解。课程期间，我将证明一些内容。这些证明的目的并不是为了折磨你，或 是把你搞糊涂，也不仅仅是为了让你确信我讲的是正确的，而是为了让你理解这些证明，特别是归纳证明，这能让你更好地理解自己的工作。我并不主张证明程序是正确的，但是，但凡你 在尝试比较复杂的问题时，脑海中进行一些归纳证明总是必需的，这能保证你的成果在所有情况下正常工作。

课程涉及领域

(1)有限自动机和正则表达式

(2)上下文无关语法

(3)图灵机和可判定性

(4)难解性理论或NP-完备性问题