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

第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?Σ*，如果