形式语言与自动机

课程信息

本来是计科那边的课，2024 年移植到软院，作为非方向课的选修课。在仙林和鼓楼均有开班，可以相互替代。

主要讲一些计算机与计算的抽象模型(形式模型)，包括自动机、语言文法、图灵机、判定性与复杂度等等，详见课程网站。

授课老师：卜磊，李宣东
课时：3 学分。每周一次课 3 个小时(2024)
成绩：期末考试(50%)，期末项目(20%)，平时作业(30%)
教材： John E. Hopcroft, Rajeev Motwani, Jeffery D.Ullman. Introduction to Automata Theory, Languages, and Computation.
课程网站：Formal Languages and Automata(2024)，如果访问不了了，可以到Lei Bu's Homepage里面找一找

上课不点名。

基本是卜磊老师在上课。PPT 全英文，上课中后期的很多知识比较硬核，如果要顺利听懂需要预习。

老师上课讲得不错，值得去听。可以省下一些自己啃笔记和 PPT 的时间。

平时作业有 6 次，每一次作业 4 道大题。题面纯英文，以基础题为主，也会有比较难的题。难题大多都特别有意思，值得研究与讨论。

作业结束后会放助教录的作业讲解视频。

平时作业给分会参考正确性。

24 年期末项目是一个 TM 和 PDA 的模拟器，外加三个 TM 和 PDA 程序设计。要根据实验手册搓一个命令行工具，语言为 C++，没有代码框架。可能需要一天以上才能写完。

期末项目 DDL 在期末考完之后一周。

期末考试难度和平时作业的基础题差不多。考前多看看作业题和往年题。把关键概念搞懂了的话上 60 不是特别难。平时正常写作业，期末考前复习一天左右就能比较容易地考过。

期末考试题面为中文。

毕竟是选修课，60 分即可。但是平时作业的基础题一定要自己写，尽量要把概念弄明白。比较难的题可以不用深究。期末记得复习。

课程内容很有意思，能够激发你的求知欲和探索欲，并且前期知识（文法和自动机）与编译原理无缝衔接。总的来说是能学的知识的好课，作为选修课值得一选。

第一年在软院开课。本文主要内容都是根据 2024 年的情况写的。