Context-Free Language

只对 3 进行证明。\(w\in L(G)\Rightarrow w\in L\) 是简单的，从 \(R\) 可以看出每一步生成的 \(a, b\) 等量。也可以选用数学归纳，归纳时只需要第一步自己走就行。

\(w\in L \Rightarrow w\in L(G)\) 还是归纳比较方便。

Basis step: \(|w|=0\)，则 \(w=e\)，\(S\to e\) 直接得到 \(w\in L(G)\)

Induction hypothesis (IH): 对 \(|w|\leqslant k\) 都成立，\(k\) 是偶数。（\(w\in L\) 可以得到 \(|w|\) 是偶数）

Induction step: \(|w|\) 是偶数，所以考虑 \(|w|=k+2\)。有

\((1)w=axa\), \((2)w=axb\), \((3)w=bxa\), \((4)w=bxb\), \(|x|=k\)。

根据 IH，(2)(3) 可以直接得到 \(x\in L(G)\)，那么可以通过 \(S\Rightarrow_G aSb(bSa)\Rightarrow_G^* axb(bxa)\) 证明 \(w\in L(G)\)。

对 (1)，\(x\) 中 \(b\) 比 \(a\) 多 2 个，分解 \(x=uv\)，\(u, v\) 中都是 \(b\) 比 \(a\) 多 1 个 ( 则 \(|u|, |v|\geqslant 1\Rightarrow |u|, |v|\leqslant k-1\))。则有 \(S\Rightarrow_G^* au, S\Rightarrow_G^* va\)，故 \(S\Rightarrow_G SS\Rightarrow_G^* auva=w\)。(4) 同理。

简单地，就是 ( 当前状态 ) \(\to\) ( 输入字符 )( 下一状态 )，把输入字符一个个搬到左边。正式写出来就是 CFG \(G=(V, \Sigma, R, S)\)

1. 如下图
   
2. 将上题 \(\Sigma\) 中 \(c\) 删去，\(\Delta\) 中第三条改为 \(((s, e, e), (f, e))\) 即可
3. 利用下一节的 CFG \(\to\) PDA 的方法，可以这么构造
   
   然而直接构造可以这样
   
   这里的 \(c\) 充当栈底符的作用，即说明已经读到了栈底。由于读到 \(e\) 并不能说明已经到栈底了（即使栈里还有很多也可以读 \(e\)），所以这个栈底符是必要的。

整体逻辑很清晰：第一步放入栈底符，然后不断读，过量的存入栈，读入和栈顶 ( 非 \(c\)) 不同的可以相消。这样，\(c\) 上方就只能都是 \(a\) 或都是 \(b\)。直到 \(c\) 出现在栈顶时就可以进入终结状态，当然也可以继续读输入。

给出一个 claim：\(\forall w\in\Sigma^*\), \(\alpha\in (V-\Sigma)V^*\cup\{e\}\),

如果该 claim 成立，则取 \(\alpha=e\)，左侧就等价于 \(w\in L(G)\)，右侧就等价于 \(w\in L(M)\)，从而得证。于是下证该 claim。

(1) 正推基于最左推导的步数进行数学归纳。

Basis step: 推导长度为 0，\(w=e\)，\(\alpha=S\)，显然有 \((q, w, S)\vdash_M^*(q, e, \alpha)\) ( 一步都没有 )

Induction hypothesis: 对 \(n\geqslant 0\) 步以内的最左推导都成立

Induction step: 设 \(n+1\) 步的最左推导如下

设 \(u_n=xA\beta\)，其中 \(A\) 是 \(u_n\) 中最左的非终结符。再设第 \(n+1\) 步最左推导使用的是 \(R\) 中的 \(A\to \gamma\) 规则，则 \(u_{n+1}=x\gamma\beta\)。以上有 \(x\in\Sigma^*, \beta, \gamma\in V^*\)。

对 \(S\stackrel{L}{\Rightarrow}^* u_n\) 利用 IH，可知有 \((q, x, S)\vdash_M^*(q, e, A\beta)\)。利用 \(A\to \gamma\) 有

根据 \(u_{n+1}=w\alpha=x\gamma\beta\) 有 \(\exists\; y\in \Sigma^*\) s.t. \(w=xy, y\alpha=\gamma\beta\) (\(w\) 是左侧最长连续的 \(\Sigma^*\)，所以 \(x\) 一定是其前缀 )。这样就有

\(y\) 的消除利用了所构造的 \(M\) 的第三阶段规则，故完成了正推。

(2) 反推基于第二阶段 PDA 转移的次数进行数学归纳。

设 CFG \(G_1=(V_1, \Sigma_1, R_1, S_1), G_2=(V_2, \Sigma_2, R_2, S_2)\)。调整编码保证 \((V_1-\Sigma_1)\cap (V_2-\Sigma_2)=\emptyset\)，得到 \(G=(V, \Sigma, R, S)\)。具体构造方法类似正则表达式运算构造 FA，如下所示：

• 并：\(V=V_1 \cup V_2 \cup \{S\}\), \(\Sigma=\Sigma_1 + \Sigma_2\)

• 连接：\(V=V_1 \cup V_2 \cup \{S\}\), \(\Sigma=\Sigma_1 + \Sigma_2\)

• Kleene Star：\(V=V_1 \cup \{S\}\), \(\Sigma=\Sigma_1\)

并行模拟。PDA \(M_1=(K_1, \Sigma, \Gamma_1, \Delta_1, s_1, F_1)\), DFA \(M_2 = (K_2, \Sigma, \delta, s_2, F_2)\)，构造 PDA \(M=(K, \Sigma, \Gamma, \Delta, s, F)\):

设 \(\Sigma=\{a, b\}\)。

\(L_1=\{w\in\Sigma^*:\; w\) 中 \(a, b\) 等量 } 是 CFL，

而 \(L_2=\Sigma^*-\Sigma^*(abaa\cup babb)\Sigma^*\) 是正则语言。所以 \(L=L_1\cap L_2\) 是 CFL 。

\(|w|>\phi(G)^{|V-\Sigma|}\)，根据 Lemma 可知语法树高度 \(>|V-\Sigma|\)，所以存在一条至少长 \(|V-\Sigma|+1\) 的路径，上面有 \(|V-\Sigma|+2\) 个结点。这 \(|V-\Sigma|+2\) 个结点中，只有叶节点是终结符，根据鸽巢原理，剩下 \(|V-\Sigma|+1\) 个结点中至少两个结点相同。语法树分割如下：

显然可看出重复 \(v, y\) 依然属于 \(L(G)\)。如果预先要求语法树是生成 \(w\) 的叶子最少的语法树（因为叶子是 \(e\) 的话不影响结果），那么若 \(vy=e\)，删去其相关部分之后依然能生成 \(w\)，但是叶子更少，就不行了。由此就可以证明 \(|vy|\geqslant 1\)。

\(L_1=\{a^nb^n:\;n\geqslant 0\}c^*, L_2=a^*\{b^nc^n:\; n\geqslant 0\}\)，则 \(L_1\cap L_2\) 非 CFL。

对于补，考虑 \(L_1\cap L_2=\overline{\overline{L_1}\cup \overline{L_2}}\) 即可。

需要解决 \(R\) 中以下三种规则：

• 长规则 : \(A \rightarrow \alpha\), \(|\alpha|>2\)
• \(e\)- 规则 : \(A \rightarrow e\)
• 短规则 : \(A \rightarrow a\) 或 \(A \rightarrow B\)

分别进行处理：

• 切断长规则 \(A\to B_1B_2\cdots B_n\in R, n\geqslant 3\)。得到 \(n-1\) 条规则：

• 除去 \(e\)- 规则，定义 \(\mathcal{E}=\{A\in V-\Sigma:\; A\Rightarrow ^* e\}\)，即能导出 \(e\) 的非终结符集合

1
2
3

E := emptyset
while there is A->a in R, a in E^*, A not in E:
    add A to E

其实算法和计算 NFA 转 DFA 的 \(E(p)\) 是一样的。计算完 \(\mathcal{E}\) 之后，对推导得到 \(\mathcal{E}\) 中元素的规则需要进行替换，如下所示：

1
2
3

D(A) := {A}
while there is B->C in R, B in D(A), C not in D(A):
    add C to E

注意总有 \(A\in \mathcal{D}(A)\)，若 \(a\in \Sigma\)，则 \(\mathcal{D}(a)=\{a\}\)。

接下来的操作 PPT 上不够全面，采纳课本的说法。

先计算全部 \(\mathcal{D}(A)\)，再删去所有短规则。然后剩下的就都是 \(A\to BC\) 规则了，全部替换为 \(A\to B'C'\) 规则，其中 \(B'\in \mathcal{D}(B), C'\in \mathcal{D}(C)\)。这里就模拟了 \(B\) 产生 \(B'\) 以及 \(C\) 产生 \(C'\) 的一系列短规则的效果。

最后还有一条特殊的，回过头再看每一条 \(A\to BC\)，如果 \(A\in \mathcal{D}(S)-\{S\}\)，就添加规则 \(S\to BC\)。