跳转至

3 Context-free Language and Pushdown Automata

3.1 Context-Free Grammars

A Context-Free Grammar (CFG) is a 4-tuple

\[ G = (V, \Sigma, R, S) \]

where:

  • \(V\) is an alphabet (a finite set of symbols), called the vocabulary or set of variables. 字母表
  • \(\Sigma \subseteq V\) is the set of terminal symbols (the actual characters in the language). 终止符号
  • \(S \in V - \Sigma\) is the start symbol (a special non-terminal from which derivation begins). 起始符号
  • \(R\) is the set of production rules, a finite subset of \((V - \Sigma) \times V^*\).

比如说 \(L = \{a^nb^n|n\ge 0\}, S\rightarrow aSb,S\rightarrow e\)

注意这里左边只能是单个非终结符，与下一章的 Grammar 做区分

接下来我们证明所有的正则语言都是 CFL，这里就选择直接构造。对于一个正则语言，其被一个 DFA \(M = (K,\Sigma,\delta,s,F)\)接受。那么我们可以构造如下一个 CFG \(G = (V,\Sigma,R,S)\)，

  • 对于每个状态 \(q∈K\) 和每个字符 \(a∈Σ\)，如果 DFA 中有转移：\(δ(q,a)=p\)，那么在 CFG 中添加规则：\(q→ap\)
  • 对于每个接受状态 \(q∈F\)，添加规则：\(q→ε\)

然后我们需要考虑的是如何证明某个语言是 CFL，只需要构造一个 CFG，并说明这两者等价即可

Example

3.2 Parse Tree

A derivation of a CFG \(𝐺 = (𝑆, 𝑉, 𝛴, 𝑅)\) , can be represented with a parse tree

  • Leaves: terminal symbols
  • Root: Start Symbol
  • Node: element in \(V\)

我们也可以发现由同一个 CFG 生成出来的相同的字符串，它们的 parse tree 也可能不一样

Definition: Similarity of derivations

Let \(G = (V, \Sigma, R, S)\) be a CFG.

Let \(D = x_1 \Rightarrow x_2 \Rightarrow x_3 \Rightarrow \cdots \Rightarrow x_n\), where \(x_i \in V^*\), \(x_1 \in V - \Sigma\), \(x_n \in \Sigma^*\)

Let \(D' = x'_1 \Rightarrow x'_2 \Rightarrow x'_3 \Rightarrow \cdots \Rightarrow x'_n\), where \(x'_i \in V^*\), \(x'_1 \in V - \Sigma\), \(x'_n \in \Sigma^*\)

\(D\) precedes \(D'\) (\(D < D'\)) \(\Leftrightarrow \exists 1 \leq k \leq n \text{ such that}\)

  • For all \(i \neq k\), we have \(x_i = x'_i\)
  • \(x_{k-1} = x'_{k-1} = uAvBw\), where \(u, v, w \in V^*\), and \(A, B \in V - \Sigma\)
  • \(x_k = uyvBw\), where \(A \to y \in R\)
  • \(x'_k = uAvzw\), where \(B \to z \in R\)
  • \(x_{k+1} = x'_{k+1} = uyvzw\)

\(D\) and \(D'\) are similar \(\Leftrightarrow(D, D') \text{ belong to the reflexive, symmetric, transitive closure of } <\)

用 parse tree 的视角去理解这个相似性的定义，precede 就是交换子树，相似性就是两棵树可以通过交换子树的操作变得一样

Note

相似性是一种等价关系 （Similarity is an equivalence relation）

每个语法树都包含一个在 < 关系下是极大或极小的推导
（Each parse tree contains a derivation that is maximal or minimal under <）

  • 最左推导（类似地，最右推导）
    （Leftmost derivation (similarly, right most derivation)）

  • 最左推导是指：每次总是对最左边的非终结符应用产生式规则
    （A leftmost derivation is a derivation in which a production is always applied to the leftmost symbol）

Theorem: Let \(G = (V, \Sigma, R, S)\) be a CFG, and let \(A \in V - \Sigma\), and \(w \in \Sigma^*\). Then the following statements are equivalent:

  • \(A \Rightarrow^* w\)
  • \(\exists\) a parse tree with root \(A\) and yield \(w\)
  • \(\exists\) a leftmost derivation \(A \overset{L^*}{\Longrightarrow} w\)
  • \(\exists\) a rightmost derivation \(A \overset{R^*}{\Longrightarrow}w\)

也即是说只有存在一条路径可以推导出来，那么就存在最右推导和最左推导。

Note

下面的论述是错误的

  • A string cannot have multiple left and rightmost derivations 【错，一个字符串可以有多个最右推导和最左推导】
  • Let \(D = x_1 \Rightarrow x_2 \Rightarrow x_3 \Rightarrow \cdots \Rightarrow x_n\), where \(x_i \in V^*\), \(x_1 \in V - \Sigma\), and \(x_n \in \Sigma^*\). Let \(D' = x'_1 \Rightarrow x'_2 \Rightarrow x'_3 \Rightarrow \cdots \Rightarrow x'_n\). If \(x_1 = x'_1\) and \(x_n = x'_n\), then \(D\) and \(D'\) must be similar. 【只有初始和末尾相同，并不能说明是相似的】

Definition: A grammar in which some words has two parse trees is said to be ambiguous.

3.3 Pushdown Automata

Pushdown Automata 可以被认为是 FA 加了一个栈，也就是多了一个记忆的功能，使得其功能变得更加强大。每次 PDA 读取磁带上的输入，还要读入栈中的信息。最后当状态是最终状态且磁带读完栈为空时，接受该字符串。

形式化定义 PDA：一个 PDA 是一个六元组：

\[ P = (K, \Sigma, \Gamma, \Delta, s, F) \]

其中各部分含义如下：

  • \(K\)：有限状态集合（states）
  • \(\Sigma\)：输入字母表（input alphabet）
  • \(\Gamma\)：栈字母表（stack alphabet），即栈中可能出现的符号集合
  • \(s \in K\)：初始状态（start state）
  • \(F \subseteq K\)：接受状态集合（final/accepting states）
  • \(\Delta\)：转移关系（transition relation），是一个有限子集：
\[ \Delta \subseteq (K \times (\Sigma \cup \{e\}) \times \Gamma^*) \times (K \times \Gamma^*) \]

每一个 FA 都可以平凡地被看做为一个不对栈进行任何操作的 PDA。

在 PDA 中，同一个状态、输入符号和栈顶符号组合，可能对应多个不同的转移规则。这意味着在某一步，机器可以选择执行其中任意一个规则。因此，这种 PDA 是非确定性的（Nondeterministic PDA, NPDA）。

\((p, x, \alpha) \vdash_M (q, y, \zeta)\) (yield in one step) iff there is some transition \(((p, a, \beta), (q, \gamma)) \in \Delta\) such that

  • \(x = ay\), \(a \in \Sigma \cup \{e\}\)
  • \(\alpha = \beta\eta\)
  • \(\zeta = \gamma\eta\) for some \(\eta \in \Gamma^*\)

Let \(\vdash_M^*\) be the reflexive, transitive closure of \(\vdash_M\).

那么也就是说 PDA \(M\) 所接受的语言就是

\[ L(M) = \{w \mid (s, w, e) \vdash_M^* (p, e, e) \text{ for some state } p \in F\}. \]

Example

实际上由 PDA 所接受的语言就是 CFL，证明思路还是正反两面

  • Each context-free language is accepted by some PDA.
  • If a language is accepted by a PDA, it is a context-free language.

如何对于任意一个 CFL，构造出相应的 PDA ?

Construct a PDA \(M = (K, \Sigma, \Gamma, \Delta, s, F)\) for the CFG \(G = (V, \Sigma, R, S)\) such that \(L(M) = L(G)\)

  • PDA \(M\) has just 2 states: \(p\) ~ start state, \(q\) ~ final state
  • Stack alphabet \(\Gamma = V\)

  • Let \(\Delta\) contain the following transitions:

    • \(((p, \varepsilon, \varepsilon), (q, S))\)

    • \(((q, \varepsilon, A), (q, x))\) for each rule \(A \to x \in R\)

    • \(((q, a, a), (q, \varepsilon))\), \(\forall a \in \Sigma\)

整体思路就是先把初始符号 \(S\) 放到栈里，磁带上放相应的字符串。然后依次从栈顶读字符，如果是非终结符，则进行替换，将替换后的字符再次塞回栈顶；如果是终结符，那么就读出。这样的 PDA 实际上模仿的就是 CFG 的最左推导。

我们要证明 PDA 的操作过程就是 CFG 的最左推导，其实要说明以下式子

\[ S \overset{L^*}{\Longrightarrow} w\alpha \iff (q, w, S) \vdash_M^* (q, \varepsilon, \alpha) \]

其中 \(w \in \Sigma^*\) 然后 \(\alpha \in (V - \Sigma)V^* \cup \{\varepsilon\}\). 用人话讲就是 \(w\) 是已经处理好的终结符号，\(\alpha\) 是以未终结符开头的字符串。然后 \(\overset{L^*}{\Longrightarrow}\) 的意思是最左推导。如果有上述式子成立，我们就可以说明每个 CFL 都可以被一个 PDA 所接受【取 \(\alpha\) 为 \(\varepsilon\) 即可】

这个式子的证明还是使用数学归纳法，以最左推导的次数为归纳条件。

归纳步骤

如何说明一个被 PDA 接受的语言是 CFL?

首先我们定义 simple PDA

Simple PDA

当某个转移 \(((q,a,β),(p,γ))\) 是该 PDA 的一条转移规则，且状态 \(q\) 不是起始状态时，必须满足：

  • \(β\) 是栈中的一个符号（即 \(β∈Γ\)），
  • 并且新压入栈的字符串 \(γ\) 的长度不超过 2（即 ∣γ∣≤2）。

也就是说每次只读栈顶的一个符号，然后最多压入两个符号

那么对于一个正常的 PDA 来说，实际上我们可以转化为 simple PDA

  • 读多个栈符号 \((β≥2)\)
  • 压入多个栈符号 (\(\gamma >2\))
  • 直接转化

具体替换步骤

接下来我们完成一个从 simple PDA 到 CFG 的转化过程

首先我们定义非终结符 \(⟨q,A,p⟩\)，表示： “PDA 从状态 q 开始，栈顶是符号 A，在读取一段输入后，把 A 弹出，并进入状态 p” 的过程中，可能读到的输入字符串。然后我们对原先 PDA 的一些转移关系进行转化，添加相应的规则

(1) 规则 \(S \to \langle s,Z,f' \rangle\)：--- 其中 \(s\) 是原始 PDA 的起始状态，\(f'\) 是新的最终状态。

(2) 对于每个转移 \(((q,a,B),(r,C))\)，其中 \(q,r \in K'\), \(a \in \Sigma \cup \{\varepsilon\}\), \(B,C \in \Gamma \cup \{\varepsilon\}\)，并且对于每个 \(p \in K'\)，我们添加规则 \(\langle q,B,p \rangle \to a\langle r,C,p \rangle\)。

(3) 对于每个转移 \(((q,a,B),(r,C_1C_2))\)，其中 \(q,r \in K\), \(a \in \Sigma \cup \{\varepsilon\}\), \(B \in \Gamma \cup \{\varepsilon\}\)，且 \(C_1,C_2 \in \Gamma\)，并且对于每个 \(p,p' \in K\)，我们添加规则 \(\langle q,B,p \rangle \to a\langle r,C_1,p' \rangle\langle p',C_2,p \rangle\)。

(4) 对于每个 \(q \in K\)，规则 \(\langle q,\varepsilon,q \rangle \to \varepsilon\)。

Example

要证明构造出来的 CFG 与原先的 PDA 等价，只需要证明以下引理

引理：对于任意状态 \(q, p \in K\)，栈符号 \(A \in \Gamma \cup \{\varepsilon\}\)，以及输入串 \(x \in \Sigma^*\)，有：

\[ \langle q, A, p \rangle \Rightarrow_G^* x \iff (q, x, A) \vdash_M^* (p, \varepsilon, \varepsilon) \]

另一个类似的证明

上下文无关语言 - 鹤翔万里的笔记本

在这个证明中的 simple PDA 更加简单，每次都要么弹出一个栈，要么写入一个栈。之后的证明相比这个部分更加简洁

3.4 Languages that are and are not CF

CFL 在并操作、连接操作和 Kleene Star 操作下是封闭的，这个的证明可以通过构造 PDA

但是 CFL 在交操作和补操作下并不封闭。回忆一下之前正则语言的情况，我们可以发现，我们可以使用一个 DFA 来模拟两个 DFA 的行为，但是回到 CFL 的情况，我们却不能用一个 PDA 表示两个 PDA，因为引入了栈。

Exmaple

但是 CFL 和 正则语言的交是 CFL

Note

Example

与正则语言的泵定理类似，CFL 也有类似的泵定理

设 \(G = (V, \Sigma, R, S)\) 是一个上下文无关文法（CFG）。则对于任意字符串 \(w \in L(G)\)，如果其长度大于 \(\phi(G)^{|V - \Sigma|}\)，那么 \(w\) 可以被分解为 \(w = uvxyz\)，满足以下条件：

  • \(|vy| \geq 1\)
  • 对所有 \(n \geq 0\)，都有 \(uv^nxy^nz \in L(G)\)

其中：

  • \(\phi(G)\) 是语法中产生式右边最长符号串的长度（即最大生成长度）

  • \(|V - \Sigma|\) 是非终结符的数量

该定理的核心思想是：当字符串足够长时，其推导树必然存在“重复的非终结符路径”。在 CFG 的最左推导中，若字符串长度超过某个阈值（由非终结符数量和规则长度决定），则推导树中必有一条从根到叶的路径上出现了某个非终结符 \(A\) 两次。我们可以将这个“循环”部分对应的部分字符串 \(vy\) 提取出来，通过反复“泵”它（即重复 \(v\) 和 \(y\)），得到无限多个新字符串 \(uv^nxy^nz\)，它们仍能被相同结构的推导生成。

这说明：所有足够长的 CFL 字符串都包含可“泵”的子串，从而可以用来判断一个语言是否为 CFL。

这个定理是用来证明一个语言不是 CFL 的有效利器，整个证明过程就是首先先找一个长度大于 \(\phi(G)^{|V - \Sigma|}\) 的，然后分析所有情况，拆分为 \(uvxyz\) ，然后找到一个 \(i\)，使得 \(uv^ixy^iz\) 并属于这个语言。【因为我们的拆分是存在性】

Example

Review

  1. 𝐿 = {𝑤 ∈ 𝑎, 𝑏 ∗ : 𝑤 has twice as many 𝑏’s as 𝑎’s} is context-free. 【如何构造 CFG】
Answer

True

  1. \(𝐿 = \{𝑎^𝑚𝑏^𝑛 𝑐^{𝑚+𝑛}, 𝑚, 𝑛 ≥ 0\}\) is context-free.【如何构造 CFG】
Answer

True

\(𝑉 = \{𝑆, 𝑇, 𝑎, 𝑏, 𝑐\}\)

\(\Sigma = \{𝑎, 𝑏, 𝑐\}\)

\(𝑅 = \{𝑆 → 𝑎𝑆𝑐|𝑇, 𝑇 → 𝑏𝑇𝑐|𝑒\}\)

注意 CFG 的变化规则并不是确定性的

  1. 说明 \(L = \{ab^mc^na^{m+2n}c|m,n,\in N\}\) 是 CFL
Answer

构造 \(CFG\) , \(R = \{ S \to aS_1c,\ S_1 \to bS_1a,\ S_1 \to S_2,\ S_2 \to cS_2a^2,\ S_2 \to \varepsilon \}\)

这里的构造思路，我觉得从 parse tree 的角度去构造会比较好想。

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！