形式语言与自动机理论--第五章(蒋宗礼学习教案.pptx

课程目的和基本(jīběn)要求
课程性质
技术基础
基础知识要求
数学分析（或者高等数学），离散数学
主要特点
抽象和形式化
理论(lǐlùn)证明和构造性
基本模型的建立与性质
第1页/共112页
第一页，共113页。 a1a2…ak，
v=ak+1…aj，
w= aj+1…am
uviw∈L
第12页/共112页
第十二页，共113页。
RL的泵引理
例 5-1 证明{0n1n|n≥1}不是 RL。
证明：
假设(jiǎshè)L={0n1n|n≥1} 是 RL
z=0N1N
按照泵引理所述
v=0k k≥1
此时有，
u=0N-k-j
w=0j1N
第13页/共112页
第十三页，共113页。
RL的泵引理
从而有，
uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N
当i=2时，我们(wǒ men)有：
uv2w=0N+(2-1)k1N = 0N+k1N
注意到k≥1，所以，
N+k>N。
这就是说，
0N+k1NL
这与泵引理矛盾。所以，L不是 RL。
第14页/共112页
第十四页，共113页。
RL的泵引理
例 5-2 证明(zhèngmíng){0n|n为素数}不是 RL。
证明(zhèngmíng)：假设L={0n|n为素数} 是 RL。
取 z=0N+p ∈L ，
不妨设v=0k， k≥1
从而有，
uviw=0N+p-k-j(0k)i0j
=0N+p+(i-1)k
第15页/共112页
第十五页，共113页。
RL的泵引理
当i=N+p+1时，
N+p+(i-1)k=N+p+(N+p+1-1)k
= N+p+(N+p)k
= (N+p)(1+k)
注意到k≥1，所以
N+p+(N+p+1-1)k=(N+p)(1+k)
不是(bù shi)素数。故当i=N+p+1时，
uvN+p+1w=0(N+p)(1+k) L
这与泵引理矛盾。所以，L不是(bù shi) RL。
第16页/共112页
第十六页，共113页。
RL的泵引理
例 5-3 证明{0n1m2n+m|m，n≥1}不是(bù shi) RL。
证明：假设L={0n1m2n+m|m，n≥1} 是 RL。
取z=0N1N22N
设 v=0k k≥1
从而有，
uviw=0N-k-j(0k)i0j1N22N
=0N+(i-1)k1N22N
第17页/共112页
第十七页，共113页。
RL的泵引理
uv0w=0N+(0-1)k1N22N
= 0N-k1N22N
注意到k≥1，
N-k+N=2N-k<2N
0N-k1N22N L
这个(zhè ge)结论与泵引理矛盾。所以，L不是 RL。
第18页/共112页
第十八页，共113页。
RL的泵引理
用来证明一个语言不是 RL
不能用泵引理去证明一个语言是 RL。
⑴ 由于泵引理给出的是 RL 的必要条件，所以，在用它证明一个语言不是 RL 时，我们使用反证法。
⑵ 泵引理说的是对 RL 都成立(chénglì)的条件，而我们是要用它证明给定语言不是 RL ，这就是说，相应语言的“仅仅依赖于L的正整数N”实际上是不存在的。所以，我们一定是无法给出一个具体的数的。因此，人们往往就用符号N来表示这个“假定存在”、而实际并不存在的数。
第19页/共112页
第十九页，共113页。
RL的泵引理
⑶ 由于(yóuyú)泵引理指出，如果L是 RL ，则对任意的z∈L，只要|z|≥N，一定会存在u、v、w，使uviw∈L对所有的i成立。因此，我们在选择z时，就需要注意到论证时的简洁和方便。
⑷ 当一个特意被选来用作“发现矛盾”的z确定以后，就必须依照|uv|≤N和|v|≥1的要求，说明v不存在(对“存在u、v、w”的否定) 。
第20页/共112页
第二十页，共113页。
RL的泵引理
⑸ 与选z时类似，在寻找i时，我们也仅需要找到一个表明矛盾的“具体(jùtǐ)”值就可以了(对“所有i”的否定)。
⑹ 一般地，在证明一个语言不是 RL 的时候，我们并不使用泵引理的第(5)条。
⑺ 事实上，引理所要求的|uv|≤N并不是必须的。这个限制为我们简化相应的证明提供了良好支撑——扩充了的泵引理 。
第21页/共112页
第二十一页，共113页。
RL的封闭性
封闭性(closure property)
如果任意的、属于同一语言(yǔyán)类的语言(yǔyán)在某一特定运算下所得的结果仍然是该类语言(y