正则语言和非正则语言

语言与计算理论导引 正则语言和非正则语言 陶晓鹏 Copyright 2003 1 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，设接受它的有限自动机是FA M=(Q, , q0, A, )，对每个qQ， Lq={x* | *(q0, x)=q} 从第 1 章内容知道，集合上的等价关系相当于集合上的划分。这里集合*上有两个自然划分，一个是等价关系 IL 形成的划分，另一个是所有的Lq 形成的划分。引理3.1 揭示了这两个划分之间的关系。如果字符串 x 和y 属于同一个Lq（即*(q0, x)=*(q0, y)=q...