> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# 正则语言的泵引理
- URL: https://blog.hacking.pub/2017/06/02/beng-yin-li/
- Published: 2017-06-02T18:15:09.000Z
- Updated: 2019-08-02T07:41:52.000Z
- Author: chainhelen
- Tags: 正则表达式, 正则表达, pumping lemma, 泵引理, 泵定理, 正则语言

#### 用法

泵定理(pumping lemma):判断一个语言不是正则语言，通常使用反证法（泵引理是RL语言的必要条件）

#### 原理

设\\( L \\) 是一个RL，则存在仅依赖于\\( L \\)的正整数\\( P \\)  
对于\\( \\forall w \\in L \\)， 如果\\( |w| \\ge P \\)，则存在\\( x, y, z \\in \\Sigma^{\*} \\) 满足\\( w = xyz \\)，同时有:  
(1) \\( |xy| \\le P \\)  
(2) \\( |y| \\ge 1\\)  
(3) \\( \\forall i \\in N{0}，xy{i}z \\in L\\)

上叙是自然语言，用`正式表达式 (formal expression)`如下

$$\\begin{align}  
(\\forall L & \\subseteq \\Sigma^{\*}) \\\\  
& (regular(L) \\Rightarrow \\\\  
& ((\\exists P \\ge 1)((\\forall w \\in L)((|w| \\ge P) \\Rightarrow \\\\  
& ((\\exists x, y, z \\in \\Sigma^{\*})(w = xyz \\land (|xy| \\le P \\land |y| \\ge 1 \\land (\\forall i \\in N{0})(xy{i}z \\in L))))))))  
\\end{align}$$

#### 图形结合

![泵引理.png](https://blog.hacking.pub/qiniu/%E6%AD%A3%E5%88%99%E8%AF%AD%E8%A8%80%E7%9A%84%E6%B3%B5%E5%BC%95%E7%90%86/%E6%B3%B5%E5%BC%95%E7%90%86.png)

所以对于y这个字符串来说，无论中间重复多少遍，都是会回到红色的状态中  
其中P可以取值 = `最小DFA状态数`

#### 证明

试证明上下文无关文法\\(L = \\{0{n}1{n} | n \\ge 1\\} \\)不是RL

> 反证法：设\\(L = \\{0{n}1{n} | n \\ge 1\\} \\)是RL，则\\( L \\)满足泵引理. 不妨设 \\( P \\)是仅依赖于 \\( L \\)的正整数  
> 取语句\\( w = 0{P}1{P}\\)，由\\( L \\)的定义可知 \\( w \\in L\\).  
> 此时\\( |w| = 2P \\ge P \\)，由定理结论  
> (1) \\( |xy| \\le P\\)  
> (2) \\( |y| \\ge 1\\)  
> 可知 \\( x、y \\)一定是形如 \\(x = 0^g(g \\ge 1) , y = 0^h(h \\ge 1)\\)  
> 那么倒推出 \\(z = 0{P-g-h}1P \\)  
> 取定理结论(3)中变量\\(i = 2\\)，则\\( xy^2z = 0^g (0h)2 0{P-g-h}1P = 0{P+h}1P \\notin L\\)，不满足定理结论(3)，得出矛盾  
> 假设不成立，得证

`实际上，正则语言不具有计数性.`  
`例如编译原理中，利用正则表达式（DFA、NFA）做完词法分析，需要引入更强的语法 上下文无关文法 去做语法分析`

---

[附件下载](http://imgqi.hacking.pub/%E6%AD%A3%E5%88%99%E8%AF%AD%E8%A8%80%E7%9A%84%E6%B3%B5%E5%BC%95%E7%90%86/%E6%B3%B5%E5%BC%95%E7%90%86.vsdx?ref=blog.hacking.pub)