【计算理论】泵引理以及应用(证明某些语言不是正则的)

1、基础知识

1.1、一个典型的有穷自动机状态图

状态:q1;q2;q3
起始状态q1用一个指向它的无出发点的箭头表示;
接受状态q2带有双圈
转移:从一个状态指向另一个状态的箭头

本例中q1为起始状态,q2为接受状态。如果一个字符串w经过M1可以到达接受状态那称为M1接受s(比如字符串1,01,001,0011等等会被M1接受)。若A是机器M1接受的全部字符串集,则称A是机器M1的语言,记L(M1)=A;

以q1为例,q1状态遇到0自反,遇到1则进入q2状态;

1.2、正则运算

如果一个语言被一台有穷自动机识别,则称它是正则语言。算术运算中基本对象是数,正则运算的基本对象是语言。定义语言的运算包括并、连接、星号三种(类似算术运算中加减乘数角色)。
像M1这样的下个状态确定的自动机属于确定型有穷自动机(DFA),另一种是不确定的有穷状态自动机(non-deterministic finite automaton ,NFA)。

两者区别如下:

当机器处于给定的状态,并读入下一个输入符号时,可以知道机器的下一个状态是什么则它是确定的,称为确定型计算,而若在任何一点,下一个状态可能存在若干选择,称为非确定型计算。

2、泵引理

{直接看定义、概念确实枯燥,但看过例子之后回头再看定义就会有“意会”的感觉}

证明非正则性的技术。该定理指出所有的正则语言都有一种特殊的性质。语言中的所有字符串只要它的长度不小于某个特定的值-泵长度,就可以被“抽取”。(每一个这样的字符串都包含一段子串,把这段子串重复任意次,得到的字符串仍在这个语言中)

2.1、定义

设A为一个正则语言,则存在仅依赖于A的正整数p(泵长度),对于?s∈A,如果|s|≥p
,则s可以被分为3段,存在s=xyz,满足下述条件
(1)对于任意的整数i≥0,xyiz∈A;
(2)|y|>0;
(3) |xy|≤p;

泵长度可理解为等价DFA的状态个数。

Si在qi的间隙中,所以若S长度为n,那么状态集的长度为n+1;

在这样的划分下,条件1和2是满足的。

注意y是两个q9之间的部分,所以|xy|<=p也是满足的。

2.2、证明某些语言不是正则语言(regular language)

{语言B符合泵引理,是B是正则语言的必要而不充分条件,所以一般都用证明某些语言不是正则的}

运用泵引理证明B不是正则语言的基本步骤:

首先,假设B是正则的,以便推出矛盾;

其次,在B中寻找一个字符串s,其长度大于p;

最后,证明s不能被抽取;

对3)来讲,比如B中的一个字符串s为000111,分割s为x、y、z的过程,以y=01为例,xyz为000111,xyyz则为00010111,后者不是B的成员,矛盾。

至此,泵引理应该很容易被理解了吧

3、参考资料

[1] 计算理论导引 第二版,Michael Sipser

[2] 维基百科{http://zh.wikipedia.org/wiki/%E6%B3%B5%E5%BC%95%E7%90%86

http://en.wikipedia.org/wiki/Pumping_lemma

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages}


赞 (0) 评论 分享 ()