形式语言

计算机科学中复杂性的概念核心是形式语言的概念。形式语言是一组词语，这些词语是从一个有限的符号集（通常称为 $\Sigma$ ）中提取的有限长度字符串。我们研究定义特定语言的机器的计算复杂性，这些机器通过**接受**或**拒绝**其字母表中的每个可能的词语来定义该语言。

虽然语言中的每个词语都必须是有限的，但语言可能包含任意长度的词语，因此可能包含无限个词语。例如，从字母表 $\Sigma =\{a,b\}$ 中提取的所有字符串的集合，其中包含一定数量的 a，后跟相同数量的 b。因此，该语言包含任何形式为 $a^{n}b^{n}$ 的字符串，其中 $a^{n}$ 是重复 n 次的符号 a。由于 n 可以是任何正整数，因此该语言中必须有无限个词语。

许多形式语言都有与之关联的生成语法，生成语法是一组替换规则，这些规则包含三种类型的符号：ε，表示空字符串（长度为 0 的字符串）；非终结符，这些符号不在语言的字母表中；终结符，这些符号在语言的字母表中。按照惯例，非终结符通常是大写字母，而终结符（以及相关的形式语言的字母表）通常是小写字母。语法还包括一个称为起始符号的非终结符，这是替换规则在任何替换发生之前假设存在的符号。通过对何时应用哪个替换规则进行选择，起始符号可以转换为与该语法关联的语言中的任何词语，而不能转换为其他词语，这就是为什么该语法被称为生成语言的原因。这些替换规则如何形成取决于所涉及的语言类别，并且对语法的每组限制都会创建一个生成语法的类别。并非所有形式语言类别都与生成语法类别相关联。

通常与语言类别相关的另一个对象是识别机器。这些机器如何操作以及它们的限制是什么取决于它们所对应的语言类别，但如果机器在给定该语言中的任何词语作为输入时，总是“接受”该词语，并且永远不会“接受”不在该语言中的词语，则称该机器识别该语言。并非所有形式语言类别都与识别机器类型相关联，但计算机科学家研究的大多数语言都与识别机器类型相关联。

有多个不同语言类别，每个类别都基于其包含的语言的复杂性。最著名的语言类别是乔姆斯基层次的四个类别，这些类别由诺姆·乔姆斯基在其 1959 年的论文“关于语法的一些形式属性”中定义 1。有关其他语言类别的信息，请参阅章节其他语言类别。

总结

一个字母表是有限的符号集合。
一个词语是从字母表中提取的有限长度的符号串。
一个形式语言是一组词语。
一个生成语法是一组替换规则，这些规则允许您从起始符号创建语言中的任何词语（以及其他词语）。
一个识别机器是“接受”语言中的任何词语（以及其他词语）的机器。
一个语言类别是一组复杂性相似的语言，因此它们具有相似的生成语法类型和相似的识别机器类型。