Context-Free Languages⚓︎

Context-Free Grammars⚓︎

• 语言识别器(language recognizer)：接受合法字符串的设备
• 语言生成器(language generator)：生成语法正确的字符串的设备
  • 正则表达式可看作一种语言生成器

下面我们将认识一种更为复杂也更加强大的语言生成器，叫做上下文无关文法(context-free grammar, CFG)，基于对属于某种语言的字符串结构的更完整的理解。

对于上面的例子，考虑字符串 \(aaAb\)，符号 \(A\) 的上下文(context) 就是周围的（子）字符串 \(aa\) 和 \(b\)。不难发现，施加 \(A\) 的规则时独立于 \(A\) 的上下文，这便是“上下文无关”一词的由来。

在一条规则中，\(\rightarrow\) 左边的符号一般是大写字母，而像小写字母一般不会出现在 \(\rightarrow\) 左边——它们往往表示字符串生成过程的终结，所以称它们为终结符(terminals)。

下面给出 CFG 的形式定义：

• 当指代文法足够显而易见时，我们就会省去下标，即写作 \(A \rightarrow w, u \Rightarrow v\)

• 称如以下形式的任意序列为从 \(w_n\) 到 \(w_0\) 的 \(G\) 的推导(derivation)

  \[ w_0 \Rightarrow_G w_1 \Rightarrow_G \cdots \Rightarrow_G w_n \]
  • \(w_0, \dots, w_n\) 为 \(V^*\) 中的任意字符串
  • 推导的长度(length)（或步骤(steps)）\(n\) 为任意自然数

例子

例 1 例 2

用 CFG 表示简单的英语句子，但还是有不少 bug。

生成匹配的括号：

在数据结构课上，我们会用栈来检验字符串中的括号匹配。

Parse Trees⚓︎

根据上一节例 2 给出的 CFG，对于字符串 \(()()\)，可以通过两种截然不同的推导得到：

从结果上看，两种推导是一样的；它们唯一的区别在于使用规则的顺序(order)。我们可以用一张图表示这些推导：

• 称这幅图为解析树(PDArse tree)
• 树节点(node) 的标签表示 \(V\) 的一个符号
• 所有的叶子都是终结符或空字符串 \(e\)
• 通过从左往右拼接字符串，得到推导出来的字符串，这边是解析树的产出(yield)

对解析树更形式化的定义如下：

• 每个由 \(a \in \Sigma\) 构成的单节点就是一棵解析树，同时充当根、叶子和产出

• 若 \((A \rightarrow e) \in R\)，那么右图就是一棵解析树，其中根为 \(A\)，叶子和产出为 \(e\)

• 若下图所示的一组树均为解析树

  

  其中 \(n \ge 1\)，根节点分别为 \(A_1, \dots, A_n\)，产出分别为 \(y_1, \dots, y_n\)，并且 \((A \rightarrow A_1 \dots A_n) \in R\)，那么下图所示的树也是一棵解析树。其中根为 \(A\)，叶子为上述所有解析树的叶子，产出为 \(y_1 \dots y_n\)

  

• 除上述情况外的都不是解析树

解析树能够表示推导的等价类(equivalence classes)。令 \(G = (V, \Sigma, R, S)\) 为 CFG，\(D = x_1 \Rightarrow x_2 \Rightarrow \dots \Rightarrow x_n, D' = x_1' \Rightarrow x_2' \Rightarrow \dots \Rightarrow x_n'\) 为 \(G\) 的两个推导，其中 \(x_i, x_i' \in V^*\ (i = 1, \dots, n);\ x_1, x_1' \in V - \Sigma;\ x_n, x_n' \in \Sigma^*\)。当 \(n > 2\) 且存在整数 \(k\)，\(1 < k < n\)，满足：

• \(\forall i \ne k, x_i = x_i'\)
• \(x_{k-1} = x_{k-1}' = uAvBw\)，其中 \(u, v, w \in V^*, A, B \in V - \Sigma\)
• \(x_k = uyvBw\)，其中 \(A \rightarrow y \in R\)
• \(x_k' = uAvzw\)，其中 \(B \rightarrow z \in R\)
• \(x_{k+1} = x_{k+1}' = uxvyw\)

那么称 \(D\) 先于(precedes) \(D'\)，记作 \(D \prec D'\)。

例子

当 \((D, D')\) 属于 \(\prec\) 的自反、对称、传递闭包时，称 \(D, D'\) 是相似的(similar)。说人话就是：如果其中一个推导能够通过“交换(switching)”使用规则的顺序来得到另一个推导，那么这两个推导就是相似的。

每个推导的等价类都满足相似性，也就是说每棵解析树都包含一个在 \(\prec\) 关系下最大的(maximal) 推导，即先于任何推导的推导。这样的推导就叫做最左推导(leftmost derivation)。可按以下步骤从解析树中获得最左推导：从根节点开始，通过运用解析树蕴含的规则，重复替换最左侧的非终结符。

类似地，最右推导(rightmost derivation) 就是不先于任何推导的推导，也可通过类似的方式得到。每一棵解析树有且仅有一个最左推导和一个最右推导。以最左推导为例：每棵树的最左推导是唯一确定的，因为每一步都有一个需要替换的非终结符，即最左侧的那个。最右推导同理。

判断何时某个推导步是最左推导的一部分是比较容易的一件事。当且仅当 \(x = wA\beta, y = w\alpha\beta\)，其中 \(w \in \Sigma^*, \alpha, \beta \in V^*, A \in V - \Sigma\) 且 \(A \rightarrow \alpha\) 是 \(G\) 的一条规则时，记作 \(x \xRightarrow{L} y\)。

• 因此，若 \(x_1\Rightarrow x_2\Rightarrow\cdots\Rightarrow x_n\) 是最左推导，那么实际上就是 \(x_1 \xRightarrow{L} x_2 \xRightarrow{L} \cdots \xRightarrow{L} x_n\)
• 最右推导的对应记号就是 \(x \xRightarrow{R} y\)

Ambiguity⚓︎

假如文法 \(G'\) 存在能来自两棵或多棵解析树的字符串，那么称 \(G'\) 是二义的(ambiguous)。这样的二义文法不利于解析，因为没有唯一的解析树，即语言中的每个字符串没有唯一的“意义 (meaning)”。

好在我们有方法能够消除二义性：引入新的非终结符 \(T, F\)，也就是说存在能够产生相同语言的非二义(unambiguous) 文法。事实上，存在 CFL 满足每个产生它们的 CFG 必须是二义的，这样的语言称为内在二义的(inherently ambiguous)。

Pushdown Automata⚓︎

并不是所有 CFL 都能被 FA 识别，因为 CFL 不一定是正则的。比如考虑这个例子：\(\{ww^R: w \in \{a, b\}^*\}\)，它是上下文无关的，但是无法用 FA 表示。然而，如果机器能够在读取时积累输入字符串，每次向已存储的字符串附加一个符号，那么机器就能以非确定的方式猜测出何时到达输入的中心，从而每次能检查内存中的符号。这样的存储设备是一个栈(stack)，因为只允许读取和写入顶部的符号。

现在我们用形式定义表述将栈作为辅助存储 (auxiliary storage) 的自动机的思路：

• 直观地，若 \(((p, a, \beta), (q, \gamma)) \in \Delta\)，那么处在状态 \(p\) 且栈的顶层符号为 \(\beta\) 的自动机 \(M\) 可能会从输入纸带中读取 \(a\)（若 \(a = e\) 就是没有读到任何东西），用 \(\gamma\) 替换栈上的 \(\beta\)，并进入状态 \(q\)。这样的一个配对就是 \(M\) 的一个转移(transition)。
• 由于可在 \(M\) 上同时作用多个转移，因此是不确定的 (nondeterministic)
• 向栈压入(push) 符号就是在栈顶添加一个符号；向栈弹出(pop) 符号就是在栈顶删除符号

• PDA 的配置(configuration) 定义为 \(K \times \Sigma^* \times \Gamma^*\) 的一个成员

  • 假如有配置 \((q, w, abc)\)，那么 \(a\) 在栈顶，\(c\) 在栈底

• 若 \((p, x, \alpha), (q, y, \zeta)\) 均为 \(M\) 的配置，当存在一个转移 \(((p, a, \beta), (q, \gamma)) \in \Delta\)，满足 \(x = ay, \alpha = \beta \eta, \zeta = \gamma \eta\ (\eta \in \Gamma^*)\) 时，称 \((p, x, \alpha)\) 一步产生了(yields in one step) \((q, y, \zeta)\)，写作 \((p, x, \alpha) \vdash_M (q, y, \zeta)\)

  • 记它的自反传递闭包为 \(\vdash_M^*\)

• 当且仅当对于某些状态 \(p \in F\)，\((s, w, e) \vdash_M^* (p, e, e)\)，称 \(M\) 接受了字符串 \(w \in \Sigma^*\)

• 从另一种角度看“接受”这件事：存在配置序列 \(C_0, C_1, \dots, C_n (n > O)\)，满足 \(C_0 \vdash_M C_1 \vdash_M \dots \vdash_M C_n, C_0 = (s, w, e)\) 且 \(C_n = (p, e, e)\ (p \in F)\)

  • 我们称这样的序列为 \(M\) 的一次计算(computation)，长度/步数为 \(n\)

• \(M\) 接受的语言 \(L(M)\) 即为所有被 \(M\) 接受的字符串的集合

例子

例 1 例 2

Pushdown Automata and Context-Free Grammars⚓︎

证明分为两部分（两条引理的证明）：

下面证明定理的另一半：

Languages that Are and Are Not Context-Free⚓︎

Closure Properties⚓︎

Pumping Theorem⚓︎

令 \(G = \{V, \Sigma, R, S\}\) 为 CFG，

• \(G\) 的扇出(fanout) \(\phi(G)\) 是 \(R\) 的所有规则中箭头右边最大的符号数
• 解析树的路径(path) 是指由不同节点构成的序列，每一个节点和上一个节点用线段连接，其长度(length) 即为线段数
• 解析树的高度(height) 是最长路径的长度

泵定理 (pumping theorem)

令 \(G = (V, \Sigma, R, S)\) 为上下文无关文法，任意长度超过 \(\phi(G)^{|V - \Sigma|}\) 的字符串 \(w \in L(G)\) 能被重写为 \(w = uvxyz\)，满足 \(v\) 或 \(y\) 为非空（即 \(vy \ne e\)），且每个 \(n \ge 0\) 的字符串 \(uv^nxy^nz\) 均在 \(L(G)\) 内。

证明

• 令 \(w\) 为字符串，\(T\) 为解析树，其根节点为 \(S\)，产出 \(w\) 为所有同根和同产出的解析树中叶子数最少的那个
• 由于产出长于 \(\phi(G)^{|V - \Sigma|}\)，所以 \(T\) 的路径长至少为 \(|V - \Sigma| + 1\)，即有 \(|V - \Sigma| + 2\) 个节点；其中只有一个节点是终结符，其余均为非终结符
• 由于路径上的节点数多于非终结符的个数，因此存在路径上两个不同节点有相同成员 \(A \in V - \Sigma\)

观察以上路径：

• 令 \(u, v, w, x, y, z\) 为 \(T\) 的部分产出
• \(T'\) 中除去 \(T''\) 的部分能够被重复任意多次（包括 0 次），以产生其他解析树，对应产出为 \(uv^nxy^nz\)

Algorithms for Context-Free Grammars⚓︎

下面展示如何将 \(G\) 转换为对应的 CNF。有以下三种在规则右侧违背 CNF 的情况：

• 长规则（长度 >= 3）
• 空 (e) 规则（\(A \rightarrow e\ (A \notin S)\)）
• 短规则（\(A \rightarrow a\) 或 \(A \rightarrow B\)）

接下来将一一移除这些违背 CNF 定义的情况：

• 长规则：假设 \(A \rightarrow B_1 B_2 \dots B_n \in R\)，其中 \(B_1 \dots B_n \in V\) 且 \(n \ge 3\)

  • 用新的 \(n - 1\) 条规则替换它，即：

    \[ \begin{aligned}A\to&B_1A_1,\\A_1\to&B_2A_2,\\&\vdots\\A_{n-2}\to&B_{n-1}B_n\end{aligned} \]

    其中 \(A_1, \dots, A_{n-2}\) 为非终结符

  • 重复上述替换过程，结果一定等价于原来的那条规则，且箭头右侧长度不超过 2

• e 规则

  • 定义一个可擦除非终结符的集合 \(\mathcal{E}=\{A\in V-\Sigma:A\Rightarrow^*e\}\)，即所有可能推导出空字符串的非终结符

  • 这一过程可通过以下闭包计算完成：

    E := emptyset
    while there is a rule A -> alpha with alpha in E* and A not in E do
        add A to E
    

  • 有了 \(\mathcal{E}\) 之后，可根据它删掉 \(G\) 中所有的 e 规则——重复以下步骤：对于每条形如 \(A \rightarrow BC\) 或 \(A \rightarrow CB\)（\(B \in \mathcal{E}, C \in V\)）的规则，将 \(A \rightarrow C\) 加入到文法中

  • 这么操作下来，除了 \(e\) 不能推导出来外，其他推导照旧，因为上述过程忽略了规则 \(S \rightarrow e\)

• 短规则

  • \(\forall A \in V\)，通过以下简单的闭包算法，计算从 \(A\) 推导出的符号集合 \(\mathcal{D}(A) = \{B \in V: A \Rightarrow^* B\}\)：

    D(A) := {A}
    while there is a rule B -> C with B in D(A) and C not in D(A) do
        add C to D(A)
    

  • 若 \(a\) 为终结符，\(\mathcal{D}(a) = a\)

  • 我们用 \(A \rightarrow B'C'\) 替换 \(A \rightarrow BC\)，其中 \(B' \in \mathcal{D}(B), C' \in \mathcal{D}(C)\)，从而消除了短规则
  • 最后为 \(A \rightarrow BC\) 增加规则 \(S \rightarrow BC\)，满足 \(A \in \mathcal{D}(S) - \{S\}\)

最后分析一下上述操作的时间复杂度：

• 长规则：\(\mathcal{O}(n)\)
• e 规则：\(\mathcal{O}(n^2)\)
• 短规则：\(\mathcal{O}(n^2)\)

因此总的时间复杂度为 \(\mathcal{O}(n^2)\)

CNF 的一个好处是它能在多项式时间内判断是否能从一个文法中生成某个字符串，对应算法如下（通过分析 \(x\) 的所有子字符串判断 \(x \in L(G)\)）：

for i := 1 to n do
    N[i][i] = {x[i]}; all other N[i][j] are initially empty
for s := 1 to n - 1 do
    for i := 1 to n - s do
        for k := i to i + s - 1 do
            if there is a rule A -> BC in R with B in N[i][k] and C in N[k + 1][i + s]
                then add A to N[i][i + s]
    Accept x if S in N[1][n]

该算法是一种动态规划(dynamic programming) 算法，因为它将一个问题划分为多个子问题，并且其解是从子问题的解中构建出来的。

为证明算法正确性，我们需声称：对于自然数 \(0 \le s \le n\)，算法经 \(s\) 次迭代后，\(\forall\ i = 1, \dots, n - s\)， $$ N[i,i+s]={A\in V:A\Rightarrow^*x_i\cdots x_{i+s}} $$

成立。（可通过归纳法证明，见教材 \(P_{155-156}\)）

上述算法的时间复杂度为 \(\mathcal{O}(n^3)\)。

评论区