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

韩曙亮

发布于 2023-03-27 20:14:57

1K0

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、四个等价概念

1 . 正则语言 : 给定一个语言 , 可以自动设计一个识别该语言的自动机 ; 该语言必须是一个正则表达式表达的语言 ;

2 . 正则表达式可以转成自动机 : 先构造接受单字符自动机 , 然后通过串联并联或星计算 , 拼装成自动机 ; 这个转化成的自动机是非确定性有限自动机 ( NFA ) , NFA 可以转成确定性有限自动机 ( DFA ) ;

3 . 自动机可以转成正则表达式 : 给定一个自动机 , 逐个删除自动机的状态 , 最后删除到只剩下开始状态与接受状态两个状态 , 开始状态读取正则表达式跳转到接受状态 , 这个正则表达式就是自动机转成的 ;

确定性有限自动机 ( DFA ) 与非确定性有限自动机 ( NFA ) 等价 , NFA 与扩展型的非确定性有限自动机 ( GNFA ) 是等价的 , GNFA 可以写成正则表达式语言 ( 正则语言 ) ;

上述 DFA , NFA , GNFA , 正则语言概念是等价的 ;

二、自动机界限

1 . 自动机界限 : 自动机不是万能的 , 它有一个界限 , 有的语言自动机可以识别 , 有的语言自动机无法识别 , 这样就需要给有限自动机确定一个界限 ;

2 . 判断语言是否能被自动机识别 : 如何判定一个语言是否是自动机能识别的语言 , 只需要判定该语言是否是正则语言即可 ;

① 语言是正则语言 : 如果该语言是正则语言 , 那么该语言就可以被自动机识别 ;

② 语言不是正则语言 : 如果该语言不是正则语言 , 那么该语言不能被自动机识别 ;

3 . 引入 Pumping 引理 : 如何判定语言是否是正则语言 , 这里使用 Pumping 引理 , 可以判定一个语言是否是正则语言 ;

三、Pumping 引理

Pumping 引理 :

① 正则语言 :

是正则语言 ;

② 数字 : 存在数字

, 这个

叫做 Pumping 长度 ;

③ 字符串 :

是

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

; ( 字符串两个要求 )

④ 字符串分组及要求 :

可以分为三个部分 ,

s = xyz

, 满足如下要求 :

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

表示中间的

的重复次数 ;

|y| > 0

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

|xy| \leq p

四、Pumping 引理示例

1 . 正则语言与自动机等价 : 如果语言

是正则语言 , 该语言可以被有限自动机识别 ;

2 . 已知的语言 :

语言的字符串

s = s_1 \; s_2 \; s_3 \; s_4 \; s_5 \; s_6 \; \cdots \; s_n \;

, 字符串的长度为

;

3 . Pumping 引理中的字符串有两个要求 :

① 长度要求 : 长度

大于等于 Pumping 长度

;

② 语言要求 : 字符串属于语言

;

4 . 假设 : 上述字符串可以被下面的自动机接受 ;

5 . 将上述字符串

输入到自动机中进行计算 :

q_1

是自动机的开始状态 , 读取

s_1

字符 , 就会跳转到

q_3

状态 ;

q_3

状态下 , 读取

s_2

字符 , 就会跳转到

q_{20}

状态 ;

q_{20}

状态下 , 读取

s_3

字符 , 就会跳转到

q_{9}

状态 ;

q_{9}

状态下 , 读取

s_4

字符 , 就会跳转到

q_{17}

状态 ;

q_{17}

状态下 , 读取

s_5

字符 , 就会跳转到

q_{9}

状态 ;

\vdots

q_{..}

状态下 , 读取

s_n

字符 , 就会跳转到

q_{13}

状态 ;

6 . 重复状态说明 : 字符串

的长度是大于字符串输入自动机过程中经过的状态个数的 , 中间肯定有重复的状态 ;

① 这个重复的状态是

q_9

;

② 将两个

q_9

中间的部分

s_4 s_5

再重复几遍 , 该字符串仍然可以被接受 ;

上图就是

字符串中的

xyz

三部分 , 其中的

部分可以无限重复 ;

五、证明语言不是正则语言步骤

证明步骤 : 使用反正法进行证明 ;

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

② Pumping 引理证明 : 存在长度至少为

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

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

六、证明语言不是正则语言示例

证明 :

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

语言不是正则语言 ;

提出假设 : 假设

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

语言是正则语言 ;

引用 Pumping 引理 , 看上述语言是否符合该 Pumping 引理 ;

Pumping 长度 : 存在一个数字

( Pumping 长度 ) , 使得任何长度至少为

的字符串 , 并且该字符串属于

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

语言 ;

满足 Pumping 引理的三个条件 :

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

|y| > 0

|xy| \leq p

如果所有的字符串都满足上述上个条件 , 说明该语言是正则语言 , 如果找出了一个字符串不满足上述条件 , 该语言就不是正则语言 ;

按照上述提出的证明步骤 , 证明该字符串不是正则表达式 ;

1 . 选择反例字符串 : 目的是证明正则表达式不成立 , 选择的是反例 ;

① 反例选择 : 选择字符串

s = 0^p 1^p

, 该字符串有

个

和

个

字符组成 ;

② Pumping 引理条件 : 将上述字符串分成

s = xyz

三个部分 , 看是否满足 Pumping 引理的三个条件 ;

2 .

出现三种情况 :

全部由

组成

全部由

组成

全部由

0,1

组成 ;

如果上述每种情况都出现矛盾 , 说明假设不成立 ;

3 .

全部由

组成情况分析 :

① 假设 : 假设

全部由

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

语言 ;

②

重复后不符合要求 : 但是

重复若干次之后 ,

的个数就大于

的个数了 , 此时不符合

s = 0^p 1^p

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

4 .

全部由

组成情况分析 :

① 假设 : 假设

全部由

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

语言 ;

②

重复后不符合要求 : 但是

重复若干次之后 ,

的个数就大于

的个数了 , 此时不符合

s = 0^p 1^p

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

5 .

全部由

0,1

组成情况分析 :

① 假设 : 假设

全部由

0,1

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

语言 ;

②

重复后不符合要求 : 但是

0,1

重复若干次之后 , 就会打乱

s = 0^p 1^p

字符串中

0,1

的相互顺序 , 其中

0,1

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

经过上述讨论 ,

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

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

语言不是正则语言 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-05-17，如有侵权请联系 cloudcommunity@tencent.com 删除

正则表达式

设计

字符串

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

正则表达式

设计

字符串

登录后参与评论

0 条评论

热度