2.1. 语言、文法与机器¶

一个 语言 简单来说就是一串串的集合（具体而言，是从某个 字母表 推导出的那些串的子集）。 对串能做的一件基本事情，就是判断它是否属于某个给定的语言。 这学期我们研究各种类型的机器，看看它们能可靠地 识别 哪些语言（也就是说，可靠地判断某个串是否在那种语言中）。 我们还将研究表达或定义语言的其他方式，其中包括 文法 ，以及其他“用于定义语言的语言”，比如 正则表达式 。

2.2. 语言层次¶

这幅图展示了我们这学期大部分时间要做的事情。 到课程结束时，你将理解图中各部分彼此之间的关系、它们如何应用于编译器，以及一些相关问题有多难解决。

你对编程语言很熟悉。 现在，我们要更细致地看看编程语言是如何（利用文法）定义出来的，以及 自动机 （它是比你的笔记本电脑更简单的计算机版本）。 “自动机”（Automata）只不过是“机器”的另一种说法。

我们从图中最中心的位置开始，它代表最小的语言集合。 我们将先考察较简单的语言与文法，然后逐步上升到编程语言是如何形成的。 我们从 有穷自动机 （也称 有穷状态机 ）开始。 我们将看到，任何有穷自动机都代表一种简单的语言，而且有一种文法（ 正则文法 ）能表示同一种语言。 此外，我们还会考察 正则表达式 。 这些最终都归结为可以由不加额外内存的程序表示的语言。

然后，我们会以非常简单的方式加入内存—一个栈—，所用的机器（ 下推自动机 即 PDA ）能够表示更大的语言集合，以及它们对应的文法。

接着，我们再加入更多内存与能力，把我们带到另一种机器（图灵机）、它能表示的语言类型，以及它对应的文法类型。

最后，我们将简要讨论那些你无法编写程序可靠识别的语言（这一话题称为 可计算性 理论），并略谈（相对）便宜就能解决的问题与（相对）昂贵才能解决的问题之间的差别（这一话题称为 计算复杂性理论 ）。

2.3. 机器的能力¶

这学期我们会详细介绍所有这些内容。 但下表可以让你快速一览。

2.4. 应用：编译器¶

问题：给定某种语言（比如 Java 或 C++）的一个程序，它是合法的吗？ 也就是说，它是一个语法正确的程序吗？ 如果该语言的文法定义得当，那么某些自动机就能做到这一点。

如果程序在语法上正确，编译器就会继续生成代码，以便高效地执行该程序。 我们不会讨论编译器的这一部分—想了解这部分，你需要修一门编译器课程。

你可能会认为，理解如何编写文法来识别一种语言（或者把语言设计成确实可以写出文法）是一门多余的技能。 但事实上，很多程序员在工作中会编写“小型语言”。 例如，你可能在一家制造机器人的公司工作，需要一个用来控制机器人的小型语言。 或者你可能要编写一个网页，其中的输入框必须把输入限制为某种特定结构。

2.5. 一些令人费解的想法¶

与形式语言相关的“元”（meta）概念非常多。 这里列出几件值得思考的事。

语言的描述本身只是一些串。 这意味着，例如，（作为串的）正则表达式的集合本身就是一种语言。 这引出了下面这类问题：

• （在我们的层次结构中）正则表达式的集合属于哪种类型的语言？

• （在我们的层次结构中）Java 属于哪种类型的语言？

• 所有上下文无关文法的集合属于哪种类型的语言？

下面还有一些别的有趣的“元”问题与论断。

对任意给定的语言 \(L\) ，定义语言 co-\(L\) 为所有 不在 \(L\) 中的串构成的集合。 co-\(L\) 是否总是与 \(L\) 属于（我们的层次结构中）同一类型的语言呢？

图灵机可以做任何事情（至少，是任何计算机都能做的任何事情）。

还有，你怎么可能无法判断一个循环是否会停机呢？！ .. odsascript:: AV/PIFLA/Intro/HierarchyCON.js .. odsascript:: AV/PIFLA/Intro/CompileCON.js .. odsascript:: AV/PIFLA/Intro/CompileStagesCON.js