资源描述：
《正则语言和非正则语言》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、语言与计算理论导引正则语言和非正则语言5正则语言和非正则语言5.1判定正则性的一个标准在上一章，Kleene定理给出了正则语言一个有用的特征：即一个语言是（正则表达式定义的）正则语言当且仅当它能够被某个有限自动机接受。也就是，一种通过简单方式产生的语言（简单的初始语言，简单的扩展运算）与一种简单的机器模型（有限的状态数，没有辅助存储空间）对应起来了。我们仍然要问：正则语言的本质特征是什么？为什么它能够被那么简单的运算产生、能够被那么简单的机器识别？我们已经部分地回答了这个问题。定理3.2给出了一个语言成为正则语言的必要条件，或反过
2、来讲，成为非正则语言的充分条件。如果存在无限多个字符串，它们在语言L上两两可区分，那么L不是正则语言。语言L定义了å*上的一个等价关系，如果字符串x和y在L上是不可区分的，则x和y等价。这个等价关系带来了å*上的划分和等价类，因此上面说法可以重新叙述成：如果语言L定义的等价类有无穷多个，则语言L是非正则语言，否则是正则语言。如果等价类是有限的，且能够清楚地描述，则存在一个抽象的方法构造出有限自动机来，而且这种方法构造的自动机具有最少的状态数。上述讨论也隐含指示了存在一种化简有限自动机状态数的方法。定义5.1任给一个语言LÍå*，å
3、*上的不可区分关系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的有限自动机。我们先讨论已知是正则语
4、言的语言L，设接受它的有限自动机是FAM=(Q,å,q0,A,d)，对每个qÎQ，Lq={xÎå*
5、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的合集
6、。特别地，如果Lq的个数与IL的等价类个数相等，则两个划分完全相同，且FAM是接受L的最少状态数的有限自动机。现在增加问题的难度。如果我们知道了一个正则语言，不知道接受它的有限自动机，那么如何找到它呢？在第3章，我们认识到FA中的每个状态q代表在识别字符串过程中需要记住的一定的信息量，状态q表示了一类具有相同判定特征的字符串。这里我们看到IL形成的等价类中的字符串就具有相同的判定信息。因此我们可以用等价类表示状态。字符串x的等价类记为[x]，则转移函数可以写成，d([x],a)=[xa]。引理5.2关系IL对连接运算是右确定的（r
7、ightinvariant）。即对于任意的字符串x、y和字符a，如果xILy，则xaILya。即如果[x]=[y]，则[xa]=[ya]。证明：对于任意的字符串x、y和字符a，只需要证明xaz和yaz要么同时属于L，要么同时不属于L。只需要令z’=az，由于xILy，因此xz’和yz’要么同时属于L，要么同时不属于L。13陶晓鹏Copyright2003语言与计算理论导引正则语言和非正则语言定理5.1任给语言LÍå*，QL是关系IL形成的等价类集合，如果QL是一个有限集，则构造接受L的有限自动机ML=(QL,å,q0,AL,d)如
8、下，q0=[L]，AL={qÎQL
9、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],y
10、a)=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]Ç
