上下文无关语言 ¶

上下文无关文法 ¶

• Context-Free Grammar (CFG) 一些生成字符串的规则
  • e.g. \(S\to aSb,\ S\to A,\ A\to c,\ A\to e\)
    • 可以生成 \(S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aaAbb\Rightarrow aabb\)
  • 其中 \(S\) 是起始符号（start symbol），大写字母是非终结符号（non-terminals），小写字母是终结符号（terminals）
• 形式化定义，一个 CFG 是一个四元组 \(G=(V, \Sigma, S, R)\)
  • \(V\)：a finite set of symbols
  • \(\Sigma\subseteq V\)：the set of terminals
    • \(V-\Sigma\)：the set of non-terminals（即 \(V\setminus\Sigma\)）
  • \(S\subseteq V-\Sigma\)：the start symbol
  • \(R\subseteq (V-\Sigma)\times V^*\)：the set of rules
    • 即一个由非终结符号和转换得到的字符串组成的元组构成的集合
• 推导
  • derive in one step: for any \(x, y, z\in V^*\), for any \(A\in V-\Sigma\)
    • \(xAy\Rightarrow_G xuy\) if \((A, u)\in R\)
  • derive: for any \(w, u\in V^*\)
    • \(w\Rightarrow_G^* u\) if \(w=u\) or \(w\Rightarrow_G\cdots\Rightarrow_G u\)
• 生成字符串：\(G\) generates a string \(w\in\Sigma^*\) if \(S\Rightarrow_G^* w\)
• 生成语言：\(G\) generates \(L(G) = \{w\in\Sigma^*: G\text{ generates }w\}\)
• 上下文无关语言（Context-Free Language，CFL）
  • A language is context-free if some CFG generates it

Chomsky Normal Form¶

• 一个 CFG 是 Chomsky Normal Form（CNF）的，如果它的所有规则都是以下三种形式之一：
  • \(S\to e\)：只有起始符号可以推导出空串
  • \(A\to BC\) for some \(B, C\in V-\Sigma\)：非终结符号可以推导出两个非终结符号
  • \(A\to a\) for some \(a\in\Sigma\)：非终结符号可以推导出一个终结符号
• 特点：生成一个长度为 \(n\) 的串需要 \(2n-1\) 步推导
• 定理：任何一个 CFG 都可以转换成等价 CNF 形式（即保证生成语言相同）

Pushdown Automata¶

• 下推自动机（Pushdown Automata, PDA）是 NFA 的一个扩展
  • 在 NFA 基础上加了一个额外的栈结构，并在状态转移时会进行栈操作
  • PDA 可以和 CFG 等价
• 形式化定义，一个 PDA 是一个六元组 \(P=(K, \Sigma, \Gamma, \Delta, s, F)\)
  • 其中 \(K, \Sigma, s, F\) 的含义和 NFA 中的相同
  • \(\Gamma\): stack alphabet，即栈里面会出现的符号集合
  • \(\Delta\): transition relation, a finite subset of \((K\times (\Sigma\cup\{e\})\times \Gamma^*)\times (K\times\Gamma^*)\)
    • 对比 NFA \((K\times (\Sigma\cup\{e\}))\times K\)，即在转移前后都加了栈相关字符串
    • 前一个 \(\Gamma^*\) 是栈顶的字符串，匹配后 pop 出来
    • 后一个 \(\Gamma^*\) 是在转移后要 push 进去的字符串（从尾到头逐符号 push）
• configuration：\(C\in K\times \Sigma^*\times \Gamma^*\)，即 PDA 的状态、输入串、栈的状态
• yield in one step 形式化描述 \((p, x, \alpha)\vdash_P(q, y, \beta)\)：
  • if \(\exists \big((p, a, \gamma), (q, \eta)\big)\in\Delta\) s.t. \(x=ay, \alpha=\gamma\tau, \beta=\eta\tau\) for some \(\tau\in\Gamma^*\)
  • yield 同样即通过 0 步或更多步到达
• PDA 接受字符串：\(P\) accepts \(w\in\Sigma^*\) if \((s, w, e)\vdash_P^*(q, e, e)\) for some \(q\in F\)
  • 起始状态是空栈，结束状态要求也是空栈，其他和 NFA 相同
• PDA 接受语言：\(P\) accepts \(L(P) = \{w\in\Sigma^*: P\text{ accepts }w\}\)

Simple PDA¶

定义一个更简单的 PDA 形式用于方便后续证明。

A PDA \(P=(K, \Sigma, \Gamma, \Delta, s, F)\) is simple, if:

1. \(|F| = 1\)：只有一个接受状态
2. for each transition \(\big((p, a, \alpha), (q, \beta)\big)\in\Delta\), either
   • \(\alpha=e\) and \(|\beta|=1\) or
   • \(|\alpha|=1\) and \(\beta=e\)
   • （就是要么 pop 一个字符，要么 push 一个字符）

PDA 与 CFG 等价 ¶

分两个部分证明：

CFG -> PDA¶

对任意 CFG \(G\)，存在 PDA \(M\) 使得 \(L(M)=L(G)\)，证明思路：

• 在栈中从 \(S\) 开始非确定性地进行字符串的生成
• 将生成的内容和输入比较
• 如果匹配则接受

Given \(G=(V, \Sigma, S, R)\Rightarrow P=(K, \Sigma, \Gamma, \Delta, s, F)\), s.t. \(L(P)=L(G)\):

• \(K=\{s, f\},\ s=s,\ F=\{f\},\ \Gamma = V\)
• \(\Delta\) 由以下部分组成：
  • \(\big((s, e, e), (f, S)\big)\)：起始先 push 进 \(S\)
  • \(\big((f, a, a), (f, e)\big),\forall a\in\Sigma\)：匹配到输入串则 pop
  • \(\big((f, e, A), (f, u)\big),\forall (A, u)\in R\)：对于所有规则进行生成，非确定自动机会“猜测”

PDA -> CFG¶

前面证明了任意 PDA -> simple PDA，所以只需要证明 simple PDA -> CFG 即可。

Given \(P=(K, \Sigma, \Gamma, \Delta, s, F)\) is simple \(\Rightarrow G=(V, \Sigma, S, R)\), s.t. \(L(P)=L(G)\):

• 设立一系列非终结符号：\(\{A_{pq}: (p, q)\in K\times K\}\)，表示从状态 \(p\) 到状态 \(q\) 的路径
  • 设立的目标：\(A_{pq}\Rightarrow^* w\in\Sigma^*\) iff \((p, w, e)\vdash_P^*(q, e, e)\)
• 起始符号：\(S=A_{sf}\)
  • 因为 \(s\in L(P)\) iff \((s, w, e)\vdash_P^*(f, e, e)\)
• 转移关系 \(R\)
  • \(\forall p\in K\)，\(A_{pp}\to e\)
  • \(\forall p, q, r\in K\)，有以下两种情况：
    • 如果在从 \(p\) 转移到 \(q\) 的过程中出现了一个时刻在状态 \(r\) 且栈是空的
      • \(A_{pq}\to A_{pr}A_{rq}, \forall r\in K\)
    • 如果过程中没有出现过任何一次栈为空的情况
      • 注意到第一步和最后一步有对应关系，假设第一步读取 \(a\) 并 push \(\alpha\)，最后一步读取 \(b\) 并 pop \(\alpha\)，所以可以添加以下转移：
      • \(A_{pq}\to aA_{p'q'}b, \forall\big((p, a, e), (p', \alpha)\big), \big((q', b, \alpha), (q, e)\big)\in\Delta\text{ for some }\alpha\in\Gamma\)

这样就出现了一个类似 DP 的情况，可以证明 \(A_{pq}\Rightarrow^* w\in\Sigma^*\) iff \((p, w, e)\vdash_P^*(q, e, e)\)：

• 左推右：by induction on length of derivation from \(A_{pq}\) to \(w\)
• 右推左：by induction on number of steps of computation

CFL 性质 ¶

Closure Properties¶

PDA 可以定义一个 CFL，所以根据 PDA 的结构，CFL 有以下性质：

如果 \(A\) 和 \(B\) 是 CFL，则 \(A\cup B, A\circ B, A^*\) 也是 CFL，但 \(A\cap B, \overline{A}\) 不一定是 CFL。简单证明：设 \(G_A=(V_A,\Sigma,S_A,R_A), G_B=(V_B,\Sigma,S_B,R_B)\)，则：

• \(G_{A\cup B}\)：规则 \(S\to S_A\ |\ S_B\)
• \(G_{A\circ B}\)：规则 \(S\to S_AS_B\)
• \(G_{A^*}\)：规则 \(S\to e\ |\ SS_A\)

针对 \(\cap, \overline{A}\)，可以构造反例：

• \(A=\{a^ib^jc^k:i=j\}, B=\{a^ib^jc^k:j=k\}\) 都是 context-free 的
• \(A\cap B = \{a^nb^nc^n:n\geq 0\}\) 不是 context-free 的（后面会通过 pumping theorem 证明）
• \(A\cap B = \overline{\overline{A}\cup\overline{B}}\)，所以 \(\cap\) 不封闭则 \(\overline{A}\) 也不封闭

Pumping Theorem for CFL¶

类似正则语言的 pumping theorem，CFL 也有一个相似的定理：

• 令 \(L\) 为一个 CFL
• 则存在一个整数 \(p\geq 1\)（称为 pumping length）
• 使得对于所有长度不小于 \(p\) 的字符串 \(w\in L\)
• 都可以将 \(w\) 分解为五个部分 \(w=uvxyz\) 满足：
  1. 对于任意 \(i\geq 0\)，有 \(uv^ixy^iz\in L\)
  2. \(|v| + |y| > 0\)
  3. \(|vxy| \leq p\)

证明思路：非终结符号一共有 \(V-\Sigma\) 是有限的，但生成的字符串可以是无限长的，所以生成过程产生的 parse tree 中一定会有重复的非终结符 \(Q\)，简单画成如下：

即一层一层从上到下生成，最终推导生成 \(uvxyz\)，可见一定有以下结论：

• \(S\Rightarrow^* uQz,\ Q\Rightarrow^* vQy,\ Q\Rightarrow^* x\)
• 因此有 \(uv^ixy^iz\in L\)