正规语言版本

$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$

即
$$\begin{array}{rl}& \left(\forall L\subseteq {\Sigma }^{\ast }\right)\\ & (\text{ regular }(L)\Rightarrow \\ & ((\exists p\ge 1)((\forall w\in L)((|w|\ge p)\Rightarrow \\ & \left(\left(\exists x,y,z\in {\Sigma }^{\ast }\right)\left(w=xyz\wedge \left(|y|\ge 1\wedge |xy|\le p\wedge (\forall n\ge 0)\left(x{y}^{n}z\in L\right)\right)\right)\right)))))\end{array}$$

证明：
根据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