（限选）形式语言与自动机

授课教师

• zyf

  挺好的老师，交流时感觉很亲切。

• tbz

• cb

• lxb

• ly

关于作业

作业有些班级是英文的，有些班级是中文的。

中文的作业都是重要的基础题，尽量完全弄懂。

英文的作业有一些十分有趣的构造和证明，网上可以搜到一些类似题目的答案。这类题目 20 级考试中并没有出现。

关于考试

考试都是基础题型，参考 exam 中的试卷。

但考试本身难度较大，因为形式语言与自动机本身有很多巧妙的构造和分析。只掌握 PPT 上的概念和例子不太能得到很高的分数，可能还需要自己找一些常见的语言文法和自动机的转换习题。

据说 20 级挂得不多，掌握基础知识就能稳过。但 21 级变成考试课后不知道会不会有变化。

（20 级得分排名参考：92 分 rk1，82 分 rk60/500）

学习建议

“课程是很难的课程，但是过还是比较容易的。”

本课程以前是《编译原理》的一部分，20 级独立出来作为一门必修课程。

相比《算法设计与分析》、《数理逻辑》和离散数学一系列课程，《形式语言与自动机》似乎是计科培养计划里难度最大的理论计算机科学（Theoretical Computer Science）课程。希望以后有更多的 TCS 课程能以选修的形式出现在培养计划里。

如果有同学对 TCS 感兴趣（如果有 TmT），可以 B 站搜一搜北京大学的《理论计算机科学基础》课程，这门课程前半部分有更细致的自动机理论，后半部分利用这些知识介绍了可计算性理论和计算复杂性理论，欢迎和笔者交流相关细节~

资料下载

如果你是校内学生，可点击如下「内网网盘」按钮查看本门课程的电子书、课件和实验软件等。

参与

《HITSZ 自动化课程攻略共享计划》是所有同学都可以参与编写的，如果你有好的笔记或者资料，欢迎前往我们的 GitHub 进行参与，也可以发邮件至 📮hi@hoa.moe 联系我们，我们会在收到的第一时间进行答复。