关于老师

由软件学院的卜磊老师授课，上课很有精神，时常会使用一些生动有趣的例子解释比较抽象的理论概念，思维跳跃但逻辑严谨。

前置知识

集合论

课程内容

参见民间课程网站：形式语言与自动机 - cuijiacai

课程包含了有关形式语言和自动机的基础内容，和计算方法类似，是一门偏向于概念介绍的“讲座课”；主要包含了：

  • 有穷自动机
  • 上下文无关语言
  • 下推自动机
  • 图灵机
  • 判定性与复杂度
  • （略讲）迁移系统、Petri 网、时间自动机

算是 NJU CS 里偏简单的一门理论课。

作业、考试与得分

作业偏向于理论，有一定难度，可能需要一定的灵感乍现才能做出来（有一些题也根本不是一般人能想出来的，可以适当搜索）。共有 6 次作业，平均每次耗时 4 小时。

考试题量非常之大，但难度平平，所以题目都有在现场做出来的可能。最终得分差距主要体现在期末考试。

实验是使用 C++14 模拟一个 PDA 和一个 TM，需要支持读取一个给定格式的 PDA 或 TM 文件，并按文件所描述的自动机在给定的输入上运行。主要难度在于读取文件并正确解析，真正模拟的部分很快就能写完。若设计得当，总体码量约为 1k 行，耗时 10 小时左右。

其他

笔者认为，这门课里最有用的部分还是概念：诚然，很多地方都会用到自动机的概念（TCP 自动机、文法分析等），但并不需要我们使用很复杂的建模技巧和规约证明。因此笔者认为，在这门课上搞懂每一个自动机的概念、每一种自动机的能力边界即可，不需要过于深究那些规约技巧。