1.1.1. 引言¶

这本电子教科书旨在为形式语言的高级课程使用。

1.1.2. 先决条件¶

这是一门计算机科学“理论”课程。在实践中，这意味着一门具有基本计算机科学应用的数学课程。本课程假设您已经在许多计算机科学主题方面具有足够的背景。

您应该修过离散数学课程，涵盖至少以下内容：

• 基本证明技巧，如反证法和归纳法。

• 求解求和与递推关系的基本技巧。

• 集合论与关系。

您应该修过一门数据结构课程，涵盖至少以下内容：

• 基础算法分析，包括大 O、大 Ω 和 \(\Theta\) 记号。

• 基础数据结构与算法，包括列表、搜索结构（如二叉搜索树）、排序算法、堆、哈希以及基础图算法。

1.1.3. 我们将做什么¶

现代英特尔处理器拥有数十亿个晶体管，其能力确实难以推理。当你可以用正则表达式解析器处理输入，或者用 YACC 之类的工具生成一个简单的编译器时，你并不愿意重新发明轮子。因此，为帮助解决这些问题，计算机科学家们已经开发出许多简单的计算模型，每一种都能在软件中相对容易地实现。

本课程涉及这些各种计算模型、每个模型的复杂性以及它们的限制。例如，如果你知道正则表达式能做什么或不能做什么，那么你就知道是否值得尝试使用正则表达式工具来解决某个问题。同样，如果你知道像 YACC 或 Bison 这样的给定编译器生成器所支持的语法类型的限制，那么你就知道是否能使用该工具完成工作，或者是否需要付出“自己动手编写”编译器的巨大努力。这类问题在从业程序员的职业生涯中经常遇到，因此你需要知道某个工具是否能解决你的问题或不能。

在本节课结束时，您将能够回答以下类型的问题。

• 你能编写一个程序来判断一个字符串是否为整数吗？

  • 示例：9998.89 8abab 789342

  这应该很容易。想一想，你会如何用程序来解决它。

• 如果机器除了程序本身外没有额外内存，你能做到吗？也就是说，你不能存储任何值或再次查看它们。

  答案：是。你可以逐个查看符号，不回看之前的符号，也不使用内存来跟踪任何内容。

• 你能编写一个程序来判断一个字符串的字符数是否为奇数吗？

  当然，这很简单。

• 你能在不使用任何工作记忆的情况下做到吗？

  答案：是。这里我们进入了“偶状态”和“奇状态”的概念。但它们是程序的一部分，而不是工作记忆的一部分。

• 你能编写一个程序来判断一个字符串是否为合法的算术表达式吗？

  • 示例：

    • ((34 + 7 ∗ (18/6)))

    • (((((((a + b) + c) ∗ d(e + f)))))

  你会如何解决这个问题？你需要跟踪什么？

  一个问题是平衡括号。你能仅仅确定括号的数量是否正确，并且它们是否按正确的顺序排列吗？ (()(())) 是好的，但 ())( 不是好的。为此，一个栈将起作用。

  但是，你能否用更简单的方法解决这个问题，而不用栈？实际上，你只需要一个整数变量：遇到左括号加一，遇到右括号减一。要求是计数从 0 开始，永远不会变成负数，最后回到 0。

• 但是，如果你的机器除了程序本身外没有额外的内存，你能做到吗？也就是说，你不能存储任何值或再次查看它们。

  答案是 NO，你必须拥有内存（至少需要一个整数变量）来跟踪左括号与右括号。没有额外内存就无法解决这个问题。我们不能使用上面提到的“状态”技巧，因为可能的“状态”数量是无限的（整数变量的每个取值对应一个“状态”）。

• 你能在不使用内存的情况下解决此问题吗？如果你被限制只能查看长度不超过 12 的表达式呢？

  是的，你可以这样做。你可以编写一个程序来检查每一个可能的字符串。注意字母表是有限的，假设有 N 个字符。有多少个可能的字符串需要检查？ \(N^12\) ，其中一些是有效的，一些则不是。你的程序将是暴力枚举，极其庞大，其形式为“如果 x 是这个字符串，则有效，否则如果 x 是这个字符串，则无效，等等。”但是，这是 可能 做到的。

  另一种方法是使用状态来跟踪当前的不平衡程度。在这种情况下，这之所以有效，是因为我们不可能拥有超过 12 种这样的状态。因此，我们不需要工作内存。

• 你能编写一个程序来确定有效数学表达式的 值 吗？

  • 示例：

    • ((34 + 7 ∗ (18/6)))

  这个问题不同。我们不是在问它是否有效，而是在评估并解决它。

• 但是，需要多少内存或计算能力？识别一个字符串是否为有效的数学表达式的能力，与计算该表达式结果所需的计算能力是同一水平吗？

  答案：否。

• 你能编写一个程序来判断一个文件是否为有效的 Java 程序吗？

  这就是编译器所做的！它们首先确定程序是否有效，然后就可以执行程序。

• 你能编写一个程序，以确定作为输入给出的 Java 程序是否最终会停止吗？

  输入是一个 java 程序，输出是该程序是否会停止。这样的程序可能如何工作？

  程序中哪些构造使得难以判断程序是否会终止？循环可能难以判断，因为它们可能不明显地会终止。直接递归和间接递归（通过函数调用另一个函数，该函数又调用第一个函数）也是如此。仅关注循环，如何确定循环条件是否会被满足从而使循环终止？这是一个非常困难（实际上是不可能的）问题。这是本学期我们要探讨的另一个主题：哪些函数是 可能 计算的？

• 我们可以用正则表达式、BNF 文法和上下文无关文法表示哪些类型的语言？

• 下推自动机、有限状态自动机、非确定性有限自动机与图灵机的相对“力量”是什么？

1.1.4. 处理¶

本课程的主要工作将来自每周的作业集。