跳转至

03A

约 1907 个字 预计阅读时间 6 分钟

让我们从正则语言往上走一大步。如果说正则语言和有理性（rationality）紧密联系，那么上下文无关语言（context-free language, CFL）就是与代数性（algebraicity）紧密联系的。但是，这里它的代数性质事实上会麻烦很多，我们也会看到，上下文无关语言的充要条件不再来自于代数，而是来自于形式语言相关的内容。

在本文中将继续弱化机器刻画的内容而强化代数相关的刻画，因此，我们将尝试从语法到代数刻画再到自动机的方式。需要指出，事实上正则语言也应当可以采取这样的形式进行介绍，只要将正则语法给定，就可以推出大部分结论。

Basic Definitions 基本定义

在第一节中我们已经提到了语法的概念，在此直接表述上下文无关语法的版本：

定义

一个上下文无关语法（context-free grammar） \(G\) 是一个四元组 \((V, \Sigma, S, R)\) ，其中：

  • \(V\) 是一个有限集，称为符号集（set of symbols）；
  • \(\Sigma \subseteq V\) ，其中的元素称为终止符（terminals），事实上，它就是这个语法生成的语言的字母表；
  • \(S \in V - \Sigma\)，称为起始符（start symbol）；
  • \(R \subseteq (V - \Sigma) \times V^\ast\)，是一个有限集（这由定义显然），称为生成规则（production），其中的元素记为 \(A \rightarrow u\)，若 \((A, u) \in R\)。

事实上，我们通常将 \(S\) 称为公理（axioms）而将剩下三个分离开来，在下一节中，这样操作的动机会显得更加充分：语言事实上描述了一套逻辑系统，\(R\) 作为它的演绎过程而存在，而公理事实上超脱在演绎过程之外。

记号

我们称一步演绎/推导（derivation）为一个从字符串 \(xAy \in V^\ast\) 到达 \(xuy \in V^\ast\) 的过程，其中 \(A \to u \in R\)，\(A \in V - \Sigma\)，记作 \(xAy \Rightarrow_G xuy\)。

形式上将，这就是一步替换，将非终止符继续推导下去的过程。

记号

如果经过一串长为 \(n\) 的演绎可以将 \(w \in V^\ast\) 转变为 \(u \in V^\ast\)，则我们将其记为 \(w \Rightarrow^\ast_G u\)。

这样，\(G\) 生成的语言就可以被定义了：\(L(G) = \{w: S \Rightarrow_G^\ast w\}\)。可见，生成规则往往是最核心的部分，因此我们很多时候只给出生成规则，其他部分都省略。

注意，在这里定义的生成规则 \(R\) 与一般语法的差别在于，箭头左侧的符号一定是一个非终止符。而在无限制的语法（unrestricted grammar，或 free grammar）中，我们对左侧和右侧的符号都仅限制为 \(V^\ast\)，在上下文相关语法（context-sensitive grammar）中，我们要求生成规则的形式为 \(xAy \rightarrow xuy\)，其中 \(x, u, y \in V^\ast\)，\(A\) 为非终止符。也就是说，只有在特定上下文中（即 \(x, y\)）\(A\) 才可被如此推导。这样的比较应该能更加明确“上下文无关”的含义：无论何时何地看到了非终止符，它都能作此推导。

而正则语法，如前所述，只包含 \(X \rightarrow a, X \rightarrow aY, X \rightarrow \varepsilon\) 三种形式，其中 \(X, Y\) 为非终止符，\(a\) 为终止符。很容易看出，根据我们的定义，正则语法包含于 CFG 当中。事实上，存在这样一个层级关系（hierachy）：

  • 无限制的语法（Type 0）
  • 上下文相关语法（Type 1）
  • 上下文无关语法（Type 2）
  • 正则语法（Type 3）

这个层级关系被归为 N. Chomsky 的成果，称为 Chomsky 层级。这个名字会在我们此后的讨论中一次又一次地出现。

定义

如果存在 \(A \in V - \Sigma\)，有 \(A \rightarrow x\) 和 \(A \rightarrow y\) 两条生成规则，且 \(x \neq y\)，那么我们就称这个语法是两可的（ambiguous）。如果没有 \(X \rightarrow Y\) 或 \(X \rightarrow \varepsilon\) 这样的规则，其中 \(X, Y\) 为非终止符，那么我们就称它是真的（proper）。

以下一个结论对于读者来说应当不难证明：

命题

可以找到一个等价的上下文无关语法 \(G^\prime\) 使得 \(L(G) = L(G^\prime)\)，且：

  • 若 \(\varepsilon \in L(G)\) 则 \(G^\prime\) 中只有一条规则 \(S \rightarrow \varepsilon\) 是形如 \(X \rightarrow \varepsilon\) 的；
  • 反之，则 \(G^\prime\) 是真的。

定义

称一个语言 \(L\) 为上下文无关语言，若存在上下文无关语法 \(G\) 使得 \(L(G) = L\)。

当然，这样的语法可能有很多种，在下一节中，我们将会讨论怎样标准化上下文无关语法，将其化简成统一的形式。

下面给出几个上下文无关语言的例子，它们都是相当重要的：

  • Dyck 语言，设 \(A\) 为一字母表，\(\bar A\) 是它的一个复制（即一个与之无交但元素一一对应的集合），\(A\) 中的元素与 \(\bar A\) 对应，\(a \in A\) 被对应到 \(\bar a \in \bar A\)。推广到 \((A \cup \bar A)^\ast\) 中，我们有 \(\bar{xy} = \bar y \bar x\)。由生成规则 \(S \rightarrow TS|\varepsilon\) 和 \(S \rightarrow aS\bar a\) 生成的语言被称为 Dyck 语言。事实上，很容易看出，它可以被视为“括号配对”的语言，\(|A|\) 指的就是括号的种类数。
  • Lukasiewicz 语言，字母表为 \(\{a, b\}\)，生成规则为 \(S \rightarrow aSS|b\)。

练习

在这里，证明非上下文无关语言事实上并不容易，因为我们需要证明，不存在一个上下文无关语法能够表出这种语言。因此，本节只要求证明“是”，最简单的方法就是构造上下文无关语法。

  1. 证明 \(a^nb^n, n \geqslant 1\) 的字符串构成的语言为 CFL 并构造其正则语法；
  2. 证明不是所有上下文无关语法都可以化为非两可的上下文无关语法（提示：考虑 \(\{a^nb^mc^md^n: m, n > 0\} \cup \{a^nb^nc^md^m: m, n > 0\}\) 对应的上下文无关语法）；
  3. 证明上面提到的等价性；
  4. 证明正则语言的部分闭包性质：并、衔接、翻转、Kleene 星，同态的像及其原像；
  5. 表明 Lukasiewicz 语言事实上就是 \(A\) 为单元素集 \(\{a\}\) 的 Dyck 语言与 \(\{b\}\) 的衔接；
  6. 计算 Dyck 语言的句法幺半群，事实上，它被称为双循环半群（bicyclic semigroup）。

Linear Systems 线性系统

在正则语言那里已经给出了线性方程的概念，当时我们考虑的是形如 \(X = KX + L\) 的结构。但是在这里，因为衔接不是交换的，线性方程就必须变成 \(X = KXK^\prime + L\)。

TODO: 线性方程的解法和格性质，Parikh 定理以及 Ginsberg-Spanier 对它的推广

Normal Forms 标准型

TODO: Greibach 标准型和算子标准型，以及关于统一的标准型的介绍

Applications of Greibach Normal Form Greibach 标准型的应用

TODO: Shamir 定理，Chomsky-Schützenberger 定理以及 Wechler 定理

Pumping Lemma 泵引理

TODO: Ogden 引理，交换引理以及各种变体，"Di-lemma"，PII: 0304-3975(88)90138-7 | Elsevier Enhanced Reader，强泵引理（D. S. Wise）

An Algebraic View 代数刻画

TODO: 代数级数、余代数刻画、Chomsky 代数、公理化与方程、上下文无关代数

Push-down Automata 下推自动机

Group As Memory 作为内存的群

TODO 0601061.pdf (arxiv.org) 第四节

Algebraic Applications 代数应用

TODO: 使用 CFL 研究有限展示代数、分次代数以及 Hilbert 级数

参考资料

M. Blattner and S. Ginsburg. Canonical forms of context-free grammars and position restricted grammars. In Karpinski, editor, Fundamentals of Computing Theory, volume 56 of Lect. Notes Comp. Sci., 1977