1. 关于本课程与本书¶
1.1. 引言¶
这本电子教科书面向形式语言与自动机（FLA，Formal Languages and Automata）课程，属于高年级课程层次。 它涵盖了一套公认的主题，与传统 FLA 课程大体一致。 但是，它的呈现方式有些反传统，具体如下文所述。 此外，由于这可能是你课程体系中唯一的一门经典 CS 理论课程， 我们会在结尾顺带介绍 CS 理论中的另外两个传统主题： 复杂性理论，也就是 NP 完全性 （它涉及理解什么计算起来昂贵、什么不算昂贵）； 以及 可计算性 （研究计算机程序所能解决的问题在哪些方面存在极限）。
1.2. 先修要求¶
这是一门 CS“理论”课程。 实际上，这意味着用数学来帮助理解深层次的 CS 概念，以及它们如何与实际 CS 应用相关联。 本课程假定你已经在若干数学和 CS 主题上具备足够的背景知识。
你应该上过一门离散数学课程，至少涵盖以下内容：
你应该上过一门数据结构课程，至少涵盖以下内容：
1.3. 本书的运作方式¶
这本书在很多方面都和你的典型教科书不一样。 你可能以前出于另一门课程用过 OpenDSA 电子教科书。 如果是这样，其中有些内容你会觉得熟悉。 但即使你以前用过 OpenDSA，本书中的一些基本功能对你来说可能也仍然是新的。
首先，很多内容是用一种叫作“程序化教学”（Programmed Instruction）的技术呈现的。 程序化教学的想法是，通过不断就你正在阅读的内容提问，让你始终保持对材料的专注。 所以你会看到一种幻灯片式的演示，我们称之为“程序化教学框架集”（Programmed Instruction frameset）。 框架集中的每一张幻灯片都会呈现一小部分信息，有时还配上图形，帮助把问题讲清楚。 但通常，要在框架集中继续前进，你就必须先回答一个问题。 我们希望你会发现这些问题大多不难（至少，设计者打算让其中大多数都很简单）。 这些问题的目的是让你专注于内容的意义，通过不断检验你的理解，迫使你边学边思考。 所以，除了让你保持专注之外，能够一路答出这些问题，也意味着你可以确信自己确实读懂了所读的内容。
其次，这本书包含大量自动评分的练习。 与框架集中那些简单的问题相比，这些练习有助于在更综合的层面上，确认你确实理解了所读的内容。
第三，由于本书讲的全是简单类型的“机器”，我们提供了许多工具，用来创建这些机器并（以可视方式）模拟它们的行为。 我们把这些模拟集成到部分练习中。 这很像编写小型程序，只不过你不是用像 Java 这样的常规编程语言来编写，而是用机器编辑器来编写。 你的机器通常用图来表示。 有时，你会通过编写文法（grammar）来定义另一种类型的“机器”。 但无论哪种方式都跟编程很像，而且在内部，我们会对你的机器运行单元测试，检查它的答案是否与我们的相符，从而验证你的机器是否正确。
1.4. 我们将要做的事¶
要推理一台拥有数十亿晶体管、现代化的 Intel 或 AMD 处理器的能力，真的非常困难。 而且，如果能用一个正则（regex）解析器处理你的输入，或者借助 YACC 之类的工具生成一个简单的编译器，你肯定不想重新发明轮子。 具体来说，我们将考察求解一些与串有关的基本问题所需的计算能力。 通常大家想解决的问题，是给定一个串是否属于某个给定的语言，或者给定的串表示能否生成某个特定的串。 为了帮助理解这些问题及其求解工具，计算机科学家开发了许多简单的计算模型。 它们每一种都能比较容易地在软件中实现。 但更重要的是，它们足够简单，让我们能够真正理解它们能做什么（以及不能做什么）。
本课程讨论这些不同的计算模型、每种模型的复杂程度及其局限。 例如，如果你了解正则表达式能做什么、不能做什么，那么也许你可以通过简单调用正则表达式库来解决一个难题。 另一方面，也许你可以避免浪费时间，用正则表达式工具去解决并不适合它们的问题 （并不是所有的串集合都能用正则表达式表示）。 同样，如果你了解某个编译器生成器（如 YACC 或 Bison）所支持的文法类型的局限，那么你就会知道能否用该工具为给定语言快速编写解释器或编译器，还是需要付出多得多的努力去“自研”编译器。 这类问题在从业程序员的工作中经常出现，因此你希望知道什么时候某个工具能解决你的问题、什么时候不能。
到本课程结束时，你将能够回答下面这类问题。
你能否编写一个程序来判断一个串是否为整数？
示例：9998.89 8abab 789342
这应该很容易。 想想你会如何用自己最喜欢的编程语言来解决它。
如果你的机器除了程序本身之外没有任何额外内存，你还能做到吗？ 也就是说，你不能存储任何值（没有变量！），也不能再回头查看输入。
答案：可以。你可以从左到右一次只看一个符号，不回看前面的符号，也不用任何变量来记录任何东西，从而解决这个问题。
你能否编写一个程序来判断一个串的字符数是否为奇数？
当然，这很容易。
你能否不用任何工作内存就做到这一点？
答案：可以。这里我们就会接触到“偶状态”（even state）和“奇状态”（odd state）的概念。 但这些状态可以直接内置到程序中，因此你不需要用任何变量来记住状态。 当输入用完时，你在程序中的当前位置就会告诉你答案。
你能否编写一个程序来判断一个串是否为合法的算术表达式？
示例：
((34 + 7 ∗ (18/6)))
(((((((a + b) + c) ∗ d(e + f)))))
你会如何解决这个问题？ 你需要跟踪哪些东西？
其中一个子问题是括号是否平衡。 你能仅仅判断括号数目是否正确、而且顺序是否合法吗？
(()(()))是合法的，而())(不合法。 要做到这一点，用栈就行。但你能不借助栈、用更简单的方式解决它吗？ 实际上用一个整数变量就能做到：遇到左括号加一，遇到右括号减一。 要求是计数从 0 开始、绝不为负，并且以 0 结束。
但如果你的机器除了程序本身之外没有任何额外内存，你还能做到吗？ 也就是说，你不能存储任何值，也不能再看它们。
答案是不能，你必须要有内存（至少一个整数变量）来跟踪左括号与右括号。 没有额外内存就不可能解决这个问题。 我们不能使用上面提到的“状态”技巧，因为可能存在无限多个“状态”（整数变量的每个值都对应一个“状态”）。
如果只允许你处理长度不超过 12 的表达式，你能否（不用内存）解决这个问题？
可以。 字母表必须是有限的，比如 \(N\) 个字符。 需要检查的串共有多少种可能？ \(N^{12}\) 种，其中有些是合法的，有些不是。 你的程序可以采用暴力法，因此体积会大得惊人。 它可以写成“如果 x 是这个串，则合法；否则如果 x 是那个串，则不合法；等等”的形式。 但这种做法 是可行的 。
另一种做法是用状态来记录当前的不平衡程度。 在这种情况下，这种做法可行，是因为这样的状态不可能超过 12 个。 所以，这也是一个不需要工作内存的解决方案。
顺便说一句，“不用工作内存来解决问题”这种想法，在编写程序的背景下对你来说可能相当陌生。 但我们将看到其他类型的计算方式（特别是检查给定串是否属于某个串的集合）， 而这些方法使用工作内存的方式，在其各自的语境中会显得相当自然。
你能否编写一个程序来确定一个合法数学表达式的 值 ？
示例：
((34 + 7 ∗ (18/6)))
这个问题有所不同。 这里不是问表达式形式是否合法，而是要求验证其格式并求出结果 （当然，只有当表达式恰好合法时，这一步才会成功）。
但是，这需要什么样的内存或计算能力呢？ 识别一个串是否为合法数学表达式的能力，与计算该表达式结果所需的能力，是否处于同一水平？
答案：不是。目前你可以自行思考这个断言。
你能否编写一个程序来判断一个文件是否为合法的 Java 程序？
这正是 Java 编译器所做的！ 它首先判断程序是否为合法的 Java。 如果是，就把程序转换成计算机执行起来更高效的形式。 最后（至少在你要求时）执行该程序。
你能否编写一个程序，判断一个作为输入给出的 Java 程序是否会停机？
输入是一个 Java 程序，输出是该程序是否会停机。 这样的程序会如何工作呢？
程序中有哪些构造会让判断程序是否停机变得困难？ 循环可能很难判断，因为循环是否终止可能并不显然。 递归是否停止也可能很难判断。 而且我们可能遇到直接递归（一个函数调用自身），或者间接递归（一个函数调用另一个函数，而后者又调用前者）。 仅仅关注循环：你如何判断某个循环条件是否会被满足，从而使循环停下来？ 这是一个非常难解决的问题。 （这样说还不够准确。 实际上，在一般情况下这是一个 不可能 解决的问题。 我们 并不能总是 判断某个循环是否会停机。） 这是我们这学期将要讨论的另一个主题：哪些函数是 可以 计算的？
我们能用 正则表达式 、 正则文法 和 上下文无关文法 表示哪些类型的语言？ 这些表示方式是否彼此“一样”（即处理相同的语言），还是各不相同？
下推自动机 、 有穷状态自动机 、 非确定的 有穷自动机以及 图灵机 的相对“能力”是怎样的？ 对其中任意两者而言，是否存在一个问题，其中一个能解决而另一个不能解决？
