形式语言学ch5

第5章 正则语言的性质
RL性质 泵引理及其应用 并、乘积、闭包、补、交 正则代换、同态、逆同态的封闭性
从RL固有特征寻求表示的一致性 Myhill-Nerode定理 FA的极小化
RL的几个判定问题 空否、有穷否、两个DFA等价否、成员关系
5.1 RL的泵引理
泵引理(pumping lemma) 设L为一个 RL ，则存在仅依赖于L的正整数N，对于 ∀z∈L，如果|z|≥N，则存在u、v、w，满足 ⑴ z=uvw； ⑵ |uv|≤N； ⑶ |v|≥1； ⑷ 对于任意的整数i≥0，uviw∈L； ⑸ N不大于接受L的最小DFA M的状态数。
封闭的可直接由定理5.4得出，关于逆同态，令DFA M满
则 L = L(B),其中B是DFA (Q, Σ,δ , q0,Q − F ) 即:A的接受状态都是B的非接受状态,反之亦然.因此 w属
于L(B)当且仅当δ^(q0,w)属于Q-F,而后者成立当且仅当 w不属于 L(A).
5.2正则集合的封闭性质
例
L∈{a},Σ ={a,b}
a
q0
q
b
a,b
M
d
a,b
7
5.1 RL的泵引理
⑶ 由于泵引理指出，如果L是 RL ，则对任意的z∈L， 只要|z|≥N，一定会存在u、v、w，使uviw∈L对所有的i成 立。因此，我们在选择z时，就需要注意到论证时的简洁和 方便。
⑷ 当一个特意被选来用作“发现矛盾”的z确定以后，就 必须依照|uv|≤N和|v|≥1的要求，说明v不存在(对“存在u、 v、w”的否定) 。
1
5.1 RL的泵引理
证明思想
5.1 RL的泵引理
证明： DFA在处理一个足够长的句子的过程中，必定会重复地经 过某一个状态。换句话说，在DFA的状态转移图中，必定存 在一条含有回路的从启动状态到某个终止状态的路。由于是 回 路 ， 所 以 ， DFA 可 以 根 据 实 际 需 要 沿 着 这 个 回 路 循 环 运 行，相当于这个回路中弧上的标记构成的非空子串可以重复 任意多次。
9
5.2正则集合的封闭性质
定理5.1 正则集合在并、连接和Kleene闭包运算下是封 闭的。
(r1 + r2),(r1r2)及(r1)* 仍是正则式，所以正则集
合的并、连接和Kleene闭包表示正则集合
定理5.2 正则集合对补运算的封闭，即若 L ⊆ Σ* 是一正则集合， L = Σ* − L 也是正则集合。 证明：令L=L(M) M为一DFA M = (Q, Σ,δ , q0,F )
果，其中 wi ∈Rai , wi为Rai 中的任意的字。
12
5.2正则集合的封闭性质
用f表示代换，则f为一个映射 f : Σ → 2∆* ∆ 为 一字母表 Σ到∆* 的字集合映射，f把 Σ 中每个符 号与一个正则集合联起来，可以把f扩展成
f : Σ* → 2∆* 1. f (ε ) = ε 2. f ( xa ) = f ( x ) f ( a )再扩充到集合上
而L(M’)恰好是R经代换后得到的集合， 所以该集合是正则集合。 例
令 f (0) = a, f (1) = b*, f (0) ={a}, f (1) ={b}*
前二者为正则表示
f (010)}{ } { }{ } F (L) = {a}* a + b* b* * = a* a + b* b* *
uviw=0N-k-j(0k)i0j1N22N =0N+(i-1)k1N22N
6
5.1 RL的泵引理
uv0w=0N+(0-1)k1N22N = 0N-k1N22N
注意到k≥1， N-k+N=2N-k<2N 0N-k1N22N ∉L 这个结论与泵引理矛盾。所以，L不是 RL。
5.1 RL的泵引理
用来证明一个语言不是 RL 不能用泵引理去证明一个语言是 RL。 ⑴ 由于泵引理给出的是 RL 的必要条件，所以，在用它 证明一个语言不是 RL 时，我们使用反证法。 ⑵ 泵引理说的是对 RL 都成立的条件，而我们是要用它 证明给定语言不是 RL ，这就是说，相应语言的“仅仅依赖 于L的正整数N”实际上是不存在的。所以，我们一定是无 法给出一个具体的数的。因此，人们往往就用符号N来表 示这个“假定存在”、而实际并不存在的数。
f (L) = U f (x) x∈ L
例：h(0)=ab, h(1)=ε定义的函数h是一个同态。任何给定由0和1组成的 串，它用ab替换所有的0并把所有的1用空串替换。如0011成为abab.
5.2 RL的封闭性
例 5-4 设∑={0，1}，Δ={a，b}，f(0)=a，f(1)=b*，则 f(010)=f(0)f(1)f(0)=ab*a f({11，00})=f(11)∪f(00) =f(1)f(1)∪f(0)f(0)=b*b*+aa=b*+aa f(L(0*(0+1)1*))=L(a*(a+b*)(b*)*) =L(a*(a+b*)b*)=L(a*ab*+a*b*b*) =L(a*b*)
且满足 L1 = L(M 1 )和L2 = L(M 2 )
构造
M = (Q1 × Q2 , Σ,δ ,[q1, q2 ], F1 × F2 ) δ ([p1, p2 ], a) = [δ1( p1, a),δ2 ( p2, a)]
对于所有p1 ∈ Q1, p2 ∈ Q2 ,∀a ∈ Σ
易证 : L(M ) = L(M1) I L(M 2 )
3
5.1 RL的泵引理
故， δ(q0，a1a2…ak(ak+1…aj)i aj+1…am)=qm 也就是说， a1a2…ak(ak+1…aj)i aj+1…am∈L(M) u= a1a2…ak， v=ak+1…aj， w= aj+1…am uviw∈L
5.1 RL的泵引理
例 5-1 证明{0n1n|n≥1}不是 RL。 证明：
5.1 RL的泵引理
例 5-2 证明{0n|n为素数}不是 RL。 证明：假设L={0n|n为素数} 是 RL。 取 z=0N+p ∈L ， 不妨设v=0k， k≥1 从而有， uviw=0N+p-k-j(0k)i0j
=0N+p+(i-1)k
5
5.1 RL的泵引理
当i=N+p+1时， N+p+(i-1)k=N+p+(N+p+1-1)k
5.1 RL的泵引理
⑸ 与选z时类似，在寻找i时，我们也仅需要找到一个表明 矛盾的“具体”值就可以了(对“所有i”的否定)。
⑹ 一般地，在证明一个语言不是 RL 的时候，我们并不使 用泵引理的第(5)条。
⑺ 事实上，引理所要求的|uv|≤N并不是必须的。这个限制 为我们简化相应的证明提供了良好支撑——扩充了的泵 引理 。
假设L={0n1n|n≥1} 是 RL
z=0N1N 按照泵引理所述
v=0k
k≥1
此时有，
u=0N-k-j
w=0j1N
4
5.1 RL的泵引理
从而有， uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N
当i=2时，我们有： uv2w=0N+(2-1)k1N = 0N+k1N
注意到k≥1，所以， N+k>N。 这就是说， 0N+k1N∉L 这与泵引理矛盾。所以，L不是 RL。
以及δ 2 (q jk−1 , ak ) = q jk , k = 1,2,...n且q jn ∈ F2
由定义知有：
[ ] [ ] δ ( q , q ik−1
jk −1
, ak ) =
qik , q jk
对于k
= 1,2,...n
[ ] [ ] [ ] 而 qi0 , q j0 为 q1, q2 即M的初态，qin , q jn ∈ F1 × F2
= N+p+(N+p)k = (N+p)(1+k) 注意到k≥1，所以 N+p+(N+p+1-1)k=(N+p)(1+k) 不是素数。故当i=N+p+1时， uvN+p+1w=0(N+p)(1+k) ∉L 这与泵引理矛盾。所以，L不是 RL。
5.1 RL的泵引理
例 5-3 证明{0n1m2n+m|m，n≥1}不是 RL。 证明：假设L={0n1m2n+m|m，n≥1} 是 RL。 取z=0N1N22N 设 v=0k k≥1 从而有，
13
5.2正则集合的封闭性质
定理5.4 正则集合类对代换运算是封闭的
证明：设 R ⊆Σ* 为一正则集合，对每个 a∈Σ
令 Ra ⊆ ∆* 是一正则集合。 f定义 f (a) = Ra ，令正则式r表示正则集合R， 正则式ra表示正则集合Ra 把r中的每个a都替换成ra后，仍为正则式，显然， 替换后得到的正则式表示的恰好是R经过代换后得 到的集合，因此是正则集合。 或者，若R为正则集合，则有DFA M使 L(M ) = R ，
= a*ab* + a*b* = a*b*
5.2正则集合的封闭性质
同态是一种特殊的替换：即 f (a) ={x} x∈∆* ，记同 态为 h: h(a) = x,h 可以有逆同态 h−1(L) = {x h(x) ∈ L}
定理5.5 正则集合类对于同态运算和逆同态运算都是封 闭的。
证：同态是一种特殊的代换，故正则集合对同态运算是
5.2正则集合的封闭性质
Ra为正则集合，则有DFA Ma使 L(M a ) = Ra 中每条标记为a的弧做替换
，对于M
对每个Ma引入一个新的状态fa做终态，原来终态改成非