Sets, Relations and Language⚓︎

Sets⚓︎

• 集合
  • 没有重复元素
  • 顺序不重要
• 元素 / 成员
• 单元集 (singleton)：只有 1 个元素的集合
• 空集 \(\emptyset\)
• 子集
• 真子集 (proper subset)
• 判断两个集合是否相等

• 集合运算

  • 并 (union)：\(\bigcup S = \{x : x \in P \text{ for some set } P \in S\}\)
  • 交 (intersection)：\(\bigcap S = \{x : x \in P \text{ for each set } P \in S\}\)
  • 差 (difference)

• 集合的性质：

  • 幂等性 (idempotency)：\(A \cup A = A, A \cap A = A\)
  • 交换律 (commutativity)：\(A \cup B = B \cup A, A \cap B = B \cap A\)
  • 结合律 (associativity)：\((A \cup B) \cup C = A \cup (B \cup C), (A \cap B) \cap C = A \cap (B \cap C)\)
  • 分配律(distributivity)：\((A \cup B) \cap C = (A \cap C) \cup (B \cap C), (A \cap B) \cup C = (A \cup C) \cap (B \cup C)\)
  • 吸收律 (absorption)：\((A \cup B) \cap A = A, (A \cap B) \cup A = A\)
  • 德摩根定律(Demorgan's law)：\(A - (B \cup C) = (A - B) \cap (A - C), A - (B \cap C) = (A - B) \cup (A - C)\)
    • \(A = U\)（全集）的时候可能是我们更加熟悉的形式

• 不相交集 (disjoint)：两个集合无公共元素，即它们的交集为空集

• 幂集(power set)：包含某一集合 \(A\) 所有子集的集合，记作 \(2^A\)
• 划分(partition)：幂集的子集，记作 \(\Pi\)，并且满足：
  • 不包含空集
  • 每个元素（原集合的子集）互不相交
  • \(\bigcup \Pi = A\)

Relations and Functions⚓︎

• 有序对(ordered pair) \((a, b)\)

  • \(a, b\) 为其分量 (component)
  • 和集合 \(\{a, b\}\) 不同，首先要考虑分量的顺序，其次两个分量可以是一样的

• 集合 \(A, B\) 的笛卡尔积(Cartesian product)：记作 \(A \times B\)，所有有序对 \((a, b)\ (a \in A \text{ and } b \in B)\) 构成的集合

• 集合 \(A, B\) 的二元关系(binary relation) 即为 \(A \times B\) 的子集

• 有序元组(ordered tuple) \((a_1, \dots, a_n)\)（其中 \(n\) 为任意自然数）

  • 有序三元组 / 四元组 / 五元组 / 六元组 (ordered triples/quadruples/quintuple/sextuples)

• 序列(sequence) 即未指定 \(n\)（序列长度）的有序 \(n\) 元组

• n 重笛卡尔积(n-folds Cartesian product) \(A_1 \times \dots \times A_n\)：所有有序对 \((a_1, \dots, a_n)\ (a_i \in A_i\ (i = 1, \dots, n))\) 构成的集合
• n 元关系(n-ary relation) 即为 \(A_1 \times \dots \times A_n\) 的子集
  • 1, 2, 3 元关系分别对应 unary/binary/tenary relations

• 集合 \(A\) 到集合 \(B\) 的函数(function) 是 \(A\) 到 \(B\) 的二元关系，并满足以下性质：对于每个元素 \(a \in A\)，恰好存在一个以 \(a\) 为第一元素的有序对
• 一般用 \(f, g, h\) 表示函数
• \(f: A \mapsto B\) 表示从 \(A\) 到 \(B\) 的函数 \(f\)
• 其中 \(A\) 为函数的域(domain)
• \(f(a)\) 为 \(a\) 在 \(f\) 中的像(image)
• 若 \(A'\) 是 \(A\) 的子集，那么定义 \(f[A'] = \{f(a): a \in A'\}\)，称 \(f[A']\) 为 \(A'\) 在 \(f\) 中的像
• \(f\) 的范围(range) 即为域对应的像
• 若函数为 \(f: A_1 \times \dots A_n \mapsto B\)，并且 \(f(a_1, \dots, a_n) = b\)（\(a_i \in A_i \text{ and } b \in B\)），那么称 \(a_1, \dots, a_n\) 为 \(f\) 的参数(auguments)，\(b\) 为 \(f\) 的值(value)

• 对于 \(f: A \mapsto B\)

  • 若对于任意两个不同元素 \(a, a' \in A,\ f(a) \ne f(a')\)，称 \(f\) 是单射的 (one-to-one)
  • 若 \(B\) 的每个元素是 \(A\) 中某些元素的像，称 \(f\) 是满射的 (onto)
  • 若既是单射，又是满射，那么 \(f\) 是双射函数 (bijection)

• 二元关系 \(R \subseteq A \times B\) 的逆(inverse) 记作 \(R^{-1} \subseteq B \times A\)，即 \(\{(b, a) : (a, b) \in R\}\)

  • 但函数的逆不一定是函数，只有当 \(f\) 是双射时才能保证是函数（即反函数 \(f^{-1}\)）
  • \(f^{-1}(f(a)) = a\ (\forall a \in A)\)，\(f(f^{-1}(b)) = b\ (\forall b \in B)\)

Special Types of Binary Relations⚓︎

（二元）关系 \(R \subseteq A \times A\) 可以被表示为一张有向图(directed graph)

• \(A\) 的每个元素用一个小圈表示，称为节点(node)
• 而 \((a, b)\) 则用由 \(a\) 到 \(b\) 的箭头表示，称为边(edge)

有向图（\(R \subseteq A \times A\)）的一些性质：

• 自反(reflective)：\((a, a) \in R, a \in A\)

• 对称(symmetric)：当 \((a, b) \in R\) 时，\((b, a) \in R\)

  • 没有形如 \((a, a)\) 对的对称关系可用无向图(undirected graph) 表示
• • 反对称(antisymmetric)：当 \((a, b) \in R\) 时，\((b, a) \notin R\)
• 传递(transitive)：当 \((a, b), (b, c) \in R\) 时，\((a, c) \in R\)

同时满足自反、对称、传递的关系被称为等价关系(equivalence relation)。用无向图表示的等价关系由一组集群构成，这些集群就是等价类(equivalence classes)，如下图所示：

通常我们用 \([a]\) 表示包含元素 \(a\) 的等价类，即 \([a] = \{b: (a, b) \in R \text{ or } (b, a) \in R\}\)。

而同时满足自反、反对称和传递的关系被称为偏序(partial order)。假如 \(R \subseteq A \times A\) 是偏序，

• 对于 \(a \in A\)，若满足仅当 \(a = b\) 时 \((b, a) \in R\)，称 \(a\) 为最小值(minimal)
  • 可以这么想：最小值 \(a\) 总是要位于左侧，除非右侧也是 \(a\)
• \(\forall a, b \in A\)，\((a, b) \in A\) 且 \((b, a) \in A\)，那么偏序 \(R\) 就是全序(total order)

二元关系的路径(path) 是一个序列 \((a_1, \dots, a_n)\)（\(n \ge 1\)），满足 \((a_i, a_{i+1}) \in R\)（\(i = 1, \dots, n-1\)）。路径长度就是 \(n\)。

• 对于路径 \((a_1, \dots, a_n)\)，当 \((a_n, a_1) \in R\) 时，该路径就是一个环(cycle)。

Finite and Infinite Sets⚓︎

若存在双射 \(f: A \mapsto B\)，称集合 \(A, B\) 是等势的(equinumerous)。由于双射可逆，因此等势性体现了对称关系。

若集合与 \(\{1, 2, \dots, n\}\)（\(n\) 为自然数）等势，那么该集合是有限的(finite)。而 \(A\) 的基数(cardinality) \(|A|\) 就是 \(n\)（即有限集合的元素个数）。

当集合不是有限的，那就是无限的(infinite)。需要注意的是，不是所有的无限集合是等势的。

若集合与 \(\mathbb{N}\) 等势，那么该集合就是可数无限的(countably infinite)；并且有限和可数无限均属于可数的(countable)，反之就是不可数的(uncountable)。

Three Fundamental Proof Techniques⚓︎

下面介绍三种在各种证明中经常出现的基本原理 (fundamental principle)：

• 数学归纳法(mathematical induction)：令 \(A\) 为一个自然数集合，满足：

  • \(0 \in A\)
  • 对于每个自然数 \(n\)，若 \(\{0, 1, \dots, n\} \subseteq A\)，那么 \(n + 1 \in A\)

  那么 \(A = \mathbb{N}\)

  • 可以用反证法 (contradiction) 证明其正确性

  • 实际上归纳法通常用来证明以下形式的断言：“对于任意自然数 \(n\)，性质 \(P\) 为真。”设集合 \(A = \{n : P \text{ is true of } n\}\)，那么：

    • 在基础步骤(basis step) 中证明 \(0 \in A\)，即 \(P\) 在 \(0\) 上为真
    • 归纳假设(induction hypothesis)：对于固定但任意的 \(n \ge 0\)，\(P\) 在每个自然数 \(0, 1, \dots, n\) 都成立
    • 在归纳步骤中，要利用归纳假设证明 \(P\) 在 \(n+1\) 上为真

    以上便是运用数学归纳法的模板。

  • 具体应用可参考教材列出的例子

• 鸽巢原理(pigeonhole principle)：若 \(A, B\) 是有限集合且 \(|A| > |B|\)，那么 \(A\) 到 \(B\) 的映射不是单射。

  • 通俗版：假设 \(A\) 表示一群鸽子，\(B\) 表示一些鸽巢，那么至少有一个鸽巢会有超过一只的鸽子
  • 可用数学归纳法证明（具体证明见教材，这里只给思路）
    • 基本步骤：证明 \(|B| = 0\) 时成立
    • 归纳假设：\(|B| \le n\) 时均成立
    • 归纳步骤：证明 \(|B| = n + 1\) 时成立

  定理

  令 \(R\) 为有限集合 \(A\) 上的二元关系，\(a, b \in A\)，若 \(R\) 上存在由 \(a\) 到 \(b\) 的路径，那么路径长度至多为 \(|A|\)。

  证明

  用鸽巢原理 + 反证法，其实挺简单的，所以这里不给证明，可参考教材。

• 对角化(diagonalization)：令 \(R\) 为集合 \(A\) 上的二元关系，且令 \(D\) 为 \(R\) 上的对角集合 (diagonal set)，即 \(\{a : a \in A \text{ and } (a, a) \notin R\}\)。\(\forall a \in A\)，令 \(R_a = \{b : b \in A \text{ and } (a, b) \in R\}\)，那么 \(D\) 和所有 \(R_a\) 均不同。

  定理

  幂集 \(2^{\mathbb{N}}\) 是不可数的。

  证明

  假设 \(2^{\mathbb{N}}\) 是可数无限的，也就是说假定存在一种方法可以枚举 \(2^N\) 的所有元素，如： $$ 2^{\mathbb{N}} = {R_0, R_1, R_2, \dots} $$

  （注意这些就是在对角化原理陈述中的集合 \(R_a\)，一旦我们考虑关系 \(R = \{(i,j) : j \in R_i\}\)）。现在考虑（对角）集合 $$ D = {n \in N : n \notin R_n} $$

  \(D\) 是自然数的一个子集，因此它应该出现在枚举 \(\{R_0, R_1, R_2, \dots\}\) 中的某个位置。

  • 但 \(D\) 不可能是 \(R_0\)，因为它在是否包含 0 这一点上与 \(R_0\) 不同（当且仅当 0 不在 \(R_0\) 中时，0 在 \(D\) 中）
  • 同样地，它也不可能是 \(R_1\)，因为它在 1 的归属上不同于 \(R_1\)
  • 以此类推，不得不推出这样一个结论：\(D\) 根本不会出现在这个枚举中，这就和假设产生了矛盾

Closures and Algorithms⚓︎

根据上述定义，我们可以得到一个计算对于任意给定的在有限集合 \(A = \{a_1, a_2, \dots, a_n\}\) 上的二元关系 \(R\) 的自反传递闭包的算法（该算法的正确性来自其对定义的直接实现）：

Initially R^* = emptyset
for i = 1, ..., n do
    for each i-tuple (b[1], ..., b[n]) in A^i do
        if (b[1], ..., b[i]) is a path in R then add (b[1], b[i]) to R^*

显然算法最终会得出正确答案。接下来要研究的问题是：它将在多少步之后终止(terminate)？答案取决于输入关系的规模，即依赖于集合 \(A\) 中元素的数量 \(n\)。因此，我们要寻找一个函数 \(f: \mathbb{N} \mapsto \mathbb{N}\)，使得当 \(n \ge 1\) 时，对于二元关系 \(R \subseteq A \times A, |A| = n\)，算法 \(f(n)\) 步后终止。

正如算法分析中常见的那样，我们允许 \(f(n)\) 是一个粗略的高估 (overestimate)，只要其增长率(rate of growth) 正确即可。下面就来探讨增长率这一话题。

Growth of Functions⚓︎

如果有两个函数 \(f, g: \mathbb{N} \mapsto \mathbb{N}\)，有 \(f \in \mathcal{O}(g), g \in \mathcal{O}(f)\)，那么可以写作 \(f \asymp g\)。容易证明，\(\asymp\) 是一个等价关系。

因此，所有从自然数集合到其自身的函数可通过 \(\asymp\) 划分为不同的等价类中。\(f\) 关于 \(\asymp\) 的等价类就是 \(f\) 的增长率。

Analysis of Algorithms⚓︎

现在对上述算法所需步骤做一个大致的估计：

• 算法需要检验每个序列 \((b_1, \dots, b_i)\)（长度至多为 \(n\)），确定它是否为 \(R\) 的一条路径，若是则将其放入 \(R^*\)
• 每次检验都需要不超过 \(n\) 次的这样的的基本运算：测试 \((a, b)\) 是否在 \(R\) 内，以及将 \((a, b)\) 放入 \(R^*\) 内
• 因此总运算次数不超过 \(n \cdot (1 + n + n^2 + \dots + n^n)\)，即该算法所需时间的增长率为 \(\mathcal{O}(n^{n+1})\)，效率超低！

于是考虑以下更高效的算法，并且可能比前面的算法看起来更为自然和直观：

# reflective
Initially R^* = R union {(a[i], a[i]) : a[i] in A}
# transitive
while there are three elements a[i], a[j], a[k] in A such that 
    (a[i], a[j]), (a[j], a[k]) in R^* but (a[i], a[k]) not in R^* do:
        add (a[i], a[k]) to R^*

算法的正确性不言而喻。那么算法何时停止呢？答案是至多 \(n^2\) 次迭代，因为 \(R^*\) 至多有 \(n^2\) 个二元对。并且由于每次迭代需要 \(\mathcal{O}(n^3)\) 的操作（因为三元组中的每个元素都要被搜一遍），所以整个算法的复杂度为 \(\mathcal{O}(n^5)\)。从原来的指数(exponential) 级降至多项式(polynomial) 级，该算法实现了巨大的提升！

然而这样还不够高效——一个显而易见的问题是该算法会重复遍历已经检查过的三元组。如果能够克服这个问题，算法的复杂度就能降至 \(\mathcal{O}(n^3)\)（每个三元组仅检查一次）。改进思路是将三元组按中间元素的索引升序排序遍历，对应算法如下：

Initially R^* = R union {(a[i], a[i]) : a[i] in A}
for each j = 1, 2, ..., n do
    for each i = 1, 2, ..., n and k = 1, 2, ..., n do
        if (a[i], a[j]), (a[j], a[k]) in R^* but (a[i], a[k]) not in R^* then
            add (a[i], a[k]) to R^*

要想证明该算法的正确性，就需要证明以下陈述：对于每个 \(j = 1, \dots, n\)，在外层循环执行完 \(j\) 次后，\(R^*\) 包含了所有 \((a_i, a_k)\) 对，满足 \(R\) 中从 \(a_i\) 到 \(a_k\) 之间有一条等级(rank)（路径上中间节点的最大索引，不包括起点和终点）不超过 \(j\) 的路径。可通过归纳法证明，具体证明过程见教材 \(P_{37}\)，这里不再赘述。

Closure Properties and Closures⚓︎

任何在有限集合上的闭包性质能在多项式时间内被算出来。假设在有限集合 \(D\) 上有不同元数的关系 \(R_1 \subseteq D^{r_1}, \dots, R_k \subseteq D^{r_k}\)，并有集合 \(A \subseteq D\)。现在要计算 \(A\) 在关系 \(R_1, \dots, R_k\) 下的闭包 \(A^*\)。我们可以通过泛化前面得到的 \(\mathcal{O}(n^5)\) 的传递闭包算法实现在多项式时间内的计算。

Initially A^* = A
while there is an index i, 1 <= i <= k, and r[i] elements a[j[1]], ..., a[j[r[i-1]]] in A^*
    and a[j[r[i]]] in D - A^* such that (a[j[1]], ..., a[j[r[i]]]) in R[i] do:
        add a[j[r[i]]] in A^*

该算法的复杂度为 \(\mathcal{O}(n^{r+1})\)，其中 \(n = |D|\) 且 \(r\) 为 \(r_1, \dots, r_k\) 中最大的数。

Alphabets and Languages⚓︎

计算理论的数学研究必须要从理解符号字符串的数学原理开始。

• 字母表(alphabet)：关于符号(symbol) 的有限集合
  • 和计算理论密切相关的一个字母表是二元字母表(binary alphabet) \(\{0, 1\}\)

• 字符串(string)：来自字母表的有限符号序列

  • 字符串的书写不需要用括号或逗号间隔，而是直接将符号连在一起写，比如 watermelon, 0110011
  • 单个符号等同于用该符号表示的字符串
  • 没有符号的字符串是空字符串(empty string)，记作 \(e\)
  • 一般使用 \(u, v, w, x, y, z\) 和希腊字母表示字符串
  • 所有在字母表 \(\Sigma\) 上的字符串集合记作 \(\Sigma^*\)
  • 字符串 \(w\) 的长度(length) 即序列长度，记作 \(|w|\)
  • 可将字符串看作一个函数 \(w: \{1, \dots, |w|\} \mapsto \Sigma\)；\(w(j)\) 的值就是 \(w\) 在第 \(j\) 个位置上的符号
  • 如果需要区分不同位置上的相同符号，我们将它们称为该符号的不同出现(occurrence)

  • 拼接(concatenation)：将两个来自相同字母表的字符串 \(x, y\) 结合起来，形成新的字符串，记作 \(x \circ y\) 或 \(xy\)

    • 形式上的，当且仅当 \(|w| = |x| + |y|, w(j) = x(j)\ (j = 1, \dots, |x|)\) 且 \(w(|x| + j) = y(j)\ (j = 1, \dots, |y|)\) 时， \(w = x \circ y\)
    • \(w \circ e = e \circ w = w\)
    • 拼接满足结合律，即 \((wx)y = w(xy)\)
    • 当且仅当存在字符串 \(x, y\)，满足 \(w = xvy\)，称字符串 \(v\) 为 \(w\) 的子字符串(substring)；此外还有以下特殊情况：
      • \(w = xv\) -> \(v\) 是 \(w\) 的后缀(suffix)
      • \(w = vy\) -> \(v\) 是 \(w\) 的前缀(prefix)

    • 字符串 \(w^i\) 的定义如下（一种归纳定义(definition by induction)）：

      \[ \begin{aligned} w^0 & = e, \quad \text{the empty string} \\ w^{i+1} & = w^i \circ w, \quad \text{for each } i \ge 0 \end{aligned} \]

  • 反转(reversal)：记作 \(w^R\)

    • 形式的归纳定义为：
      • 若 \(|w| = 0\)，则 \(w^R = w = e\)
      • 若 \(|w| = n + 1 > 0\)，则 \(w = ua\)，其中 \(a \in \Sigma\) 且 \(w^r = au^R\)

• 语言(language)：\(\Sigma^*\) 的任意子集（即字母表 \(\Sigma\) 上任意字符串构成的集合）

  • \(\Sigma^*, \emptyset, \Sigma\) 都是语言

  • 用以下形式表述无限 (infinite) 语言：

    \[ L=\{w\in\Sigma^*:w\text{ has property }P\} \]

  • 若 \(\Sigma\) 是有限字母表，那么 \(\Sigma^*\) 是可数无限的

  • 要想构建双射 \(f: \mathbb{N} \mapsto \Sigma^*\)，首先要确定字母表顺序，即 \(\Sigma = \{a_1, \dots, a_n\}\)，然后可按以下方式枚举 \(\Sigma^*\) 的成员：

    • \(\forall k \ge 0\)，所有长度为 \(k\) 的字符串应在长度为 \(k+1\) 字符串之前被枚举
    • 长度恰好为 \(k\) 的 \(n^k\) 个字符串按词典序(lexicographically) 枚举，即 \(a_{i_1}, \dots, a_{i_k}\) 先于 \(a_{j_1}, \dots, a_{j_k}\) 枚举，其中 \(0 \le m \le k - 1, i_l = j_l\ (l = 1, \dots, m), i_{m+1} < j_{m+1}\)

  • 由于语言本质上是集合，所以可通过集合运算（并、交、差）将语言结合起来

    • \(A\) 的补(complement) 为 \(\bar{A} = \Sigma^* - A\)

  • 语言的拼接(concatenation)：若 \(L_1, L_2\) 为在 \(\Sigma\) 上的语言，那么拼接为 \(L = L_1 \circ L_2 = L_1 L_2\)，其中

    \[ L=\{w\in\Sigma^*:w=x\circ y\text{ for some }x\in L_1\mathrm{~and~}y\in L_2\} \]

  • 克莱尼星号(Kleene star)：记作 \(L^*\)，是通过拼接 0 个或多个来自 \(L\) 的字符串构成的全部字符串的集合，即

    \[ L^*=\{w\in\Sigma^*:w=w_1\circ\cdots\circ w_k\text{ for some }k\geq0\text{ and some }w_1,\ldots,w_k\in L\} \]
    • 如果将字母表看作一种有限语言，那么 \(\Sigma^*\) 的定义和克莱尼星号是一致的

  • \(L\) 在拼接运算下的闭包(closure) 记作 \(L^+ = LL^*\)，即包含 \(L\) 和所有由 \(L\) 内字符串拼接而成的字符串的最小语言

    \[ \{w\in\Sigma^*:w=w_1\circ w_2\circ\cdots\circ w_k\text{ for some }k\geq1\text{ and some }w_1,\ldots,w_k\in L\} \]

Finite Representations of Languages⚓︎

计算理论的中心问题是通过有限规范表示语言。显然有限语言是能穷举出来的，所以仅需考虑无限语言的问题。

一个结论是：无论有多么强大的方法来表示语言，只有可数多个的语言能够被表示出来，只要表示本身也是有限的。所以那些不可数的语言自然无法使用有限表示了。

考虑表达式(expression) 的概念，即描述语言是如何通过前面介绍的运算构建的符号字符串。其中，在 \(\Sigma^*\) 上的正则表达式(regular expression) 是在字母表 \(\Sigma \cup \{(, ), \oslash, \mathsf{U}, *\}\) 的全体字符串，可按以下方式获取：

• \(\oslash\) 和 \(\Sigma\) 的每个成员都是正则表达式
• 若 \(\alpha, \beta\) 都是正则表达式，那么 \((\alpha, \beta)\) 也是正则表达式
• 若 \(\alpha, \beta\) 都是正则表达式，那么 \((\alpha \mathsf{U} \beta)\) 也是正则表达式
• 若 \(\alpha\) 是正则表达式，则 \(\alpha^*\) 也是正则表达式
• 只有上述四条均满足时才是正则表达式，否则就不是

正则表达式和它们所表示的语言之间的关系由函数 \(\mathcal{L}\) 构建，使得若 \(\alpha\) 是任意正则表达式，那么 \(\mathcal{L}(\alpha)\) 就是用 \(\alpha\) 表示的语言。函数 \(\mathcal{L}\) 的具体定义如下：

• \(\mathcal{L}(\oslash) = \emptyset, \mathcal{L}(a) = \{a\}\ (\forall a \in \Sigma)\)
• 若 \(\alpha, \beta\) 都是正则表达式，那么 \(\mathcal{L}((\alpha \beta)) = \mathcal{L}(\alpha)\mathcal{L}(\beta)\)
• 若 \(\alpha, \beta\) 都是正则表达式，那么 \(\mathcal{L}((\alpha \mathsf{U} \beta)) = \mathcal{L}(\alpha) \cup \mathcal{L}(\beta)\)
• 若 \(\alpha\) 是正则表达式，那么 \(\mathcal{L}(\alpha^*) = \mathcal{L}(\alpha)^*\)

每个能够用一种正则表达式表达的语言能够被无限多个其他正则表达式表示。我们通常会忽略正则表达式中多余的括号（\((, )\)）。

字母表 \(\Sigma\) 上的正则语言(regular language) 类定义为满足 \(L = \mathcal{L}(\alpha)\) 的全部语言 \(L\)，即能被正则表达式表达的全部语言。正则语言也可被看成是一种闭包——在 \(\Sigma\) 上的正则语言类就是以下语言集合（关于并、拼接、克莱尼星号运算）的闭包： $$ {{\sigma}:\sigma\in\Sigma}\cup{\emptyset} $$

特别为某种语言 \(L\) 设计，用于回答“字符串 \(w\) 是 \(L\) 的成员”这类问题的算法，称为语言识别装置(language recognition device)。

另一种用于指定语言的方法是语言生成器(language generators)，用于描述如何生成一个语言的通用示例 (generic specimen)。这样的方法不是一种算法，因为它不是为了回答问题而设计的，也不是完全明确地告诉我们要做什么，但它仍然是表示语言的重要而有用的手段。

评论区