正则语言的泵引理

用法

泵定理(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}$$

图形结合

所以对于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}1^P$
取定理结论(3)中变量$i = 2$，则$xy^2z = 0^g (0^h)^2 0^{P-g-h}1^P = 0^{P+h}1^P \notin L$，不满足定理结论(3)，得出矛盾
假设不成立，得证

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

附件下载