第五章---泵引理.pdfVIP

问题 • 判定一个语言是正则语言，或者判定一个语言 不是正则语言。 – 用泵作用引理判定某些语言是非正规的。 – 根据正规语言的封闭性，可以判定某些由正规语言 经过运算得到的语言还是正规的。 • 一个正则语言可以有多种描述形式，每种描述 形式可以有多个不同的描述，是否能有一种比 较“本质” 的描述。 – 如何构造DFA 的等价最小DFA 。 正则语言的泵引理 • 设L是一个RL ，DFA M= (Q,Σ,δ,q0,F)满足L(M)=L ，|Q|=N，而且不 妨设Q 中不含任何不可达状态。 • 取L 的句子z=a a …a (m ≥ 1 2 m N) ，对∀h ，1≤h ≤m ，令 ,a a …a )=q 。由于 ,q ,…,q 中至少有 m ≥ δ(q0 1 2 h h N ，所以在状态序列q0 1 N q q kj ≤N 。如下 两个状态是相同的。设这两个状态为q 与 ： =q ， k j k j 图所示： a …a k+1 j a …a a …a 1 k j+1 m q q =q 0 k j qm • 此时有： – δ(q ,a a …a )=q ，δ(q ,a …a )=q ，δ(q ,a …a )=q ，q ∈F 0 1 2 k k k k+1 j j j j+1 m m m • 对于任意整数i ≥0，有： i i – δ(q ,a …a (a …a ) a …a )=q ，即a …a (a …a ) a …a ) ∈L(M) 0 1 k k+1 j j+1 m m 1 k k+1 j j+1 m • 取u=a a …a ，v=a …a ，w=a …a ，那么有： 1 2 k k+1 j j+1 m i – uv w ∈L ，|uv|≤N ，|v|≥1