第5 章
正则语言的性质
前面曾经提到,{0n1n|n≥1}不是正则语言(RL)。这并不是因为某人构造不出产生该
语言的正则文法(RG)、有穷状态自动机(FA)或者正则表达式(RE)等,而是从RL的性质出
发,可以证明该语言不具有RL的性质,所以不存在这些形式的描述。那么,RL具有什么样
的性质呢? 本章将首先对此进行讨论,包括RL的泵引理及其应用;RL关于并、乘积、闭包、
补、交、正则代换、同态、逆同态等运算的封闭性。
另一个问题是对一个给定的RL,存在多个产生该语言的正则文法,多个识别该语言的
有穷状态自动机和多个表达该语言的正则表达式。由于它们描述的是同一个语言,所以,它
们“本质上”应该是一样的。因此,人们希望能找到一种方法,给出RL“本质上”的描述———
该语言所决定的相应字母表的克林闭包的等价分类,然后根据这个分类,构造出接受这个给
定RL的、状态最少的、确定的有穷状态自动机———最小DFA。由于语言是给定的,所以相
应的最小DFA 在规定的意义(如同构)下应该是唯一的。最后将讨论如何根据DFA 去构
造其相应的最小DFA,并且此方法是可以自动化的。这一部分的内容包括:右不变的等价
关系、DFA 所确定的等价关系与语言确定的等价关系的右不变性,Myhill-Nerode定理的证
明与应用,DFA 的极小化。
在有了语言L 的最小DFA 后,去掉其相应的陷阱状态,可以方便地得到较为简洁的正
则文法。当然,从最小DFA 出发,寻求L 的正则表达式也可能对构造是非常有利的。
最后,本章还将讨论RL的判定算法。
5.1 正则语言的泵引理
从前面的讨论知道,任何有穷语言都是RL。所以,非RL一定是无穷语言。因此,我们
只讨论无穷语言是否为RL的判定问题。如何判定一个语言不是RL呢? 这需要从RL的
“本质”特性出发进行讨论。
DFA 是RL的识别模型。一个DFA 只有有穷个状态,这就是说,当该DFA 识别的语
言L 是无穷语言时,L 中必定存在一个足够长的句子,使得DFA 在识别该句子的过程中,
肯定要重复地经过某些状态。
例如句子z=a1a2…am ,不妨假设DFA 在识别它的过程中需要经过的状态依次为q0,
q1,…,qm 。根据重叠原理,当m 大于或等于DFA 所有可达状态的个数时,这些状态中至少
正则语言的性质
第
有一对是重复的,如qk
和qj
。显然,这里的k≠
j
成立,不妨设k<j。设v=ak+1…aj
是
5
引导DFA 从状态qk
到达状态qj
的子串,则它就是该DFA 中从q0 到qm
的标记为
x
的路
章
中从qk
到qj
因此,所构成的字符串
的标记为
v
的回路,
v
在它出现的位置无论重复多少次,
都一定是DFA 所识别的语言的句子,如图5-1所示。
531
图5-
1
DFA
处理句子中经历的状态序列
由于qk
和qj
是同一个状态,为了便于理解,将该图重画成如图5-2所示的样子。
图5-
2
DFA
处理句子经历的状态序列中存在重复的状态
根据重叠原理,这样的qk
与qj
在序列q0,qN
中一定是存在的,
N
为相应
q1,…,其中,
DFA 的可达状态个数。下面给出这种现象的严格描述,并给出判定一个语言不是RL 的一
般方法。
设
L
是一个RL,DFA
M
=(Q,δ,F)
Σ,q0,
满足
L(
M
)=L,|Q|=
N
不失一般性,不妨假设
Q
中不含任何不可达状态,并且|Q|=
N
。取
L
的句子
对.h,1≤h≤m,令
z=a1a2…am
(m≥
N
)
δ(a1a2…ah
)=qh
在状态序列q0,
q0,
中至少有两个状态是相同的。不妨假设qk
由于m≥
N
,所以, q1,…,与
qj
是该状态序列中最早出现的相同状态:
qN
qk
=qj
显然
,
k<j≤
N
此时有
δ(q0,a1a2…ak
)=qk
qk
,)
δ(ak+1…aj=qj
=qk
δ(qj
,aj+1…am
)=qm
注意到qj
=qk
,所以对于任意整数i≥0,
i)
i
qk
,()qk
,()1)
δ(ak+1…aj=δ(ak+1…aj
.
=δ()
qk
,
ak+1…aj
=qk
631
形式语言与自动机理论(第4版)
因为
z∈L(
M
)
所以
qm
∈
F
故,对于任意整数i≥0,
δ()
)
i
也就是说,
q0,a1a2…ak
(ak+1…ajaj+1…am
=qm
i
a1a2…ak
()
M
)
ak+1…ajaj+1…am
∈L(
取
u=a1a2…ak
v=ak+1…aj
对于任意整数i≥0,
w
=aj+1…am
注意到k<j≤
N
,所以u,
uviw∈
L
v
满足如下条件:
|uv|≤
N
|v|≥1
再注意到讨论中的DFAM
的任意性,所以,该结论对最小DFA 也成立。从而得到如下
引理。
5-
1
设
L
为一个RL,则存在仅依赖于
L
的正整数
N
,对于.z∈L,如果
则存在u,满足:
|z|≥
N
, v,w,
(1)z=vw 。
(2)|uv|≤N。(u)
(3)|v|≥1 。
uw∈L。
(4)对于任意整数i≥0,vi(5)
N
不大于接受
L
的最小DFAM
的状态数。
引理5-1被称为关于RL 的泵引理(pumpinglemma )。由于它是如此的重要和有影
响,以至于人们一直将其称为引理而未改称其为定理。
例51
证明{0n1n|n≥1}不是RL 。
证明:设L={0n1n|n≥1 }。假设
L
是RL,则它满足泵引理。不妨设
N
是泵引理所指
的仅依赖于
L
的正整数,取
显然
z,
=0N1N
必存在u,wu并且|所以
v
只可能
z∈L。按照泵引理所述, v,。由于|v|≤
N
, v|≥1,
是由0组成的非空串。不妨
设
v=0k
,k≥1
此时有
u=0N
-k-
j
w=0j1N
正则语言的性质
第
从而有
5
-k-j(i0i-1)
章
当i=2时,有
uviw=0N
0k
)j1N
=0N
+(k1N
uv2w=0N
+(2-1)k1N
=0N
+k1N
731
注意到k≥1,所以
N
+k>
N
这就是说,
0N
+k1N
.
L
这与泵引理矛盾,所以,
L
不是RL 。
证明{0n|
n
为素数}不是RL 。
例52
证明:设L={0n|
n
为素数}。假设
L
是RL,则它满足泵引理。不妨设
N
是泵引理所
指的仅依赖于
L
的正整数,取
N
+
p
其中,
N
+
p
是素数,即z∈L。
z=0
按照泵引理所述,必存在u,。由于|所以
v
必定是由0组成的非空串。不
v,wv|≥1,
妨设
v=0k
,k≥1
此时有
u=0N+p-k-
j
w=0j
从而有
k-j(i0i-1)k
uviw=0N
+p-0k
)
j
=0N
+
p
+(
i1)
由于是要证明
L
不是RL,因此这里要能找到
i
的一个值,它能表明串0N
+p+(-
k
不是
L
的句子。对本例而言,就是要表明
N
+p+(1)当i=
N
+p+1
时,有
i-
k
不是素数。显然,
N
+p+(-
k
=
N
+p+(-k
i1)
N
+p+11)
=
N
+p+(
N
+p)
k
=(
N
+p)(1+k)
注意到k≥1,所以
N
+p+(
N
+p+11)
N
+p)(1+k)
不是素数。故当i=
N
+p+1 时,
-k=(
uvN
+
p
+1w=0(
N
+p)(1+k)
不是
L
的句子:
vN
+
p
+1
这与泵引理矛盾。所以,
L
不是RL 。
uw.
L
例53
n1n+m|m,
证明{0m2n≥1}不是RL 。
证明:设L={0n1n+m|m,则它满足泵引理。不妨设
N
是泵
m2n≥1 }。假设
L
是RL,
引理所指的仅依赖于
L
的正整数(实际上,这个
N
是不存在的), 取
831
形式语言与自动机理论(第4版)
z=0N1N22N
显然,必存在u,w。由于|uv|≤
N
,并且|v|≥1,所以
v
只可能
z∈L。按照泵引理所述, v,
是由0组成的非空串。不妨
设
v=0k
,k≥
1
此时有
u=0N-k-
j
w=0j1N22N
从而有
uviw=0N
-k-j(0i0j1N22N
=i1)k1N2
k
)0N
+(-2N
与前面两个例题一样,由于是要证明
L
不是RL,因此,这里要能找到
i
的一个值,它能
表明串0N
+(-k1N22N
不是
L
的句子。对本例而言,也就是要找
i
的一个值,它使得所得字i1)
i1)当i0时,
符串中0和1的个数之和不等于2的个数,即
N
+(-k+
N
≠2N
。显然,=有
0N
+(0-1)
N
-2N
注意到k≥1,所以
uv0w=k1N22N
=0k1N2
N
-k+
N
=2N
-k<2N
这就是说,0N
-k1N22N
.
L
这与泵引理矛盾。所以,
L
不是RL 。
通过上述3个例子,可以更清楚地看出,引理5-1是用来证明一个语言不是RL
的。因
为它只是说RL 必定满足这些条件,并没有说满足条件的语言是RL 。即引理给出的是RL
的“必要条件”而不是“充分条件”。所以,不能用泵引理去证明一个语言是RL
。此外,在使
用泵引理证明一个给定语言不是RL 时,需要注意如下几方面的问题:
(1)由于泵引理给出的是RL 的必要条件,所以,在用它证明一个语言不是RL 时,使用
反证法。
(2)泵引理说的是对RL 都成立的条件,而要用它证明给定语言不是RL 。也就是说,
相应语言的“仅仅依赖于
L
的正整数
N
”实际上是不存在的。所以,一定是无法给出一个具
体数的。因此,往往就用符号
N
来表示这个“假定存在”而实际并不存在的数。
(3)泵引理指出, 则对任意z∈L, z|≥
N
,一定会存在u,w,
如果
L
是RL, 只要|v,使
得uviw∈
L
对所有的
i
成立。因此,在选择
z
时,就需要注意到论证时的简洁和方便。
例如,例5-3中如果不取z=0N1N22N
,而是取z=0n1m2n+
m
,并且只要求2(n+m)≥
N
,那么要证明不存在这样的u,v,w,除了需要讨论v=0k
的情况外,还需要分别讨论
v=1k
,v=2k
,v=0h1k
,v=1h2k
等情况。这里,h,k≥1 。显然,这些附加的讨论在取
z=0N1N22N
时,都被避免了。
再例如,设
L={x|
x
为0的个数和1的个数相等的0,1串}
01)01)
L
不是RL 。如果取z=(
N
,就无法用泵引理证明
L
不是RL 。因为,只要取v=(
k
,
N
≥k≥1,就能保证对于任意整数i≥0,iw
∈
L
成立。这样的
z
还很多。但是,如果取
z=0N1N
,相应的证明就变得与例5-1一样(u) 容(v) 易了。由此可见,要力求寻找这样的一个z,
z
中不存在满足条件的子串v,使得当
v
被“泵进”或者“泵出”时,字符串uviw
总保持
L
的句
正则语言的性质
第
子特征。
5
综上所述,在选择
z
时,应该选择那些既可以找出矛盾,又能使证明尽可能简单的特殊
章
的z(对“ 的否定)。事实上,
z
的选取
所有
z
” 在用泵引理证明一个语言不是RL 的过程中,
是最困难的。一旦选出了一个恰当的z,证明基本上就可以顺利地进行下去,因为剩余的叙
述基本上是“按部就班”地进行。
931
(4)当一个特意被选来用作“发现矛盾”的
z
确定以后,就必须说明满足条件|uv|≤
N
和|v|≥1 的所有
v
都不能使uw∈
L
对所有i≥0 成立( 存在u,
w
”
vi对“ v,的否定)。
(5)与选
z
时类似,在寻找
i
时,也仅需要找到一个表明矛盾的“具体”值就可以了(对
“所有i”的否定)。
(6)一般地,在证明一个语言不是RL 的时候,并不使用泵引理的第(5)条。
(7)事实上,引理所要求的|uv|≤
N
并不是必需的。但它为简化相应的证明提供了良
好的支撑。但是,从引理的证明可以看出,对于一个RL,当它的句子
z
足够长时,对
z
的任
意一个长度为
N
的子串z1,同样可以在这个子串中找到可以被“泵进”或者“泵出”的非空子
串v。这会给证明带来更多的方便。例如,关于{0n1m2m|n,
m
≥1}不是RL 的证明就是如
此。这种证明方法被称为扩充了的泵引理(见相关习题)。当然,有时会需要使用RL 所具
有的其他性质来完成相应的证明。有关内容稍后讨论。
(8)除了需要证明一个语言不是RL 外,有时也希望证明一个语言是RL 。此时,最直
接的方法是给出该语言的正则文法描述,或者FA 和RE 描述。但是有时候直接用一些已
有的结果和RL 的性质会更有效,毕竟语言的正则文法描述或者FA 和RE 描述并不总是那
么容易给出的。
5.正则语言的封闭性
2
本节讨论RL 对有关运算的封闭性。
定义51
如果任意的、属于某一语言类的语言在某一特定运算下所得的结果仍然是
该类语言,则称该语言类对此运算是封闭的,并称该语言类对此运算具有封闭性(closure
property)。
给定一个语言类的若干语言的描述。如果存在一个算法,它可以构造出这些语言在给
定运算下所获得的运算结果的相应形式的语言描述,则称此语言类对相应的运算是有效封
闭的,并称此语言类对相应的运算具有有效封闭性(validclosureproperty)。
根据正则表达式的定义,立即可以得到以下定理
。
5-
1
RL 在并、乘积、闭包运算下是封闭的
。
5-
2
RL 在补运算下是封闭的
。
证明:设
L
是
Σ
上的一个RL,从而存在一个DFA
M
=(Q,δ,F)
Σ,q0,
满足
L(
M
)=
L
041
形式语言与自动机理论(第4版)
取DFA
Q,δ,
显然,对于任意x∈Σ*,
M'=(Σ,q0,Q-F)
δ(q0,x)f∈F.δ(x)=f.Q
=q0,
F
即
x∈L(
M
).x.L(M'
)
这就是说,
L(M')=Σ*-L(
M )
所以,RL 在补运算下是封闭的。定理得以证明。
5-
3
RL 在交运算下封闭。
证明:该定理由定理5-1、定理5-2以及DeMorgan定理可以推得。
对于给定的DFAM1=(Q1,δ1,和DFAM2=(Σ,F2),
Σ,F1) Q2,δ2,如何构造
出DFAM
,使得L(
M
)=L(M1)∩L(M2)呢? 显然,对于一个输入字符串,不可能让其中
一个DFA“先工作”,等它确认该字符串是它接受的句子后,再让另一个DFA 启动。因为,
DFA 并不是2DFA,所以,对一个输入串,不可能进行两次扫描。实际上,可以按照如下思
路去考虑:对Σ*中的任意字符串a1a2…am
,M1 和M2 在处理a1a2…am
的过程中一定分
q01,q02,
别经过状态序列q01,q11,…,qm1和q02,qm2 am
中字符
q12,…,。这两个状态序列依据a1a2…
的出现顺序和相应的移动函数有如图5-3所示的对应关系。根据状态及状态变换的这种对
应关系,就可以知道如何根据M1 和M2 去构造
M
。事实上,对于任意一个输入字符串,所
构造的
M
必须同时能够模拟M1 和M2 对该输入字符串的处理过程。而且要求,对M1 行
为的模拟不应该受到对M2 行为的模拟的影响;反之,对M2 行为的模拟也不应该受到对
M1 行为的模拟的影响。当a1a2…am
是L(中的句子时,有qm1∈F1,
M1)∩L(M2) qm2∈
。当a1a2…am
.L(M1)∩L(M2), 但a1a2…am
∈L(M1)∪L(M2)时,qm1∈F1,
F2 有且仅有一个成立。当a1a2…am
.L(M1)∪L(时,
根据这里的讨论,读者不难给出
M
的详细描述。
M2) qm1.F1 和qm2.F2 同时成立。
F2 qm2∈
图5-
3
M1
和M2
对应于同一个输入串的状态变换过程
上述讨论实际上涉及利用已有的(子)系统去构造一个新系统,按照上述讨论,很容易构
造出DFAM
,使得L(
M
)=L(M1)∪L(M2)。
Q,δ,下面再考虑另外一个问题。对字母表
Σ
上的RLL,令DFAM
=(Σ,F)识别
设δ(a)f(是
Δ
上的一个RL,
q0,
Qa
,
L。对于任意(q,a)∈Q×Σ, q,=p,a) 假定DFAMa
=(
δ,,)识别f()。不妨假设:对a,如果a≠b,则Qa
∩Qb
=.,Qa
∩Q=. 。
Δ,aq0aFa
b∈Σ,
容易构造一个FAMRS,(a) 它的“主框架”是
M
,而它的“分支子模块”为Ma
。如果
M
在状态
q
读入字符
a
时进入状态p,则让MRS 在状态
q
做一个空移动转到Ma
的开始状态q0a
,MRS 在
正则语言的性质
第5章
“分支子模块”Ma 中处理f(a)的句子。当这个句子被处理完后,它一定处在Ma 的某一个
终止状态。从Ma 的每一个终止状态到M 的状态p 引一条标记为ε 的弧,使M RS回到状态
p。如此下去,直到最后到达M 的终止状态。可见,M RS的状态集为Q ∪a∈Σ
Qa ,它的终止状
态即为M 的终止状态集F。从而,有FA
M RS= Q∪a∈Σ
Qa ,Δ,δRS,q0,( F )
使得L(M RS)=f(L)。可见,RL在这种运算下也是封闭的。称这种运算为正则代换。
定义5-2 设Σ,Δ 是两个字母表,映射
f:Σ→2Δ*
称为是从Σ 到Δ 的代换(substitution)。如果对于.a∈Σ,f(a)是Δ 上的RL,则称f 为正
则代换(regularsubstitution)。
先将f 的定义域扩展到Σ* 上,f:Σ* →2Δ*。
(1)f(ε)={ε}。
(2)f(xa)=f(x)f(a)。
再将f 的定义域扩展到2Σ*上,f:2Σ* →2Δ*。对于.L.Σ*,
f(L)=∪x∈Lf(x)
例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* )
定义5-3 设Σ,Δ 是两个字母表,映射
f:Σ→2Δ*
为正则代换,则
(1)f(.)=.。
(2)f(ε)=ε。
(3)对于.a∈Σ,f(a)是Δ 上的正则表达式。
(4)如果r,s 是Σ 上的正则表达式,则
f(r+s)=f(r)+f(s)
f(rs)=f(r)f(s)
f(r* )=f(r)*
141
142
形式语言与自动机理论(第4版)
是
Δ
上的正则表达式。
5-
4
设
L
是
Σ
上的一个RL,f:Σ→2Δ* 是正则代换,则f(L)也是RL 。
证明:前面曾经非形式地简要介绍了根据接受
L
的DFAM
以及接受f(的DFAMa
a)
构造接受f(L)的FA 的思路,有关构造和证明的严格描述请读者给出。在这里,用正则表
达式来进行定理的证明。
使得L(
r=
) L)
因为
L
是RL,则存在正则表达式r, r)L。
下面对
r
中运算符的个数
n
实施归纳,证明f(是表示f(的正则表达式。即
f(L(L(f(
r))=r))
当n=0时,由定义5-2和定义5-3,结论成立。
设当n≤
k
时定理成立,即当
r
中运算符的个数不大于
k
时,L(=f())。当
n=k+1 时有如下3种情况:
f(r))L(
r
(1)r=r1+r2
。
r))
f(L)=f(L(
L(
=f(L(r2)
)
=f(r1+r2))
r1)∪L(正则表达式的定
义
=f(L(L(正则代换的定
义
r1))∪f(r2)
)
=L(f(f(
r1))∪L(r2)) 归纳假
设
=L(r1)+f(正则表达式的定
义
f(r2))
f(正则表达式的正则代换的定
义
=L(f(
(2)r=r1r2。
r)
)
=L(r1+r2))
r)
)
=f(L(r2)
)
f(L)=f(L(
r1
=f(L(L(正则表达式的定
义
r1)r2))
r1))r2)) 正则代换的定义
=f(L(f(L(
=L(f(L(f(归纳假设
r1))r2)
)
=L(f(r1)f(r2)) 正则表达式的定
义
=L(f(r2)) 正则表达式的正则代换的定义
=L(f(
r1
r)
)
(
=
r
*
L。
(
3)r=
1
f(L)f(r)
)
=f(L(1)
)
r
*
L(*) 正则表达式的定
义
=(f(L(* 正则代换的定
义
=f(r1)
r1))
)
=(L(r1))
)
fr(
1)
* 归纳假设
=L(f(*) 正则表达式的定义
=L(f(1)) 正则表达式的正则代换的定义
r
*
=L(r))
f(
所以,结论对n=k+1 成立。由归纳法原理,结论对任意正则表达式成立
。
正则语言的性质
第
定理得到证明。
5
注意,定理5-1可以作为本定理的直接推论。
章
例55
1,Δ={b}
,
f(0)=ab
f(1)=b*
a *
341
f(2)=a+b)
设Σ={0,2},a,正则代换
f
定义为
a
*(
则
(1)f(00)=abab。
(2)f(010)=
b
*
a
* b=ab+a+b。
(3)f((0+1+2)*(a) )(a) =(ab+b*
a
*+
a
*(
a
+b))*=(b*
a
*+
a
*(a+b))*=
a+b)
(4)f(0+1+2)*)=aab+b*+
a
*a+b))*=aa+b)*。
(
(5)
*
f
。
(
0012(
)=
b
*
a
*
a
*
b(a(
+b)=
aab*
+
a
*(a(
+b)。
b(
(6)f(()*(a) =(b+b*
a
*)*=(b+b+a+b*
a
*)*=(*。
0+1)aaa+b)
定义54
设Σ,f:Σ→Δ* y∈Σ*,
有
Δ
是两个字母表,为映射。如果对于.x,
f(x=x)y)
y)f(f(
则称
f
为从
Σ
到Δ*的同态映射(homomorphism )。
对于.L.Σ*,
L
的同态像
f(L)=∪{f(x)}
x∈
L
对于.w.Δ*,
w
的同态原像是一个集合
:
f
-1(w)={x|f(x)=
w
且x∈Σ*
}
对于.L.Δ*,
L
的同态原像是一个集合
:
f
-1(L)={x|f(x)∈L}
例56
设Σ={0,a,
f(0)=aa
1},Δ={b},同态映射
f
定义为
f(1)=aba
则
(1)f(01)=aaaba
。
(2)f((01)*)=(ba)*
。
1(
(3)f-aab)=.。(a) (a) (a) (4)f-1(a)={0}
。a(a) aaa,baaaaaa1,
(5)f-1({a,baaaa,baaa})={100 }
。
(6)f-1((b+ba)* a)={1}
。
(7)f(1(((a) b+b* a))f({={b}
。
f-aa)=1})aa
令L=(ab+ba)* a,上述(7)表明,f(
f
-1(L))≠L。但是,不难证明,对任意语言
L
和同态映射f,
f(
f
-1(L)).
L
注意到同态映射是正则代换的特例,所以有以下推论和定理。