[理学]形式语言与自动机理论-04.ppt

  1. 1、本文档共50页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[理学]形式语言与自动机理论-04

第4章 正则语言的性质 西北工业大学计算机学院 康慕宁 问题 判定一个语言是正则语言,或者判定一个语言不是正则语言。 用泵作用引理判定某些语言是非正规的。 根据正规语言的封闭性,可以判定某些由正规语言 经过运算得到的语言还是正规的。 一个正则语言可以有多种描述形式,每种描述形式可以有多个不同的描述,是否能有一种比较“本质”的描述。 如何构造DFA的等价最小DFA。 正则语言的泵引理 正规语言的泵引理 RL的泵引理(pumping lemma,也称为泵作用引理):设L为一个RL,则存在仅依赖于L的正整数N,对于?z∈L,如果|z|≥N,则存在u,v,w,满足: (1) z=uvw (2) |uv|≤N (3) |v|≥1 (4) 对于任意的整数i≥0,uviw∈L (5) N不大于接受L的最小DFA的状态数。 正规语言泵引理的应用-1 证明{0n1n|n≥1}不是RL。 证明:设L={0n1n|n≥1}是RL,则L满足泵引理。不妨设N是泵引理所指的正整数,取z=0N1N,那么z∈L。 根据泵引理,必存在u,v,w,使得z=uvw,而且|uv|≤N, |v|≥1,所以v只能是由0组成的串。不妨设v=0k,k≥1。此时,u=0j,w=0N-k-j1N , j≥0。 根据泵引理,uviw=0j(0k)i0N-k-j1N=0N+k(i-1)1N∈L。 取 i=2,有0N+k(i-1)1N=0N+k1N∈L 而实际上,k≥1,所以N+k≠N,所以0N+k1N?L。 因此,产生矛盾,故假设不成立,即{0n1n|n≥1}不是RL。 正规语言泵引理的应用-2 证明{0n|n为素数}不是RL。 证明:设L={0n| n为素数}是RL,则L满足泵引理。不妨设N是泵引理所指的正整数,取z=0N+p,N+p是素数,那么z∈L。 根据泵引理,必存在u,v,w,使得z=uvw,而且|uv|≤N, |v|≥1。不妨设v=0k,k≥1。此时,u=0j,w=0N+p-k-j, j≥0。 根据泵引理,uviw=0j(0k)i0N+p-k-j=0N+p+k(i-1)∈L。取i=N+p+1,有0N+p+k(i-1)=0(N+p)(k+1)∈L 而实际上,k≥1,所以(N+p)(k+1)不是素数,所以0(N+p)(k+1)?L。 因此,产生矛盾,故假设不成立,即{0n|n为素数}不是RL。 正规语言泵引理的应用-3 证明{0n1m2n+m | m,n≥1}不是RL。 证明:设L={0n1m2n+m | m,n≥1}是RL,则L满足泵引理。不妨设N是泵引理所指的正整数,取z=0N1N22N,那么z∈L。 根据泵引理,必存在u,v,w,使得z=uvw,而且|uv|≤N, |v|≥1,所以v只能是由0组成的串。不妨设 v=0k,k≥1。此时,u=0j,w=0N-k-j1N22N, j≥0。 根据泵引理,uviw=0j(0k)i0N-k-j1N22N=0N+k(i-1)1N22N∈L。取i=0,有0N+k(i-1)1N22N=0N-k1N22N∈L 而实际上,k≥1,所以N-k+N=2N-k≠2N,所以0N-k1N22N ?L。 因此,产生矛盾,故假设不成立,即{0n1m2n+m |m,n≥1}不是RL。 正规语言泵引理的使用方法 应用正规语言泵引理时有以下特点: (1) 泵引理给出的是RL的必要条件,所以泵引理用来证明一个语言不是RL,而且使用反证法。 (2) 泵引理中提到的仅依赖于L的正整数N不用给出具体的数值,只用符号N来表示即可。 (3) z的选择是关键,在保证|z|≥N的前提下,使得根据|uv|≤N,u,v,w的取值很容易得出。 (4) 根据泵引理,得出uviw∈L, i≥0。然后选择一个i,使得根据语言的描述,实际上uviw?L,从而得出矛盾。 (5) 泵引理无法证明一个语言是RL。要证明这一点,可以通过给出语言的RG、FA或者RE描述等方法。 正规语言的封闭性 封闭性:如果任意的、属于某一语言类的语言在某一特定运算下所得到的结果仍然是该类语言,则称该语言类对此运算具有封闭性(closure property)。 有效封闭性:给定一个语言类的若干个语言的描述。如果存在一个算法,它可以构造出这些语言在给定运算下所获得的运算结果的相应形式的语言描述,则称此语言类对相应的运算是有效封闭的,并称此语言类对相应的运算具有有效封闭性(valid closure property)。 正规语言的封闭性可以用于证明某些语言是正规语言。 正规语言的封闭性 RL在并、乘积、闭包运算下是封闭的。 证明根据: ? 正则表达式的定义 ? 正则表达式与正规语言的等价性 正规语言在与任意语言的商运算下是封闭的 定理:设L1 ,L2?Σ*,如果

文档评论(0)

qiwqpu54 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档