参考博客 : 【计算理论】Pumping 引理 ( 四个等价概念 | 自动机界限 | Pumping 引理简介 | Pumping 引理证明正则表达式 | Pumping 引理示例分析 )

一、泵引理 ( Pumping )

正则语言 是 正则表达式 表达的语言 ;

正则表达式 是 原子字符 , 或 原子字符进行递归 并运算 $\cup$ , 串联运算 $\circ$ , 星运算 $\ast$ 形成的字符串组成的语言 ;

正则表达式 等价于 确定性有限自动机 等价于 非确定性有限自动机 ;

使用泵引理可以判定一个语言是否是正则语言 ;

泵引理 :

① 正则语言 : $\mathrm{A}$ 是正则语言 ;

② 数字 : 存在数字 $\mathrm{p}$ , 这个 $\mathrm{p}$ 叫做 泵长度 ;

③ 字符串 : $\mathrm{s}$ 是 $\mathrm{A}$ 语言中的子字符串 , 其长度大于等于 $\mathrm{p}$ ; ( 字符串两个要求 )

④ 字符串分组及要求 : 所有的子字符串 $\mathrm{s}$ 可以分为三个部分 , $\mathrm{s}=\mathrm{x}\mathrm{y}\mathrm{z}$ , 满足如下要求 :

• $\mathrm{x}{\mathrm{y}}^{\mathrm{i}}\mathrm{z}\in \mathrm{A}(\mathrm{i}\ge 0)$ : $\mathrm{i}$ 表示中间的 $\mathrm{y}$ 的重复次数 ;
• $|\mathrm{y}|>0$ : $\mathrm{y}$ 是中间重复的部分 , 星计算部分 ;
• $|\mathrm{x}\mathrm{y}|\le \mathrm{p}$

使用泵引理证明某语言是正则语言步骤 : 使用 反正法 进行证明 ;

① 提出假设 : 首先假设该语言是正则的 ;

② Pumping 引理常数提出 : 存在一个常数 $\mathrm{p}$ , 所有长度至少为 $\mathrm{p}$ 的任何字符串 , 都满足 Pumping 引理 的三个性质 ;

③ 找出矛盾 假设不成立 : 如果不满足 Pumping 引理 , 说明上面假设该语言是正则语言 是不成立的 , 该语言不是正则语言 ;

二、泵引理证明示例 1

证明 : $\{0^n{1}^n:n\ge 0\}$ 语言 不是正则语言 ;

1. 提出假设 : 假设 $\{0^n{1}^n:n\ge 0\}$ 语言 是正则语言 ;

2. 泵长度 : 存在一个泵长度 $\mathrm{p}$ , 只要是 长度至少为 $\mathrm{p}$ 的子字符串 $\mathrm{s}$ , 都 满足 Pumping 引理 的三个性质 ; $\mathrm{s}$ 字符串可以分为三个部分 , $\mathrm{s}=\mathrm{x}\mathrm{y}\mathrm{z}$ , 满足如下要求 :

• $\mathrm{x}{\mathrm{y}}^{\mathrm{i}}\mathrm{z}\in \mathrm{A}(\mathrm{i}\ge 0)$ : $\mathrm{i}$ 表示中间的 $\mathrm{y}$ 的重复次数 ;
• $|\mathrm{y}|>0$ : $\mathrm{y}$ 是中间重复的部分 , 星计算部分 ;
• $|\mathrm{x}\mathrm{y}|\le \mathrm{p}$

3. 找出矛盾 : 找出一个 长度至少为 $\mathrm{p}$ 的子字符串 $\mathrm{s}$ , 不符合泵引理要求 , 这里就出现了矛盾 , 假设不成立 ;

选择字符串 $\mathrm{s}=0^{\mathrm{p}}{1}^{\mathrm{p}}$ , 该字符串有 $\mathrm{p}$ 个 $0$ 和 $\mathrm{p}$ 个 $1$ 字符组成 ;

$y$ 出现三种情况 : $y$ 全部由 $0$ 组成 , $y$ 全部由 $1$ 组成 , $y$ 全部由 $0,1$ 组成 ;

① $y$ 全部由 $0$ 组成 情况分析 :

假设 : 假设 $y$ 全部由 $0$ 组成 , 其不停的重复 , 得到的新字符串 , 仍然属于 $A$ 语言 ;

$y$ 重复后不符合要求 : $\mathrm{i}$ 是任意值 , 但是 $0$ 重复若干次之后 , 如 重复次数$\mathrm{i}=\mathrm{p}+1$ , $0$ 的个数就大于 $1$ 的个数了 , 此时不符合 $s=0^p{1}^p$ 要求了 , 因此这种情况不成立 ;

② $y$ 全部由 $1$ 组成 情况分析 :

假设 : 假设 $y$ 全部由 $1$ 组成 , 其不停的重复 , 得到的新字符串 , 仍然属于 $A$ 语言 ;

$y$ 重复后不符合要求 : $\mathrm{i}$ 是任意值 , 但是 $1$ 重复若干次之后 , 如 重复次数$\mathrm{i}=\mathrm{p}+1$ , $1$ 的个数就大于 $0$ 的个数了 , 此时不符合 $s=0^p{1}^p$ 要求了 , 因此这种情况不成立 ;

③ $y$ 全部由 $0,1$ 组成 情况分析 :

假设 : 假设 $y$ 全部由 $0,1$ 组成 , 其不停的重复 , 得到的新字符串 , 仍然属于 $A$ 语言 ;

$y$ 重复后不符合要求 : $\mathrm{i}$ 是任意值 , 但是 $0,1$ 重复若干次之后 , 如 重复次数$\mathrm{i}=\mathrm{p}+1$ , 就会打乱 $s=0^p{1}^p$ 字符串中 $0,1$ 的相互顺序 , 其中 $0,1$ 不能存在交叉 , 因此这种情况不成立 ;

经过上述讨论 , $y$ 的三种情况都不符合 Pumping 引理 , 因此 $\{0^n{1}^n:n\ge 0\}$ 语言不是正则语言 ;

三、泵引理证明示例 2

证明 : $\{0^n{1}^n{2}^n:n\ge 0\}$ 语言 不是正则语言 ;

1. 提出假设 : 假设 $\{0^n{1}^n{2}^n:n\ge 0\}$ 语言 是正则语言 ;

2. 泵长度 : 存在一个泵长度 $\mathrm{p}$ , 只要是 长度至少为 $\mathrm{p}$ 的子字符串 $\mathrm{s}$ , 都 满足 Pumping 引理 的三个性质 ; $\mathrm{s}$ 字符串可以分为三个部分 , $\mathrm{s}=\mathrm{x}\mathrm{y}\mathrm{z}$ , 满足如下要求 :

• $\mathrm{x}{\mathrm{y}}^{\mathrm{i}}\mathrm{z}\in \mathrm{A}(\mathrm{i}\ge 0)$ : $\mathrm{i}$ 表示中间的 $\mathrm{y}$ 的重复次数 ;
• $|\mathrm{y}|>0$ : $\mathrm{y}$ 是中间重复的部分 , 星计算部分 ;
• $|\mathrm{x}\mathrm{y}|\le \mathrm{p}$

3. 找出矛盾 : 找出一个 长度至少为 $\mathrm{p}$ 的子字符串 $\mathrm{s}$ , 不符合泵引理要求 , 这里就出现了矛盾 , 假设不成立 ;

选择字符串 $\mathrm{s}=0^{\mathrm{p}}{1}^{\mathrm{p}}{2}^{\mathrm{p}}$ , 该字符串有 $\mathrm{p}$ 个 $0$ , $\mathrm{p}$ 个 $1$ , $\mathrm{p}$ 个 $2$ 字符组成 ;

$y$ 出现三种情况 : $y$ 全部由 $0$ 组成 , $y$ 全部由 $1$ 组成, $y$ 全部由 $2$ 组成 , $y$ 全部由 $0,1,2$ 组成, $y$ 全部由 $0,1$ 组成 , $y$ 全部由 $1,2$ 组成 ;

如果字符串仅有 $0,1,2$ 单个字符 , 重复任意 $\mathrm{i}$ 次后 , 不能保证三个字符数量相等 , 矛盾 ;

如果字符串由多个字符组成 , 一旦重复之后 , 次序就被打乱 , 无法保证三个字符次序 , 也是矛盾 ;

四、泵引理证明示例 3

证明 : $\{\mathrm{w}\mathrm{w}\mathrm{w}|\mathrm{w}\in \{\mathrm{a},\mathrm{b}{\}}^{\ast }\}$ 语言 不是正则语言 ;

$\{\mathrm{a},\mathrm{b}{\}}^{\ast }$ 中的星运算 $\ast$ 是 将 $\{\mathrm{a},\mathrm{b}\}$ 中的有限个字符串串联在一起 , 将若干个 $\mathrm{a}$ 与若干个 $\mathrm{b}$ 以任意先后顺序任意交错顺序进行排列 ; 即 $\mathrm{a},\mathrm{b}$ 组成的任意字符串都属于上述语言 ;

1. 提出假设 : 假设 $\{\mathrm{w}\mathrm{w}\mathrm{w}|\mathrm{w}\in \{\mathrm{a},\mathrm{b}{\}}^{\ast }\}$ 语言 是正则语言 ;

2. 泵长度 : 存在一个泵长度 $\mathrm{p}$ , 只要是 长度至少为 $\mathrm{p}$ 的子字符串 $\mathrm{s}$ , 都 满足 Pumping 引理 的三个性质 ; $\mathrm{s}$ 字符串可以分为三个部分 , $\mathrm{s}=\mathrm{x}\mathrm{y}\mathrm{z}$ , 满足如下要求 :

• $\mathrm{x}{\mathrm{y}}^{\mathrm{i}}\mathrm{z}\in \mathrm{A}(\mathrm{i}\ge 0)$ : $\mathrm{i}$ 表示中间的 $\mathrm{y}$ 的重复次数 ;
• $|\mathrm{y}|>0$ : $\mathrm{y}$ 是中间重复的部分 , 星计算部分 ;
• $|\mathrm{x}\mathrm{y}|\le \mathrm{p}$

3. 找出矛盾 : 找出一个 长度至少为 $\mathrm{p}$ 的子字符串 $\mathrm{s}$ , 不符合泵引理要求 , 这里就出现了矛盾 , 假设不成立 ;

选择字符串 $\mathrm{s}={\mathrm{a}}^{\mathrm{p}}{\mathrm{b}}^{\mathrm{p}}$ , 该字符串有 $\mathrm{p}$ 个 $\mathrm{a}$ , $\mathrm{p}$ 个 $\mathrm{b}$ 字符组成 ;

$y$ 出现三种情况 : $\mathrm{y}$ 全部由 $\mathrm{a}$ 组成 , $\mathrm{y}$ 全部由 $\mathrm{b}$ 组成, $\mathrm{y}$ 由 $\mathrm{a}\mathrm{b}$ 组成 ;

如果字符串仅有 $\mathrm{a},\mathrm{b}$ 单个字符 , 重复任意 $\mathrm{i}$ 次后 , 不能保证两个字符数量相等 , 矛盾 ;

如果字符串由多个字符组成 , 一旦重复之后 , 次序就被打乱 , 无法保证两个个字符次序 , 也是矛盾 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111401011