这门课，除了前面两章的基础知识，后面的内容主要是关于0-3型文法以及拥有对应 表达能力 的自动机。对每一个层级的表达能力，都有一些内部的相互转换，从 对人类友好 到 对计算机友好 过渡。

“语言”是一个集合，是给定字母表$T$的闭包$T^*$的子集。

语言有两种描述方式 - 文法与自动机。

下图是表示各类文法/自动机表达能力的韦恩图，从内到外对应课本第三到五章。

下面为依照上图划分整理的笔记。

正则语言部分

上下文无关语言部分

据老师说因为过于麻烦，上下文有关语言与线性有界自动机不讲了，线性有界自动机本质上是一个把计算限制在仅仅包含输入的那一段带上的图灵机。且在实际中上处理下文有关语言很少用文法与自动机的范畴来讨论。

无限制语言部分

语言	用途
正则语言	词法分析
上下文无关语言	语法分析
无限制语言	计算机的理论模型，探讨可计算性

可计算问题 -> 语言是否能够处理的问题

---

语言的性质

• pumping性质
• 闭包性质(e.g.求一个语言的非-自动机)
• 判定性质(e.g.判定是否空、包含某个字符串以及是否相等)

---

Linux 下有两个相关工具：词法分析器Lex与语法解析器Yacc，它们的GNU版分别是flex和bison。

有一些笔记在几次迁移过程中丢失了，目前有20%左右的坏链，可惜。