计算理论笔记 01A：有限自动机和正则语言

从这里开始，我们要进入计算理论的世界。计算理论（theory of computation）研究的核心问题就是计算（computation）。我们需要思考的问题是：什么是计算；什么可以计算或不可以计算；如果可以计算，这个问题有多难计算；如果不可以计算，这个问题不可以计算的程度有多少。这个系列（前半部分的）主要框架来自于浙江大学计算理论课程毛宇尘老师的授课，其中插入了大量笔者个人的想法和来源于其他参考资料的结论和思路，应当完全覆盖并超越这门课程本身。这门课程事实上只部分地回答了前两个问题，对于第三个问题一带而过，而对于第四个问题几乎完全没有讨论，但是在这个系列里，我会尽可能完整地展现整个理论从新生到现代的全貌。笔者才疏学浅，如有疏漏，望指正。