江苏龙网

  1. 首页 > 生活 > >

咋直观地理解上下文无关语言的泵引理?

Pumping Lemma for CFL 简单来讲，对于一个符合某 CFL 的字符串，你可以按照规则重复（"pump"）其中的若干部分，得到的新字符串依然属于这个 CFL。Pumping Lemma 一般用于反证某种语言不是 RL 或 CFL，所以一般用作 Lemma 而非 Theorem。
Sipser 2.3 里介绍了 Pumping Lemma for CFL 的证明，其思路如下：
在一个语言 A 中构建一个足够长的字符串 s，那么 s 就可以通过 A 对应的语法 G 来 parse 成一个 parse tree。所谓足够长的意思是，这个 parse tree 上会有一些足够长的从树根到叶的路径，根据鸽笼原理，这个路径上某些 non-terminal symbol，比如 N 会出现不止一次。你把子节点上的一个 N 替换成一个根节点上同构的 N，就相当于把字符串中间的某些部分重复了，这样 pumping 出来的新字符串依然符合其语法，也即依然在语言 A 中。这就对应了维基的配图（Sipser 中的配图也差不多）：
咋直观地理解上下文无关语言的泵引理?

https://en.wikipedia.org/wiki/File:Pumping_lemma_for_context-free_languages.svgPumping Lemma for CFL 把字符串分为五部分，是因为头尾 uy 和中间 w 是不动点（当然它们是可空的），而一个 CFL 的替换规则可以是形如
A → aAb的形式，其中大写字母是 non-terminal，小写字母是 terminal。一个 parse tree 上的一个节点按照这样的规则展开自己的时候，会同时在前后添加给定的片段（其一可以为空，但不能同时为空），所以在 lemma 的表述中 v 和 x 重复的次数是相同的。图中的例子，A 就是图中的 N，a 就是 v，b 就是 x，你同时重复 v 和 x，就是在 parse tree 上不断替换 N 下面的结构。
怎么用？一般的做法是，给你一个语法，你穷举所有把这个语法拆成 vwx 的模式（虽然比 Pumping Lemma for RL 的模式多，但其实也没多少），然后证明所有这些拆法都不行，所以这个语言不是 CFL。例子有很多，比方这个。

■网友
我学的这个“CF的泵引理”是叫做uvwxy定理，然后才知道一般说的正则泵引理是uvwxy定理的特化，或者说uvwxy定理是正则泵引理的推广。
结合最近的梗，uvwxy定理其实是在禁止套娃。
套娃是什么意思呢，假设我们有这个简单的CF语法：
S → AA → aA | b不聪明的小朋友也可以看出，通过A的套娃，我们可以产生形如aaa.....aaaab这样的字符串。禁止套娃指的就是一条规则只能用一次，也就把我们能产生的字符串限定在了 {b, ab} 这个小小的集合内。
我们直觉上容易看出，如果禁止套娃，那么一个CF语法生成的字符串长度是有上限的。毕竟生成规则的个数是有限的，在用过了所有规则以后，只有套娃才能让字符串在纸上无限延申。所以团长，不要停下来啊（划掉
既然禁止套娃能生成的字符串长度是有限的，不如把最长的非套娃字符串的长度表示为L，例如上例中L=2。uvwxy定理说：所有长度大于L的字符串（他们自然全都是套娃字符串了）都可以被分解为uvwxy五个部分，其中u和y是无关紧要的前后缀，而vwx是一个套娃：v和x是套子，w是娃。
vwx是套娃是什么意思呢，意思是形如uvwxy，uv(vwx)xy，uv(v(vwx)x)xy，uv(v(v(vwx)x)x)xy这样的套娃全都可以通过这个语法生成。这些套娃的通式是 【咋直观地理解上下文无关语言的泵引理?】 咋直观地理解上下文无关语言的泵引理?
。可以看出w是中心的那个最小的娃，它两旁的一层又一层的v..x组成了一层又一层的套娃。
证明请看另一个回答。
那么怎么把它收敛到我们一般说的正则泵引理（uvw定理）呢？我们注意到对于正则语法，x和y必须是空的（等于 咋直观地理解上下文无关语言的泵引理?


推荐阅读


上一篇：近期、中期、长期未来的世界发展潜力在哪里

下一篇：lol版本更新为啥总会比外服慢