正则语言和非正则语言.docx
《正则语言和非正则语言.docx》由会员分享，可在线阅读，更多相关《正则语言和非正则语言.docx（23页珍藏版）》请在冰点文库上搜索。
正则语言和非正则语言
5正则语言和非正则语言
5.1判定正则性的一个标准
在上一章，Kleene定理给出了正则语言一个有用的特征：
即一个语言是（正则表达式定义的）正则语言当且仅当它能够被某个有限自动机接受。
也就是，一种通过简单方式产生的语言（简单的初始语言，简单的扩展运算）与一种简单的机器模型（有限的状态数，没有辅助存储空间）对应起来了。
我们仍然要问：
正则语言的本质特征是什么？
为什么它能够被那么简单的运算产生、能够被那么简单的机器识别？
我们已经部分地回答了这个问题。
定理3.2给出了一个语言成为正则语言的必要条件，或反过来讲，成为非正则语言的充分条件。
如果存在无限多个字符串，它们在语言L上两两可区分，那么L不是正则语言。
语言L定义了å*上的一个等价关系，如果字符串x和y在L上是不可区分的，则x和y等价。
这个等价关系带来了å*上的划分和等价类，因此上面说法可以重新叙述成：
如果语言L定义的等价类有无穷多个，则语言L是非正则语言，否则是正则语言。
如果等价类是有限的，且能够清楚地描述，则存在一个抽象的方法构造出有限自动机来，而且这种方法构造的自动机具有最少的状态数。
上述讨论也隐含指示了存在一种化简有限自动机状态数的方法。
定义5.1任给一个语言LÍå*，å*上的不可区分关系IL定义如下，任给两个字符串x和y，xILy当且仅当x和y在L上不可区分。
换句话讲，任给字符串z，字符串xz和yz要么同时属于L，要么同时不属于L。
引理5.1任给语言L，IL是å*上的等价关系。
证明：
显然IL是具备自反性和对称性，现在仅证明具备传递性。
假设xILy和yILz，要证明xILz。
任给字符串wÎå*，如果xwÎL，则ywÎL，则zwÎL；类似地，如果xwÏL，则ywÏL，则zwÏL，因此xILz。
我们将发现，如果关系IL的等价类个数有限，则可能根据等价类构造接受语言L的有限自动机。
我们先讨论已知是正则语言的语言L，设接受它的有限自动机是FAM=（Q,å,q0,A,d），对每个qÎQ，
Lq={xÎå*|d*（q0,x）=q}
从第1章内容知道，集合上的等价关系相当于集合上的划分。
这里集合å*上有两个自然划分，一个是等价关系IL形成的划分，另一个是所有的Lq形成的划分。
引理3.1揭示了这两个划分之间的关系。
如果字符串x和y属于同一个Lq（即d*（q0,x）=d*（q0,y）=q），则x和y在关系IL的同一个等价类中。
这意味着（见练习1.41）Lq形成的划分与IL形成的划分相同或是它的细分。
每一个IL形成的等价类都是一个或多个Lq的合集。
特别地，如果Lq的个数与IL的等价类个数相等，则两个划分完全相同，且FAM是接受L的最少状态数的有限自动机。
现在增加问题的难度。
如果我们知道了一个正则语言，不知道接受它的有限自动机，那么如何找到它呢？
在第3章，我们认识到FA中的每个状态q代表在识别字符串过程中需要记住的一定的信息量，状态q表示了一类具有相同判定特征的字符串。
这里我们看到IL形成的等价类中的字符串就具有相同的判定信息。
因此我们可以用等价类表示状态。
字符串x的等价类记为[x]，则转移函数可以写成，d（[x],a）=[xa]。
引理5.2关系IL对连接运算是右确定的（rightinvariant）。
即对于任意的字符串x、y和字符a，如果xILy，则xaILya。
即如果[x]=[y]，则[xa]=[ya]。
证明：
对于任意的字符串x、y和字符a，只需要证明xaz和yaz要么同时属于L，要么同时不属于L。
只需要令z’=az，由于xILy，因此xz’和yz’要么同时属于L，要么同时不属于L。
定理5.1任给语言LÍå*，QL是关系IL形成的等价类集合，如果QL是一个有限集，则构造接受L的有限自动机ML=（QL,å,q0,AL,d）如下，q0=[L]，AL={qÎQL|qÇL¹f}，d:
QL´å®QL定义成d（[x],a）=[xa]。
而且ML是接受语言L的最少状态数的有限自动机。
证明：
根据引理5.2，无疑ML是一个有限自动机。
为了证明ML接受L，只要证明对任意的字符串x和y下式成立：
d*（[x],y）=[xy]
证明可以通过对y实施结构归纳法来完成。
1）归纳基础，d*（[x],L）=[xL]，根据定义3.3知这是显然成立的。
2）归纳推理，设对于任意的x和某个y，d*（[x],y）=[xy]，要证明对任意的字符a，d*（[x],ya）=[xya]。
d*（[x],ya）=d（d*（[x],y）,a）---根据d*的定义
=d（[xy],a）---根据归纳假设
=[xya]---根据d的定义
由于d*（q0,x）=d*（[L],x）=[x]，因此字符串x被ML接受的充分必要条件是[x]ÇL¹f。
如果xÎL，则[x]ÇL¹f，则x被ML接受；如果xÏL，则[x]ÇL=f（如果[x]中存在一个元素y属于L，则违反了y与x的IL关系），则x不被ML接受。
因此FAML是识别语言L的有限自动机。
最后说明ML是接受L的最少状态数的有限自动机。
设IL得到的等价类个数为n，那么从每个等价类各取出一个字符串，它们是两两可区分的，定理3.2揭示了接受L的FA至少需要n个状态，因此接受L的FA不会具有比ML还少的状态。
推论5.1L是正则语言当且仅当关系IL得到的等价类集合是有限集。
证明：
根据定理3.2和5.1立刻得到证明。
推论5.1由Myhill和Nerode证明，因此常常称为Myhill-Nerode定理。
例子5.1考虑例子3.7和3.11中的语言L={xÎ{0,1}*|x以10结尾}。
分析：
考察字符串L、1、10，容易证明它们是两两在L上可区分：
字符串L区分L和10，区分1和10；字符串0区分L和1。
但是对于任意字符串y，y等价于上述三个字符串中的一个：
如果y以10结束，则y等价于10；如果y以1结束，则y等价于1；其他情况下（y=L、y=0、y以00结尾），y等价于L。
因此只存在三个等价类。
构造FAML=（QL,{0,1},{L},{[10]},d）如下。
d（[L],0）=[0]=[L]
d（[L],1）=[1]
d（[1],0）=[10]
d（[1],1）=[11]=[1]
d（[10],0）=[100]=[L]
d（[10],1）=[101]=[1]
参见图5-1，显然它比图3-2所示的相同功能的有限自动机简洁得多。
用来证明回文语言（palindromes）不是正则语言的定理3.2实质上是定理5.1的半部分，即必要条件。
现在我们仍然用这个必要条件展示其他一些非正则语言。
例子5.2语言L={0n1n|n>=0}。
分析：
考虑无限集S={0n|n>=0}，则S中任意两个不同的元素0i和0j（i¹j），能够被字符串1i区分，因为0i1iÎL，而0j1iÏL。
因此关系IL形成无限多个等价类，语言L不是正则语言。
例子5.3L是所有合法的、只有一个标识符a、预算符+、以及左右括号构成的代数表达式组成的语言。
分析：
为了说明L是非正则的，我们忽略表达式中的大部分内容，仅仅关注下面的形式：
（（...（a）...））
它属于L当且仅当左右括号匹配。
类似上例，定义无限集S={（n|n>=0），则S中任意两个不同的元素（i和（j被）i区分。
因此IL形成的等价类有无限多个，L是非正则语言。
例子5.4语言L={ww|wÎ{0,1}*}。
分析：
定义无限集S={0n|n>=0}。
则S中任意两个不同的元素0i和0j（i¹j），能够被字符串1i0i1i区分。
因此L是非正则语言。
练习5.27要求用其他一些无限集来说明语言的非正则性。
例子5.5语言L={0,011,011000,0110001111,...}。
分析：
0和1的连续串交替出现，且长度逐渐增加。
令判定的无限集S=L。
设字符串x、y都属于S，x以0i结尾，y以0j结尾，它们被字符串1i+1区别。
因此IL的等价类有无限多个，L是非正则语言。
5.2最少状态自动机
定理5.1和推论5.1帮助我们理解了一个语言成为正则语言的本质特征。
对于一个正则语言，上一节的定理给出了明确的答案，就是判定算法在每一步应该记住多少信息：
有关字符串本身的信息都可以忘记，只要记住它属于那个IL的等价类。
前面章节，我们反面利用正则语言的性质去发现一些非正则语言。
这一节我们正面使用这些性质化简有限自动机。
例子5.1告诉了通过两两可区分的字符串发现IL的等价类的方法。
然而通常的方法是我们已经有了接受某个语言的自动机，以此为起点找到IL的等价类的方法并不容易。
第4章讲述了从正则表达式得到相应的有限自动机的方法，本节将讲述简化有限自动机的方法，或回答是否存在状态数更少的自动机这样的问题。
设FAM=（Q,å,q0,A,d），我们再次考察两类划分，一类是Lq形成，另一类由IL形成。
如果这两类划分相同，则M已经是最少状态的自动机；否则前一类划分是后一类的细化，可以从此出发找到最少状态的自动机，而不必重新构造自动机。
采用的方法就是合并属于同一个等价类的Lq。
在合并Lq之前，现去除一些冗余的Lq，能够减少一些不必要的状态，对整个å*没有影响。
如果状态q对应的集合Lq=f，即没有一个字符串满足d（q0,x）=q，即从q0无法到达q。
容易构造可到达状态的递归定义，进而构造出发现所有可到达状态的算法。
如果将其余的未到达状态删除不会影响自动机接受的语言。
我们下面的讨论假设这步工作已经完成，自动机中的所有状态都是可到达的。
图5-2a和图5-2b分别显示了例子3.11和例子5.1所构造的有限自动机，它们接受同样的语言，而5-2b状态数要少得多。
图5-2c显示了5-2aFA对应的划分，图5-2d显示了关系IL对应的划分，同时也是对应5-2b的最少状态数FA的划分。
显然我们可以将5-2c的划分进行合并，构造出5-2d的划分。
L1、L2、L4合并成LA，L3、L5、L7合并成LB，L6成为LC。
同时进行相应状态的合并，下一步就可以构造新的转移函数了。
比如从状态1、2和4出发，在输入字符0时，转移到的状态仍在1、2和4之中，因此新的转移函数在输入字符0时，从A转移到A。
从1、2和4中任一个状态，输入字符1时，转移到3、5和7中的一个，因此新转移函数在输入字符1时，从状态A转移到B。
更通用的方法是，给定一个FAM，我们判别两个状态p和q对应的语言Lp和Lq是否是关系IL的同一个等价类的子集。
我们可以通过求解这个问题的反面来解决这个问题，即判别Lp和Lq是否是属于两个不同等价类的语言，记为p¹q。
下面是这种“不等”关系的形式化判别方法。
引理5.3对于p、qÎQ，p¹q当且仅当存在字符串zÎå*，d*（p,z）和d*（q,z）只有一个与A相交不为空。
证明：
设p¹q，则语言Lp和Lq是不同等价类的子集。
分别从Lp和Lq中选取两个字符串x和y，由于x和y属于不同的等价类，即存在一个字符串z区分x和y。
有下面的公式：
d*（p,z）=d*（d*（q0,x）,z）=d*（q0,xz）
d*（q,z）=d*（d*（q0,y）,z）=d*（q0,yz）
d*（q0,xz）和d*（q0,yz）只有一个含有接受状态，因此d*（p,z）和d*（q,z）只有一个与A相交为空。
反过来，如果d*（p,z）和d*（q,z）只有一个与A相交为空，则对任意的字符串xÎLp和yÎLq，字符串z区分x和y，因此x和y在不同的等价类，Lp和Lq是包含于不同等价类的集合，即p¹q。
现在考虑p¹q的条件。
显然如果状态p和q只有一个在A中，则一定有p¹q（此时z=L）；另外，如果两个状态r和s，在输入同样的字符a时，分别到达状态p和q，而且p¹q，则s¹r。
因为存在下面的公式，d*（r,az）=d*（d*（r,a）,z）=d*（p,z）。
由此引出包含满足p¹q的二元组（p,q）的集合S的递归定义：
1.如果p和q只有一个在A中，则（p,q）在S中；
2.如果（p,q）ÎS，存在字符a，使得d（r,a）=p，d（s,a）=q，则（r,s）ÎS;
3.S中的二元组只能由1和2得到。
上面的递归定义保证了S中的所有二元组（p,q），都满足p¹q的条件。
反过来，我们将说明所有满足p¹q的二元组都在S中，使用引理5.3和根据z的长度应用数学归纳法容易证明这一点。
1）归纳基础，|z|=0，即z=L，则S递归定义的声明1保证了所有满足条件：
d（p,L）和d（q,L）只有一个在A中，的二元组（p,q）都在S中。
2）归纳推理，设|z|=k，且所有满足：
d（p,z）和d（q,z）只有一个在A中，的二元组（p,q）都在S中。
则当|z|=k+1，d（p,z）和d（q,z）只有一个在A中，不妨设z=aw，存在公式，
d*（p,aw）=d*（d*（p,a）,w）=d*（r,w）
d*（q,aw）=d*（d*（q,a）,w）=d*（s,w）
则d（r,w）和d（s,w）只有一个在A中，根据归纳假设（r,s）ÎS，根据递归定义的声明2，（p,q）也在S中。
下面将递归定义转换成发现所有满足p¹q的二元组（p,q）的算法。
算法5.1发现所有满足p¹q的二元组（p,q）
1.列出所有的状态对（p,q），其中p、q不相同。
2.遍历状态表，如果二元组中只有一个状态属于A，则该二元组移入到S（或作标记）。
3.反复遍历状态表，直到没有新二元组可加入到S（或没有新标记）。
a）如果存在字符a，使得二元组（r,s），满足d（r,a）=p，d（s,a）=q，且（p,q）ÎS（或被标记），则（r,s）加入到S（或作标记）。
算法5.1结束后，凡是没有加入到S的状态对表示了属于同一个等价类的状态，可以合并。
状态合并后，由前面的例子知道，构造新的转移函数很直观。
下面我们对例子5.1扩展来说明整个过程。
例子5.6化简图5-2a显示的有限自动机。
分析：
将算法5.1用到图5-2a显示的FA，得到表（见图5-3a），表中的数字表示是第几次扫描时标记的。
有了状态的非等价表，就很容易得到等价的状态组合。
对非等价表作一次扫描，容易发现状态1、2、4是等价的。
最后得到关系IL的三个等价类，
p1=L1ÈL2ÈL4，p2=L3ÈL5ÈL7，p3=L6
前面已经显示了新的转移函数的构造方法，化简后的FA如图5-3b所示，它与例子3.11中的FA完全相同，仅仅状态的名字不同。
5.3FA的泵引理
每个正则语言都能够被仅有有限状态、无辅助空间的自动机识别，我们能够利用状态的有限性推导出正则语言的另外一些特性。
类似推论5.1，如果一个语言不具备这些特性，则不是正则语言。
本节提出的方法是比推论5.1更通用，可以应用到更广泛的语言上，在第8章将继续讨论本节的方法。
设M=（Q,å,q0,A,d）是一个FA，接受的语言是L。
我们关注识别路径上出现的回路（循环）。
如果M在识别字符串x的过程中进入某个状态两次，则称为一个回路。
一个直观的观察会发现，在回路上的多次移动，对应的字符串仍然被M接受。
设Q共有n个状态，x是长度大于等于n的字符串，其长度为n的前缀为a1a2...an，记为x=a1a2...any，设x被M接受，则M接受x的前n+1个状态如下，
q0=d*（q0,L）
q1=d*（q0,a1）
...
qn=d*（q0,a1a2...an）
根据鸽笼原理，至少有两个状态相同，即存在一个回路，不妨设qi=qi+p，这里0<=id*（q0,a1a2...ai）=qi
d*（qi,ai+1ai+2...ai+p）=qi
d*（qi,ai+1ai+2...ai+p...any）=qfÎA
令
u=a1a2...ai
v=ai+1ai+2...ai+p
w=ai+1ai+2...ai+p...any
则得到，
d*（q0,u）=qi
（1）
d*（qi,v）=qi
（2）
d*（qi,w）=qf（3）
由
（2）易知，对每个m>=0，下式都成立
d*（qi,vm）=qi
d*（q0,uvmw）=qf
即每个uvmw都被M接受。
定理5.2设L是被一个具有n个状态的FA接受的语言，对每个字符串xÎL，|x|>=n，都可以写成三部分的连接，x=uvw，满足下面三个条件：
|uv|<=n
|v|>0
uvmwÎL
这个定理常常称为泵引理，很形象地说明了正则语言的一个特点。
在正则语言中发现一个足够长的字符串后，就可以在这个字符串中找到具有“泵”一样性质的部分，能够不断地拷贝自身，不断产生新的属于L的字符串。
定理5.2 容易证明，但它的逻辑结构比较复杂，使用中不是很方便。
下面保留定理5.2中最本质的描述，将应用条件弱化，新的表述足够用于大多数情况。
定理5.2a（正则语言的泵引理）L是一个正则语言。
则存在一个整数n，对于所有L中长度大于等于n的字符串x，都存在字符串u、v、w，满足下面的条件：
uvw=x（5.1）
|uv|<=n（5.2）
|v|>0（5.3）
uvmwÎL，m>=0（5.4）
定理5.2a避免了谈论具体的FA，也不关心n的具体值是什么，仅仅关注于存在n这个最本质的特征。
为了说明一个语言不是正则语言，只要说明它不满足泵引理。
通常采用反证法，即先假设一个语言是正则语言，然后说明它不满足泵引理。
定理5.2a的陈述是“存在一个n，对任意的xÎL，|x|>=n，则存在一组字符串，满足...”，写成数学式是，$n（"x（$u,v,w（...）））。
如果应用反证法，则应该是“任给一个n，存在一个xÎL，|x|>=n，任给一组字符串，不满足...”，写成数学式是，"n（$x（"u,v,wù（...）））。
反证法的关键是找到一个特殊的字符串x，但仅仅一个x是不够的，而是要证明在任意的n下，都存在一个x，因此要找的是一组特殊的x，或找到产生这组特殊x的方法（或函数），记为x（n）。
找到x后，不是证明某组u、v、w存在5.1-5.4式的矛盾，而是证明所有的u、v、w不满足5.1-5.4式，因此证明5.1-5.4式本身有矛盾。
例子5.7语言L={0i1i|i>=0}不是正则语言。
分析：
假设L是正则语言，任给一个整数n，存在一个字符串x=0n1n，现在证明找不到满足5.1-5.4式的一组字符串。
假设找到了一组u、v、w满足5.1-5.3。
由5.2式知uv<=n，uv=0k，根据5.3式，v=0j，j>0，则
uvmw=（uv）vm-1w=0k（0j）m-10n-k1n=0n+j（m-1）1nÏL，m>1。
因此u、v、w不满足5.4式。
应该说明，x的选取可以是多样的。
比如上例还可以令x=0m1m，m>=n/2，能够构造出其他矛盾来。
当然，我们尽量选取使得整个证明简单的x。
例子5.8语言L={xÎ{0,1}*}|x含有相同数量的0和1}不是正则语言。
分析：
假设L是正则语言，取x（n）=0n1n，如果存在u、v、w满足5.1-5.4式，则v=0j，j>0，但uvmwÏL，因为0和1的个数不相同。
本例可以看到选择合适的x的重要性，如果选择x=（01）n，很难推导出矛盾。
例子5.9语言L={0ix|i>=0,xÎ{0,1}*and|x|<=i}不是正则语言。
分析：
x（n）=0n1n，则v=0j，但uv0w=0n-j1nÏL。
泵引理还有更弱的形式，下面两种形式省去了定理5.2a的许多结论，但在判定许多语言的非正则性中非常有效。
定理5.3（泵引理的弱形式）设L是一个无限正则语言，则存在字符串u、v、w，|v|>0，且对每个m>=0，uvmwÎL。
证明：
根据定理5.2a，无论存在的n多大，由于L是无限集，则一定存在一个字符串长度大于n，因此能够找到适合的u、v、w。
定理5.3足够用于例子5.7的判定（参见练习5.28），但不能判定例子5.8和5.9。
定理5.4（泵引理的更弱形式）设L是一个无限正则语言，存在整数p和q，q>0，对于每个m>=0，L含有长度为p+mq的字符串。
即整数集lengths（L）={|x||xÎL}包含p+mq的所有算术级数。
证明：
根据定理5.3容易得证，令p=|u|+|w|，q=|v|。
例子5.10语言L={0n|n是素数}是非正则语言。
分析：
根据定理5.4，只需要说明素数集不包含形如{p+mq|m>=0}无限的算术级数，也就是说，存在整数m，p+mq不是素数。
选择m=p，则
p+mq=p+pq=p（1+q）
但不能保证p>=2，不妨令m=p+2q+2，则
p+mq=p+（p+2q+2）q=（p+2q）（1+q）
这显然不是素数。
上面的例子与算术、数字理论更有关系，而不仅仅是一种语言。
后面我们更将看到，许多有关计算的论述可以转变成有关语言的论述。
这个例子也揭示了有限自动机的能力不够强大，无法解决判定一个整数是否是素数这样的问题。
推论5.1给出了一个语言是正则语言的充分条件，定理5.2a给出了必要条件。
我们希望对于每个非正则语言，都能用泵引理证明它的非正则性，证明的技巧仅仅在于选择合适的字符串x。
下面的例子将说明上面的期望是不正确的，既有些非正则语言无法找到导致矛盾的字符串，从而无法应用定理5.2a。
例子5.11语言L={aibjcj|i>=1andj>=0}È{bjck|j,k>=0}是非正则语言。
分析：
当n=1，设xÎL且|x|>=n。
分两种情况讨论。
1.x=aibjcj，i>0，定义u=L，v=a，w=ai-1bjcj。
则每个uvmw仍然形如albjcj，因此属于L。
2.x=bicj，定义u=L，v是x的第一个字符，则每个uvmw（m>=0）属于L。
可见无法应用泵引理去证明L的非正则性，但应用推论5.1容易证明它是非正则语言，证明过程类似例子5.6，参见练习5.29。
5.4判定问题
有限自动机是一种很基本的计算机模型，它接受输入的字符串，输出回答“是”或“否”，即导致有限自动机终止在接受状态或非接受状态。
有限自动机能够解决的计算问题是判定问题，即回答“是”或“否”的问题，比如“给定一个仅含字母a或b的字符串，判定是否含有子串baa”？
说有限自动机仅能解决一些判定问题不是很有意义，导致FA是一种基本的计算模型的事实是Fa无法判定一些需要记住超过固定数目信息的实例。
单独讨论某个实例是否可判定意义不大，应该讨论更通用的情况。
有限自动机能够解决的通用的判定问题是正则语言的成员资格问题（membershipproblem），即给定一个字符串x和L，问x是否属于L？
这个问题的一个实例就是字符串x。
那么对于正则语言的成员资格问题是，给定一个FAM和字符串x，问x是否被M接受（或给定正则语言L和x，x是否属于L）？
这个问题的一个实例是二元组（M,x），解决这个问题的一个方法是将字符串x输入M，观察M最后的停止状态，如果最后停在接受状态，则x被M接受，回答“是”，否则回答“否”。
由于M的行动是明确的，并能保证在|x|步给出答案，因此上述方法可视为一个算法。
除了成员资格问题，还有许多与有限自动机和正则语言相关的判定问题，其中一些已经有了判定算法，而有些还没有有效的判定算法。
下面是一些判定问题的例子，
1.给定一个FAM，是否有一个字符串被M接受（或L（M）=f）？
2.给
升级会员 