上下文无关文法

上下文无关文法的定义

定义文法 \(G = (V, T, P, S)\)，其中产生式，除了空产生式外，有如下特点：

\[ \forall \alpha \to \beta \in P, \quad \beta \in (V \cup T)^{\ast}, \quad \text{All have } |\beta| \geq |\alpha|, \text{and } \alpha \in V \]

派生树

设有 CFG $ G = (V, T, P, S)\(，\)G$ 的派生树是满足如 下条件的有序树。

1. 树的每个顶点有一个标记 \(X\)，且 \(X \in V \cup T \cup \{\epsilon\}\)；
2. 树根的标记为 \(S\)；
3. 如果非叶子顶点 \(v\) 标记为 \(A\)，\(v\) 的儿子从左到右依次为 \(v_1, v_2, \dots, v_n\)，并且它们分别标记为\(X_1, X_2, \dots, X_n\)，则 \(A \to X_1 X_2 \cdots X_n \in P\)；
4. 如果 \(X\) 是一个非叶子顶点的标记，则 \(X \in V\)；
5. 如果顶点 \(v\) 标记为 \(\epsilon\)，则 \(v\) 是该树的叶子，并且 \(v\) 是其父顶点的惟一儿子。

派生树都是 CFG 的派生树。

顶点的结果

派生树 \(T\) 的所有叶子结点从左到右的符号串为 \(X_1 X_2 \cdots X_n\)是 \(T\) 的结果。

CFG 的化简

删除无用符号

无用符号

CNF：乔姆斯基范式文法

CFG \(G = (V, T, P, S)\) 中的产生式形式为：\(A \to BC, \, A\to a\)，其中 \(A,B,C \in V,\, a \in T\)，需要注意的是此 CFG 已完成化简。

利用 CNF 范式派生长度为 \(n\) 的串，刚好需要 \(2n-1\) 步。

上下文无关文法的性质

CFL 的泵引理

对于任意的 CFL \(L\)，存在仅仅依赖于 \(L\) 的正整数 \(N\)，对于任意的 \(z \in L\)，当 \(|z| \geq N\) 时，存在 \(u, v, w, x, y\)，使得 \(z = uvwxy\)，同时满足：

1. \(|vwx| \leq N\)；
2. \(|vx| \geq 1\)；
3. 对于任意的非负整数 \(i\)，\(u v^i w x^i y \in L\)。

利用 CFL 泵引理证明一个语言不是 CFL

1. 首先假设该语言是 CFL，则其满足泵引理，任选 \(N\)；
2. 找到语言中的句子 \(z \in L\) 且 \(|z| \geq N\)；
3. 分析 \(v\)、\(x\) 的各种取值，当满足 \(z = uvwxy\)，且 \(|vwx| \leq N\)，\(|vx| \geq 1\) 时，均能找到 \(i \geq 0\)，使得 \(i\)，\(u v^i w x^i y \notin L\)。

Ogden 引理

对于任意的 CFL \(L\)，存在仅仅依赖于 \(L\) 的正整数 \(N\)，对于任意的 \(z \in L\)，当 \(z\) 中至少含有 \(N\) 个特异点时，存在 \(u, v, w, x, y\)，使得 \(z = uvwxy\)，同时满足：

1. \(|vwx|\) 中的特异点的数目 \(\leq N\)；
2. \(|vx|\) 中的特异点的数目 \(\geq 1\)；
3. 对于任意的非负整数 \(i\)，\(u v^i w x^i y \in L\)。

CFL 在并、乘积、闭包运算下是封闭的，但在交运算下不封闭

CYK Algorithm

输入：CNF \(G = (V, T, P, S)\)，\(x\)； 输出：\(x \in L\) 或者 \(x \notin L\)；

\(V_{i,k}\)：可以派生出子串 \(x_{i,k}\) 的变量集合，\(x_{i,k}\) 表示从 \(i\) 开始，长度为 \(k\) 的子串。

1. for i = 1 in |x| \(V_{i,1} = \{A \mid A \to x_{i,1} \in P\}\)
2. for k = 2 in |x| {for i = 1 to |x| - k + 1} $V_{i,k} = $
   1. for j = 1 to k - 1 \(V_{i,k} = V_{i,k} \cup \{A \mid A \to BC \text{ and } B \in V_{i,j} \text{ and } C \in V_{i + j,k - j}\}\)

hw13

题目1： 使用CFL的泵引理证明 \(L = \{ ww \mid w \in \{a, b\}^{\ast} \}\) 不是上下文无关语言.

解答1：

我们使用 CFL 的泵引理来证明 \(L = \{ ww \mid w \in \{a, b\}^\ast \}\) 不是上下文无关语言。

假设 \(L\) 是一个上下文无关语言，则它满足 CFL 的泵引理。

设 \(N\) 为泵引理中的 \(N\)，取句子 $ z = a^{N} b^{N} a^{N} b^{N} L $

接下来分析 \(vwx\) 的各种取值：

1. 因为 \(|vwx| \leq N\)，不妨先假设 \(vwx \subseteq a^{N}\) 或者 \(b^{N}\)，显然对于 \(\forall i > 0\)，都会破坏 \(L\) 的结构，即要求 \(ww \in L\)。
   
   
2. 然后再分析 \(vwx\) 跨越了 \(a\) 部分或者 \(b\) 部分，由于 \(|vwx| \leq N\)，可以证明 \(vwx\) 最多横跨一个 \(a\) 和一个 \(b\)，也即是类似 \(a \cdots ab \cdots b\) 和 \(b \cdots ba \cdots a\) 的结构；
   
   
   1. 假设 \(vwx\) 横跨第一个 \(a\) 和 \(b\)。设 $ v = a^{m}, , x = b^{n}$，则 \(\forall i > 0\)，\(u a^{im} w b^{in} y \notin L\)，这很好证明：此时 \(u a^{im} w b^{in} y\) 可以写成 \(a^{N + im} b^{N + in} a^{N} b^{N}\) 的形式，为了保证 \(ww\) 的结构，只能如此分割 \(a^{N + im} b^{N + in}\) 和 \(a^{N} b^{N}\)，因为 \(|vx| \geq 1\)，所以不存在 \(i\) 使得分割后得两个句子相等；
      
      
   2. 同理可以证明 \(vwx\) 横跨第二个 \(a\) 和 \(b\) 时同样不满足泵引理；
      
      
   3. 对于 \(vwx\) 横跨第一个 \(b\) 和 第二个 \(a\) 的情况，此时 \(u a^{im} w b^{in} y\) 可以写成 \(a^{N} b^{N + im} a^{N + in} b^{N}\) 的形式，同样为了保证 \(ww\) 的结构，只能如此分割 \(a^{N} b^{N + im}\) 和 \(a^{N + in} b^{N}\)，显然分割后的句子不相等，也就是不满足泵引理。
      
      

综上，\(L\) 不是 CFL。

题目2： 给定文法 \(G\) 如下：

[ \[\begin{align*} &S \to AB \,|\, AA \,|\, BC \\ &A \to CD \,|\, a \\ &B \to BD \,|\, SB \,|\, b \\ &C \to c \\ &D \to DB \,|\, b \end{align*}\] ]

根据算法 CYK 算法，请识别字符串“aabbc”是否属于 \(L(G)\)?

解答2： \(x = \text{"aabbc"}\)，长度 \(|x| = 5\)。

构造一个二维表 \(V_{i,k}\)，其中 \(V_{i,k}\) 表示从位置 \(i\) 开始，长度为 \(k\) 的子串可以由哪些非终结符生成。

1. 第一步：处理长度为 1 的子串
   根据文法的终结符规则，填充 \(V_{i,1}\)：
   • \(x_1 = a \implies V_{1,1} = \{A\}\)
   • \(x_2 = a \implies V_{2,1} = \{A\}\)
   • \(x_3 = b \implies V_{3,1} = \{B, D\}\)
   • \(x_4 = b \implies V_{4,1} = \{B, D\}\)
   • \(x_5 = c \implies V_{5,1} = \{C\}\)
2. 第二步：处理长度为 2 的子串
   根据文法的组合规则，填充 \(V_{i,2}\)：
   • \(x_{1,2} = "aa" \implies V_{1,2} = \{S\}\) （因为 \(A \to AA\)）
   • \(x_{2,2} = "ab" \implies V_{2,2} = \{B\}\) （因为 \(S \to AB\)）
   • \(x_{3,2} = "bb" \implies V_{3,2} = \{B, D\}\) （因为 \(B \to BD\) 和 \(D \to DB\)）
   • \(x_{4,2} = "bc" \implies V_{4,2} = \{S\}\) （因为 \(S \to BC\)）
3. 第三步：处理长度为 3 的子串
   根据文法的组合规则，填充 \(V_{i,3}\)：
   • \(x_{1,3} = "aab" \implies V_{1,3} = \{B\}\) （因为 \(S \to AB\)）
   • \(x_{2,3} = "abb" \implies V_{2,3} = \{S\}\) （因为 \(S \to AB\) 和 \(B \to SB\)）
   • \(x_{3,3} = "bbc" \implies V_{3,3} = \{S\}\) （因为 \(S \to BC\)）
4. 第四步：处理长度为 4 的子串
   根据文法的组合规则，填充 \(V_{i,4}\)：
   • \(x_{1,4} = "aabb" \implies V_{1,4} = \{S\}\) （因为 \(S \to AB\) 和 \(B \to SB\)）
   • \(x_{2,4} = "abbc" \implies V_{2,4} = \{S\}\) （因为 \(S \to BC\)）
5. 第五步：处理长度为 5 的子串
   根据文法的组合规则，填充 \(V_{1,5}\)：
   • \(x_{1,5} = "aabbc" \implies V_{1,5} = \{S\}\) （因为 \(S \to AB\) 和 \(B \to SB\)）

最终，\(V_{1,5}\) 包含 \(S\)，因此字符串 “aabbc” 属于文法 \(G\) 的语言 \(L(G)\)。