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

2023-03-28 20:07:26 浏览数 (1)

文章目录

  • 一、泵引理 ( 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

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

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

正则表达式 博客 递归 字符串

0 人点赞