pumping lemma

正规语言版本

$L$是正规语言,则存在整数$p\ge 1$
对于任意长度大于等于$p$的字符串$w\in L$，存在一种分解$w=xyz$,满足下面3个条件
$\left|y\right|\ge 1$
$\left|xy\right|\le p$
$\forall n\ge 0,x{y}^{n}z\in L$

即
( ∀ L ⊆ Σ ∗ ) (  regular  ( L ) ⇒ ( ( ∃ p ≥ 1 ) ( ( ∀ w ∈ L ) ( ( ∣ w ∣ ≥ p ) ⇒ ( ( ∃ x , y , z ∈ Σ ∗ ) ( w = x y z ∧ ( ∣ y ∣ ≥ 1 ∧ ∣ x y ∣ ≤ p ∧ ( ∀ n ≥ 0 ) ( x y n z ∈ L ) ) ) ) ) ) ) )

​(∀L⊆Σ∗)( regular (L)⇒((∃p≥1)((∀w∈L)((∣w∣≥p)⇒((∃x,y,z∈Σ∗)(w=xyz∧(∣y∣≥1∧∣xy∣≤p∧(∀n≥0)(xynz∈L))))))))​

证明：
根据Myhill–Nerode theorem，正则语言可以转为有限自动机
设这个有限自动机由$p$个状态

对于一个长度大于等于$p$字符串$w$，进入自动机需要经过$p+1$个状态
根据抽屉原理，至少有一个状态被访问两遍，如图

$\left|y\right|\ge 1$，因为要有环
$\left|xy\right|\le p$,（因为还没走完？
显然$x{y}^{i}z\in L$

举个例子，比如 L = { 0 n 1 n ∣ n > 0 } L=\left\{0^n1^n|n>0\right\} L={0n1n∣n>0}不是正则语言
$w=0^p{1}^p$
因为$\left|xy\right|\le p$,所以$y\in 0^{\ast }$
令$x=0^{p-m},y=0^m,z=1^p\left(m\ge 1\right)$
于是$w=xyz=0^{p-m}{1}^m{1}^p$
而$x{y}^{0}z=xz=0^{p-m}{1}^p\notin L$

另一个例子： L = { a b c d } L=\left\{abcd\right\} L={abcd}
取$p=5$,因为没有$\left|w\right|\ge 5$,所以成立

反过来不一定成立：
L = { a b n c n ∣ n ≥ 1 } ∪ { a k ( b ∣ c ) ∗ ∣ k ≠ 1 } L=\left\{ab^nc^n|n\ge1\right\}\cup\left\{a^k(b|c)^*|k\neq 1\right\} L={abncn∣n≥1}∪{ak(b∣c)∗∣k​=1}
选定$p=2$
对于$w=a{b}^n{c}^n$,选择$x=ϵ,y=a,z=b^n{c}^n$
对于$w={\left(b|c\right)}^{\ast }$,选择$x=ϵ$,$y$选择第一个/前两个字符，$z$选择剩下的
对于$w=a^k{\left(b|c\right)}^{\ast }k\ge 2$,选定$x=ϵ,y=aa$,$z$选择剩下的
即可满足pumping lemma

但是显然 { a b n c n ∣ n ≥ 1 } ∩ { a k ( b ∣ c ) ∗ ∣ k ≠ 1 } = ∅ \left\{ab^nc^n|n\ge1\right\}\cap\left\{a^k(b|c)^*|k\neq 1\right\}=\empty {abncn∣n≥1}∩{ak(b∣c)∗∣k​=1}=∅，
并且 { a b n c n ∣ n ≥ 1 } \left\{ab^nc^n|n\ge1\right\} {abncn∣n≥1}不是正则语言，所以$L$不是正则语言

https://cs.stackexchange.com/questions/9181/languages-that-satisfy-the-pumping-lemma-but-arent-regular