【计算理论】计算理论总结 ( 泵引理 Pumping 证明 ) ★★

文章目录

• 一、泵引理 ( Pumping )
• 二、泵引理证明示例 1
• 三、泵引理证明示例 2
• 四、泵引理证明示例 3

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

一、泵引理 ( Pumping )

---

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

正则表达式 是 原子字符 , 或 原子字符进行递归 并运算

\cup

, 串联运算

\circ

, 星运算

*

形成的字符串组成的语言 ;

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

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

泵引理 :

① 正则语言 :

\rm A

是正则语言 ;

② 数字 : 存在数字

\rm p

, 这个

\rm p

叫做 泵长度 ;

③ 字符串 :

\rm s

是

\rm A

语言中的子字符串 , 其长度大于等于

\rm p

; ( 字符串两个要求 )

④ 字符串分组及要求 : 所有的子字符串

\rm s

可以分为三个部分 ,

\rm s = xyz

, 满足如下要求 :

• ​

\rm xy^iz \in A \quad ( i \geq 0 )

:

\rm i

表示中间的

\rm y

的重复次数 ;

• ​

\rm |y| > 0

:

\rm y

是中间重复的部分 , 星计算部分 ;

• ​

\rm |xy| \leq p

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

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

② Pumping 引理常数提出 : 存在一个常数

\rm p

, 所有长度至少为

\rm p

的任何字符串 , 都满足 Pumping 引理 的三个性质 ;

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

二、泵引理证明示例 1

---

证明 :

\{ 0^n 1^n : n \geq 0 \}

语言 不是正则语言 ;

1. 提出假设 : 假设

\{ 0^n 1^n : n \geq 0 \}

语言 是正则语言 ;

2. 泵长度 : 存在一个泵长度

\rm p

, 只要是 长度至少为

\rm p

的子字符串

\rm s

, 都 满足 Pumping 引理 的三个性质 ;

\rm s

字符串可以分为三个部分 ,

\rm s = xyz

, 满足如下要求 :

• ​

\rm xy^iz \in A \quad ( i \geq 0 )

:

\rm i

表示中间的

\rm y

的重复次数 ;

• ​

\rm |y| > 0

:

\rm y

是中间重复的部分 , 星计算部分 ;

• ​

\rm |xy| \leq p

3. 找出矛盾 : 找出一个 长度至少为

\rm p

的子字符串

\rm s

, 不符合泵引理要求 , 这里就出现了矛盾 , 假设不成立 ;

选择字符串

\rm s = 0^p 1^p

, 该字符串有

\rm p

个

\rm 0

和

\rm p

个

1

字符组成 ;

y

出现三种情况 :

y

全部由

0

组成 ,

y

全部由

1

组成 ,

y

全部由

0,1

组成 ;

①

y

全部由

0

组成 情况分析 :

假设 : 假设

y

全部由

0

组成 , 其不停的重复 , 得到的新字符串 , 仍然属于

A

语言 ;

y

重复后不符合要求 :

\rm i

是任意值 , 但是

0

重复若干次之后 , 如 重复次数

\rm i = p + 1

,

0

的个数就大于

1

的个数了 , 此时不符合

s = 0^p 1^p

要求了 , 因此这种情况不成立 ;

②

y

全部由

1

组成 情况分析 :

假设 : 假设

y

全部由

1

组成 , 其不停的重复 , 得到的新字符串 , 仍然属于

A

语言 ;

y

重复后不符合要求 :

\rm i

是任意值 , 但是

1

重复若干次之后 , 如 重复次数

\rm i = p + 1

,

1

的个数就大于

0

的个数了 , 此时不符合

s = 0^p 1^p

要求了 , 因此这种情况不成立 ;

③

y

全部由

0,1

组成 情况分析 :

假设 : 假设

y

全部由

0,1

组成 , 其不停的重复 , 得到的新字符串 , 仍然属于

A

语言 ;

y

重复后不符合要求 :

\rm i

是任意值 , 但是

0,1

重复若干次之后 , 如 重复次数

\rm i = p + 1

, 就会打乱

s = 0^p 1^p

字符串中

0,1

的相互顺序 , 其中

0,1

不能存在交叉 , 因此这种情况不成立 ;

经过上述讨论 ,

y

的三种情况都不符合 Pumping 引理 , 因此

\{ 0^n 1^n : n \geq 0 \}

语言不是正则语言 ;

三、泵引理证明示例 2

---

证明 :

\{ 0^n 1^n2^n : n \geq 0 \}

语言 不是正则语言 ;

1. 提出假设 : 假设

\{ 0^n 1^n2^n : n \geq 0 \}

语言 是正则语言 ;

2. 泵长度 : 存在一个泵长度

\rm p

, 只要是 长度至少为

\rm p

的子字符串

\rm s

, 都 满足 Pumping 引理 的三个性质 ;

\rm s

字符串可以分为三个部分 ,

\rm s = xyz

, 满足如下要求 :

• ​

\rm xy^iz \in A \quad ( i \geq 0 )

:

\rm i

表示中间的

\rm y

的重复次数 ;

• ​

\rm |y| > 0

:

\rm y

是中间重复的部分 , 星计算部分 ;

• ​

\rm |xy| \leq p

3. 找出矛盾 : 找出一个 长度至少为

\rm p

的子字符串

\rm s

, 不符合泵引理要求 , 这里就出现了矛盾 , 假设不成立 ;

选择字符串

\rm s = 0^p 1^p2^p

, 该字符串有

\rm p

个

\rm 0

,

\rm p

个

1

,

\rm p

个

2

字符组成 ;

y

出现三种情况 :

y

全部由

0

组成 ,

y

全部由

1

组成,

y

全部由

2

组成 ,

y

全部由

0,1,2

组成,

y

全部由

0,1

组成 ,

y

全部由

1,2

组成 ;

如果字符串仅有

0, 1, 2

单个字符 , 重复任意

\rm i

次后 , 不能保证三个字符数量相等 , 矛盾 ;

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

四、泵引理证明示例 3

---

证明 :

\rm \{ www | w \in \{a, b\}^* \}

语言 不是正则语言 ;

\rm \{a, b\}^*

中的星运算

*

是 将

\rm \{a, b\}

中的有限个字符串串联在一起 , 将若干个

\rm a

与若干个

\rm b

以任意先后顺序任意交错顺序进行排列 ; 即

\rm a, b

组成的任意字符串都属于上述语言 ;

1. 提出假设 : 假设

\rm \{ www | w \in \{a, b\}^* \}

语言 是正则语言 ;

2. 泵长度 : 存在一个泵长度

\rm p

, 只要是 长度至少为

\rm p

的子字符串

\rm s

, 都 满足 Pumping 引理 的三个性质 ;

\rm s

字符串可以分为三个部分 ,

\rm s = xyz

, 满足如下要求 :

• ​

\rm xy^iz \in A \quad ( i \geq 0 )

:

\rm i

表示中间的

\rm y

的重复次数 ;

• ​

\rm |y| > 0

:

\rm y

是中间重复的部分 , 星计算部分 ;

• ​

\rm |xy| \leq p

3. 找出矛盾 : 找出一个 长度至少为

\rm p

的子字符串

\rm s

, 不符合泵引理要求 , 这里就出现了矛盾 , 假设不成立 ;

选择字符串

\rm s = a^p b^p

, 该字符串有

\rm p

个

\rm a

,

\rm p

个

\rm b

字符组成 ;

y

出现三种情况 :

\rm y

全部由

\rm a

组成 ,

\rm y

全部由

\rm b

组成,

\rm y

由

\rm ab

组成 ;

如果字符串仅有

\rm a,b

单个字符 , 重复任意

\rm i

次后 , 不能保证两个字符数量相等 , 矛盾 ;

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