CFG

在一个语言 A 中构建一个足够长的字符串 s，那么 s 就可以通过 A 对应的语法 G 来 parse 成一个 parse tree。所谓足够长的意思是，这个 parse tree 上会有一些足够长的从树根到叶的路径，根据鸽笼原理，这个路径上某些 non-terminal symbol，比如 N 会出现不止一次。你把子节点上的一个 N 替换成一个根节点上同构的 N，就相当于把字符串中间的某些部分重复了，这样 pumping 出来的新字符串依然符合其语法，也即依然在语言 A 中。

即，若 v 由完成 n 次入栈循环的路径标记，y 由完成 m 次出栈循环的路径标记，那么由于 m 次出栈循环刚好可以将 n 次入栈循环入栈的符号出栈，则类似的断言对 mi 及 ni 也成立。因此 v 与 w 可重复相同多的次数而所得到的字符串依旧在 A 中。

证明语言 $L = {a^i b^i c^i|i\geq 0}$ 不是上下文无关的.

Proof.

假设 L 是CFL，设 L 的泵长度为 p。根据泵引理，这个p一定存在。

取字符串 $s = a^p b^p c^p$，显然有：

• $|s| \geq p$

• s 属于 L

泵引理称s能够被抽取，但是我们证明这是不可能的，也就是要证明不管怎么把s划分成uvxyz，总要违反泵引理中的一个条件。

P108

https://blog.csdn.net/shulianghan/article/details/110631657