正则语言和非正则语言

5 正则语言和非正则语言5.1 判定正则性的一个标准在上一章，Kleene 定理给出了正则语言一个有用的特征：即一个语言是（正则表达式定义的）正则语言当且仅当它能够被某个有限自动机接受。也就是，一种通过简单方式产生的语言（简单的初始语言，简单的扩展运算）与一种简单的机器模型（有限的状态数，没有辅助存储空间）对应起来了。我们仍然要问：正则语言的本质特征是什么？为什么它能够被那么简单的运算产生、能够被那么简单的机器识别？我们已经部分地回答了这个问题。定理 3.2 给出了一个语言成为正则语言的必要条件，或反过来讲，成为非正则语言的充分条件。如果存在无限多个字符串，它们在语言 L 上两两可区分，那么 L 不是正则语言。语言 L 定义了*上的一个等价关系，如果字符串 x 和 y 在 L 上是不可区分的，则 x 和 y 等价。这个等价关系带来了*上的划分和等价类，因此上面说法可以重新叙述成：如果语言 L 定义的等价类有无穷多个，则语言 L 是非正则语言，否则是正则语言。如果等价类是有限的，且能够清楚地描述，则存在一个抽象的方法构造出有限自动机来，而且这种方法构造的自动机具有最少的状态数。上述讨论也隐含指示了存在一种化简有限自动机状态数的方法。定义 5.1 任给一个语言 L*，*上的不可区分关系 IL 定义如下，任给两个字符串 x 和y，xI Ly 当且仅当 x 和 y 在 L 上不可区分。换句话讲，任给字符串 z，字符串 xz 和 yz 要么同时属于 L，要么同时不属于 L。引理 5.1 任给语言 L，I L 是*上的等价关系。证明：显然 IL 是具备自反性和对称性，现在仅证明具备传递性。假设 xILy 和 yILz，要证明 xILz。任给字符串 w*，如果 xwL，则 ywL，则 zwL；类似地，如果 xwL，则ywL，则 zwL，因此 xILz。我们将发现，如果关系 IL 的等价类个数有限，则可能根据等价类构造接受语言 L 的有限自动机。我们先讨论已知是正则语言的语言 L，设接受它的有限自动机是 FA M=(Q, , q0, A, )，对每个 qQ，Lq=x* | *(q0, x)=q从第 1 章内容知道，集合上的等价关系相当于集合上的划分。这里集合*上有两个自然划分，一个是等价关系 IL 形成的划分，另一个是所有的 Lq 形成的划分。引理 3.1 揭示了这两个划分之间的关系。如果字符串 x 和 y 属于同一个 Lq（即 *(q0, x)=*(q0, y)=q） ，则 x 和 y 在关系 IL 的同一个等价类中。这意味着（见练习 1.41）L q 形成的划分与 IL 形成的划分相同或是它的细分。每一个 IL 形成的等价类都是一个或多个 Lq 的合集。特别地，如果 Lq 的个数与 IL的等价类个数相等，则两个划分完全相同，且 FA M 是接受 L 的最少状态数的有限自动机。现在增加问题的难度。如果我们知道了一个正则语言，不知道接受它的有限自动机，那么如何找到它呢？在第 3 章，我们认识到 FA 中的每个状态 q 代表在识别字符串过程中需要记住的一定的信息量，状态 q 表示了一类具有相同判定特征的字符串。这里我们看到 IL 形成的等价类中的字符串就具有相同的判定信息。因此我们可以用等价类表示状态。字符串 x 的等价类记为x，则转移函数可以写成， (x, a)=xa 。引理 5.2 关系 IL 对连接运算是右确定的（right invariant） 。即对于任意的字符串 x、y 和字符 a，如果 xILy，则 xaILya。即如果x=y，则xa=ya 。证明：对于任意的字符串 x、y 和字符 a，只需要证明 xaz 和 yaz 要么同时属于 L，要么同时不属于 L。只需要令 z=az，由于 xILy，因此 xz和 yz要么同时属于 L，要么同时不属于 L。2定理 5.1 任给语言 L*，Q L 是关系 IL 形成的等价类集合，如果 QL 是一个有限集，则构造接受 L 的有限自动机 ML=(QL, , q0, AL, )如下， q0=，A L=qQL | qL， : QLQL 定义成 (x, a)=xa。而且 ML 是接受语言 L 的最少状态数的有限自动机。证明：根据引理 5.2，无疑 ML 是一个有限自动机。为了证明 ML 接受 L，只要证明对任意的字符串 x 和 y 下式成立：*(x, y)=xy证明可以通过对 y 实施结构归纳法来完成。1） 归纳基础，*(x, )=x，根据定义 3.3 知这是显然成立的。2） 归纳推理，设对于任意的 x 和某个 y，*(x,y)=xy，要证明对任意的字符 a， *(x, ya)=xya。*(x, ya)= (*(x, y), a) -根据 *的定义= (xy, a) -根据归纳假设= xya -根据 的定义由于*(q 0, x)=*(, x)=x，因此字符串 x 被 ML 接受的充分必要条件是 xL。如果xL，则 xL，则 x 被 ML 接受；如果 xL，则xL=（如果x中存在一个元素 y 属于L，则违反了 y 与 x 的 IL 关系），则 x 不被 ML 接受。因此 FA ML 是识别语言 L 的有限自动机。最后说明 ML 是接受 L 的最少状态数的有限自动机。设 IL 得到的等价类个数为 n，那么从每个等价类各取出一个字符串，它们是两两可区分的，定理 3.2 揭示了接受 L 的 FA 至少需要n 个状态，因此接受 L 的 FA 不会具有比 ML 还少的状态。推论 5.1 L 是正则语言当且仅当关系 IL 得到的等价类集合是有限集。证明：根据定理 3.2 和 5.1 立刻得到证明。推论 5.1 由 Myhill 和 Nerode 证明，因此常常称为 Myhill-Nerode 定理。例子 5.1 考虑例子 3.7 和 3.11 中的语言 L=x0, 1* | x 以 10 结尾。分析：考察字符串、1、10，容易证明它们是两两在 L 上可区分：字符串区分和 10，区分 1 和 10；字符串 0 区分和 1。但是对于任意字符串 y，y 等价于上述三个字符串中的一个：如果 y 以 10 结束，则 y 等价于 10；如果 y 以 1 结束，则 y 等价于 1；其他情况下（y= 、y=0、 y 以 00 结尾），y 等价于。因此只存在三个等价类。构造 FA ML=(QL, 0, 1, , 10, )如下。(, 0)=0=(, 1)= 1(1, 0)= 10(1, 1)= 11=1(10, 0)=100=(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（ij），能够被字符串 1i 区分，因为 0i1iL，而 0j1iL。因此关系 IL 形成无限多个等价类，语言 L 不是正则语言。语言与计算理论导引 正则语言和非正则语言陶晓鹏 Copyright 2003 3例子 5.3 L 是所有合法的、只有一个标识符 a、预算符+、以及左右括号构成的代数表达式组成的语言。分析：为了说明 L 是非正则的，我们忽略表达式中的大部分内容，仅仅关注下面的形式：(.(a).)它属于 L 当且仅当左右括号匹配。类似上例，定义无限集 S=(n | n=0)，则 S 中任意两个不同的元素( i 和( j 被) i 区分。因此 IL 形成的等价类有无限多个，L 是非正则语言。例子 5.4 语言 L=ww | w0, 1*。分析：定义无限集 S=0n | n=0。则 S 中任意两个不同的元素 0i 和 0j（ij），能够被字符串 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 章讲述了从正则表达式得到相应的有限自动机的方法，本节将讲述简化有限自动机的方法，或回答是否存在状态数更少的自动机这样的问题。设 FA M=(Q, , q0, A, )，我们再次考察两类划分，一类是 Lq 形成，另一类由 IL 形成。如果这两类划分相同，则 M 已经是最少状态的自动机；否则前一类划分是后一类的细化，可以从此出发找到最少状态的自动机，而不必重新构造自动机。采用的方法就是合并属于同一个等价类的 Lq。在合并 Lq 之前，现去除一些冗余的 Lq，能够减少一些不必要的状态，对整个*没有影响。如果状态 q 对应的集合 Lq=，即没有一个字符串满足 (q0, x)=q，即从 q0 无法到达 q。容易构造可到达状态的递归定义，进而构造出发现所有可到达状态的算法。如果将其余的未到达状态删除不会影响自动机接受的语言。我们下面的讨论假设这步工作已经完成，自动机中的所有状态都是可到达的。图 5-2a 和图 5-2b 分别显示了例子 3.11 和例子 5.1 所构造的有限自动机，它们接受同样的语言，而 5-2b 状态数要少得多。图 5-2c 显示了 5-2a FA 对应的划分，图 5-2d 显示了关系 IL 对应的划分，同时也是对应 5-2b 的最少状态数 FA 的划分。显然我们可以将 5-2c 的划分进行合并，构造出 5-2d 的划分。L 1、L 2、L 4 合并成 LA，L 3、L 5、L 7 合并成 LB，L 6 成为 LC。同时进行相应状态的合并，下一步就可以构造新的转移函数了。比如从状态 1、2 和 4 出发，在输入字符 0 时，转移到的状态仍在 1、2 和 4 之中，因此新的转移函数在输入字符 0 时，从 A 转移到 A。从 1、2 和 4 中任一个状态，输入字符 1 时，转移到 3、5 和 7 中的一个，因此新转移函数在输入字符 1 时，从状态 A 转移到 B。4更通用的方法是，给定一个 FA M，我们判别两个状态 p 和 q 对应的语言 Lp 和 Lq 是否是关系 IL 的同一个等价类的子集。我们可以通过求解这个问题的反面来解决这个问题，即判别Lp 和 Lq 是否是属于两个不同等价类的语言，记为 pq。下面是这种“不等”关系的形式化判别方法。引理 5.3 对于 p、qQ，pq 当且仅当存在字符串 z*，*(p, z)和 *(q, z)只有一个与 A相交不为空。证明：设 pq，则语言 Lp 和 Lq 是不同等价类的子集。分别从 Lp 和 Lq 中选取两个字符串 x 和 y，由于 x 和 y 属于不同的等价类，即存在一个字符串 z 区分 x 和 y。有下面的公式：*(p, z) = *(*(q0, x), z) =*(q0, xz)*(q, z) = *(*(q0, y), z) =*(q0, yz)*(q0, xz)和*(q0, yz)只有一个含有接受状态，因此 *(p, z)和*(q, z)只有一个与 A 相交为空。反过来，如果*(p, z)和*(q, z)只有一个与 A 相交为空，则对任意的字符串 xLp 和yLq，字符串 z 区分 x 和 y，因此 x 和 y 在不同的等价类， Lp 和 Lq 是包含于不同等价类的集合，即 pq。现在考虑 pq 的条件。显然如果状态 p 和 q 只有一个在 A 中，则一定有 pq（此时 z=）；另外，如果两个状态 r 和 s，在输入同样的字符 a 时，分别到达状态 p 和 q，而且 pq，则sr。因为存在下面的公式， *(r, az) = *(*(r, a), z) =*(p, z)。由此引出包含满足 pq 的二元组(p, q)的集合 S 的递归定义：1. 如果 p 和 q 只有一个在 A 中，则(p, q)在 S 中；2. 如果(p, q) S，存在字符 a，使得(r, a)=p，(s, a)=q，则(r, s)S;3. S 中的二元组只能由 1 和 2 得到。上面的递归定义保证了 S 中的所有二元组(p, q)，都满足 pq 的条件。反过来，我们将说明所有满足 pq 的二元组都在 S 中，使用引理 5.3 和根据 z 的长度应用数学归纳法容易证明这一点。1）归纳基础，|z|=0 ，即 z=，则 S 递归定义的声明 1 保证了所有满足条件：(p, )和(q, )只有一个在 A 中，的二元组 (p, q)都在 S 中。2）归纳推理，设|z|=k ，且所有满足： (p, z)和 (q, z)只有一个在 A 中，的二元组(p, q)都在S 中。则当|z|=k+1 ，(p, z)和(q, z)只有一个在 A 中，不妨设 z=aw，存在公式，*(p, aw) = *(*(p, a), w) =*(r, w)*(q, aw) = *(*(q, a), w) =*(s, w)则(r, w)和(s, w)只有一个在 A 中，根据归纳假设(r, s)S，根据递归定义的声明 2，(p, q)也在 S 中。下面将递归定义转换成发现所有满足 pq 的二元组(p, q) 的算法。算法 5.1 发现所有满足 pq 的二元组(p, q)1. 列出所有的状态对(p, q)，其中 p、q 不相同。2. 遍历状态表，如果二元组中只有一个状态属于 A，则该二元组移入到 S（或作标记）。3. 反复遍历状态表，直到没有新二元组可加入到 S（或没有新标记）。a) 如果存在字符 a，使得二元组(r, s)，满足(r, a)=p，(s, a)=q，且(p, q)S（或被标记），则(r, s) 加入到 S（或作标记）。算法 5.1 结束后，凡是没有加入到 S 的状态对表示了属于同一个等价类的状态，可以合并。语言与计算理论导引 正则语言和非正则语言陶晓鹏 Copyright 2003 5状态合并后，由前面的例子知道，构造新的转移函数很直观。下面我们对例子 5.1 扩展来说明整个过程。例子 5.6 化简图 5-2a 显示的有限自动机。分析：将算法 5.1 用到图 5-2a 显示的 FA，得到表（见图 5-3a），表中的数字表示是第几次扫描时标记的。有了状态的非等价表，就很容易得到等价的状态组合。对非等价表作一次扫描，容易发现状态 1、2、4 是等价的。最后得到关系 IL 的三个等价类，p1=L1L2L4，p2=L3L5L7，p3=L6前面已经显示了新的转移函数的构造方法，化简后的 FA 如图 5-3b 所示，它与例子 3.11中的 FA 完全相同，仅仅状态的名字不同。5.3 FA 的泵引理每个正则语言都能够被仅有有限状态、无辅助空间的自动机识别，我们能够利用状态的有限性推导出正则语言的另外一些特性。类似推论 5.1，如果一个语言不具备这些特性，则不是正则语言。本节提出的方法是比推论 5.1 更通用，可以应用到更广泛的语言上，在第 8 章将继续讨论本节的方法。设 M=(Q, , q0, A, )是一个 FA，接受的语言是 L。我们关注识别路径上出现的回路（循环）。如果 M 在识别字符串 x 的过程中进入某个状态两次，则称为一个回路。一个直观的观察会发现，在回路上的多次移动，对应的字符串仍然被 M 接受。设 Q 共有 n 个状态，x 是长度大于等于 n 的字符串，其长度为 n 的前缀为 a1a2.an，记为x=a1a2.any，设 x 被 M 接受，则 M 接受 x 的前 n+1 个状态如下，q0=*(q0, )q1=*(q0, a1).qn=*(q0, a1a2.an)根据鸽笼原理，至少有两个状态相同，即存在一个回路，不妨设 qi=qi+p，这里0=0，下式都成立*(qi, vm)=qi*(q0, uvmw)=qf即每个 uvmw 都被 M 接受。定理 5.2 设 L 是被一个具有 n 个状态的 FA 接受的语言，对每个字符串 xL，|x|=n，都可以写成三部分的连接，x=uvw，满足下面三个条件：|uv|0uvmwL这个定理常常称为泵引理，很形象地说明了正则语言的一个特点。在正则语言中发现一个足够长的字符串后，就可以在这个字符串中找到具有“泵”一样性质的部分，能够不断地拷贝自身，不断产生新的属于 L 的字符串。定理 5.2 容易证明，但它的逻辑结构比较复杂，使用中不是很方便。下面保留定理 5.2 中最本质的描述，将应用条件弱化，新的表述足够用于大多数情况。定理 5.2a （正则语言的泵引理）L 是一个正则语言。则存在一个整数 n，对于所有 L 中长度大于等于 n 的字符串 x，都存在字符串 u、v、w ，满足下面的条件：uvw=x (5.1)|uv|0 (5.3)uvmwL，m=0 (5.4)定理 5.2a 避免了谈论具体的 FA，也不关心 n 的具体值是什么，仅仅关注于存在 n 这个最本质的特征。为了说明一个语言不是正则语言，只要说明它不满足泵引理。通常采用反证法，即先假设一个语言是正则语言，然后说明它不满足泵引理。定理 5.2a 的陈述是“存在一个 n，对任意的 xL，|x|=n ，则存在一组字符串，满足.”，写成数学式是，n(x( u,v,w (.)。如果应用反证法，则应该是“任给一个 n，存在一个xL，|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 式知 uv0 ，则uvmw=(uv)vm-1w=0k(0j)m-10n-k1n=0n+j(m-1)1nL，m1 。因此 u、v、w 不满足 5.4 式。应该说明，x 的选取可以是多样的。比如上例还可以令 x=0m1m，m=n/2 ，能够构造出其他矛盾来。当然，我们尽量选取使得整个证明简单的 x。例子 5.8 语言 L=x0, 1* | x 含有相同数量的 0 和 1不是正则语言。分析：假设 L 是正则语言，取 x(n)=0n1n，如果存在 u、v 、w 满足 5.1-5.4 式，则v=0j，j0，但 uvmwL，因为 0 和 1 的个数不相同。本例可以看到选择合适的 x 的重要性，如果选择 x=(01)n，很难推导出矛盾。例子 5.9 语言 L=0ix | i=0, x0, 1* and |x|0 ，语言与计算理论导引 正则语言和非正则语言陶晓鹏 Copyright 2003 7且对每个 m=0，uv mwL。证明：根据定理 5.2a，无论存在的 n 多大，由于 L 是无限集，则一定存在一个字符串长度大于 n，因此能够找到适合的 u、v、w 。定理 5.3 足够用于例子 5.7 的判定（参见练习 5.28），但不能判定例子 5.8 和 5.9。定理 5.4（泵引理的更弱形式）设 L 是一个无限正则语言，存在整数 p 和 q，q0，对于每个 m=0，L 含有长度为 p+mq 的字符串。即整数集 lengths(L)=|x| | xL包含 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=1 and j=0bjck | j, k=0是非正则语言。分析：当 n=1，设 xL 且|x|=n。分两种情况讨论。1. x=aibjcj，i0，定义 u=，v=a，w=a i-1bjcj。则每个 uvmw 仍然形如 albjcj，因此属于L。2. x=bicj，定义 u=，v 是 x 的第一个字符，则每个 uvmw（m=0）属于 L。可见无法应用泵引理去证明 L 的非正则性，但应用推论 5.1 容易证明它是非正则语言，证明过程类似例子 5.6，参见练习 5.29。5.4 判定问题有限自动机是一种很基本的计算机模型，它接受输入的字符串，输出回答“是”或“否”，即导致有限自动机终止在接受状态或非接受状态。有限自动机能够解决的计算问题是判定问题，即回答“是”或“否”的问题，比如“给定一个仅含字母 a 或 b 的字符串，判定是否含有子串 baa”？说有限自动机仅能解决一些判定问题不是很有意义，导致 FA 是一种基本的计算模型的事实是 Fa 无法判定一些需要记住超过固定数目信息的实例。单独讨论某个实例是否可判定意义不大，应该讨论更通用的情况。有限自动机能够解决的通用的判定问题是正则语言的成员资格问题（membership problem），即给定一个字符串 x 和 L，问 x 是否属于 L？这个问题的一个实例就是字符串 x。8那么对于正则语言的成员资格问题是，给定一个 FA M 和字符串 x，问 x 是否被 M 接受（或给定正则语言 L 和 x，x 是否属于 L）？这个问题的一个实例是二元组(M, x)，解决这个问题的一个方法是将字符串 x 输入 M，观察 M 最后的停止状态，如果最后停在接受状态，则 x 被 M 接受，回答“是”，否则回答“否”。由于 M 的行动是明确的，并能保证在|x|步给出答案，因此上述方法可视为一个算法。除了成员资格问题，还有许多与有限自动机和正则语言相关的判定问题，其中一些已经有了判定算法，而有些还没有有效的判定算法。下面是一些判定问题的例子，1. 给定一个 FA M，是否有一个字符串被 M 接受（或 L(M)=）？2. 给定一个 FA M，L(M) 是否是有限集？3. 给定两个 FA M1 和 M2，是否存在同时被 M1 和 M2 接受的字符串？4. 给定两个 FA M1 和 M2，它们是否接受同样的语言（或 L(M1)=L(M2)）？5. 给定两个 FA M1 和 M2，L(M1) 是否是 L(M2)的子集？6. 给定两个正则表达式 r1 和 r2，它们是否对应相同的语言？7. 给定一个 FA M，M 是否是接受 L(M)的最少状态的 FA？5.2 节已经给出了问题 7 的判定算法，将 FA 的最简化算法应用到 M，观察状态数是否减少了。其他 6 个问题中，有些相互关联，比如如果我们有了问题 1 的判定算法，我们可以构造解决问题 3 到问题 6 的判定算法。对于问题 3，首先应用 3.5 节给出的算法构造接受 L(M1)L(M2)的有限自动机 M，然后将问题 1 的算法应用到 M 上。问题 5 可类似解决，先构造接受L(M1)-L(M2)的有限自动机 M，然后判定 L(M)是否为（因为 L(M1)L(M2)当且仅当 L(M1)-L(M2)= ）。问题 4 可归结到问题 5。有了问题 5 的算法，则根据第 4 章的定理，能够发现问题 6 的算法。因此仅剩下问题 1 和问题 2 没有解决。先看问题 1，显然如果一个 FA 的接受状态集为，即没有接受状态，那么接受的语言为，另外，如果 FA 有接受状态，但是接受状态从初始状态不可到达，那么接受的语言为。我们可以用下面的递归公式计算 FA 的可到达状态，0|),(1100 kaTqaTkk问题 1 的判定算法 对每个 k 计算 Tk，直到 Tk 包含一个接受状态或 Tk=Tk-1，在前一种情况 L(M)，在后一种情况，如果 Tk 不包含接受状态，则 L(M)=。如果 M 的状态数为 n，则上面算法至多计算 n 步。它预示下面的算法也成立。按照升序检查每个字符，如果在长度=n 的字符串被接受，则根据泵引理，能够找到无限多个被 M 接受的字符串。反过来，如果 M 接受的字符串无限多，则一定存在一个=n 的字符串被接受，更进一步，存在 =n，且=2n 的字符串 x 被 M 接受，设 z 是其中最短的字符串，根据泵引理得到，z=uvw，其中|uv|0 ，且 uv0w=uw 也属于 L(M)，|uw|=|uvw|-|v|=n，且|uw|=n ，=0这样的非正则语言。但通常我们不以这种方式理解计算机，因为这样一种有限仅仅是一组凌乱元素的集合，找不到体现整个集合的规律，反而导致整个集合的复杂和难于使用。10因此我们常常不关心计算机内存的具备空间大小，认为它是足够大，在解决实际问题时，几乎是无限大，这导致它与 FA 有了根本的区别，因此我们可以编写程序识别类似0 j1j | j=0这样的语言。随着本书内容的展开，我们将引入更接近现代计算机的抽象模型，它们不是现代计算机的完美的物理模型，但研究这些概念模型仍然是目前理解现代计算机能力和局限的最好途径。- END -Kleene 定理给出了一个正则语言的标准，即能够被有限自动机识别的语言就是正则语言。而我们知道有限自动机是一种很简单的机器，因此正则语言也是很简单的机器，但我们想知道为什么正则语言如此简单，它的本质特征是什么呢？定理 3.2 揭示了正则语言的部分本质特征和成为正则语言的必要条件。我们可进一步发展定理 3.2。称两个字符串相等，如果它们在语言 L 上是不可区分的。这是一个等价关系，因此语言 L 的不可区分性导出许多等价类，*上的每个字符串属于且只属于某个等价类。根据定理 3.2，如果 L 的不可区分性导出的等价类有无穷多，则 L 不是正则语言（需要无限自动机去识别）；反之，如果等价类有限，则 L 是正则语言。最优的自动机应该有尽可能少的状态，上面的讨论既提供了获得自动机的抽象方法，又提供了减少状态数，优化自动机的方法。定义 5.1 对于语言 L，关系 I_L 定义为，任给字符串 x 和 y，xI_Ly 当且仅当 x 和 y 在语言 L上是不可区分的。即任给字符串 z，连接得到的新字符串 xz 和 yz 要么都在语言 L 中，要么都不在语言 L 中。引理 5.1 对于任何一个语言 L（注意，不仅仅是正则语言），I_L 都是*上的等价关系。如果我们知道了一个正则语言 L，则很容易构造关系 I_L。根据 L 对应的有限自动机，先得到*上的一个划分，L_q=x | *(q0, x)=q。根据这个划分，得到一个等价关系，这个等价关系等同于 I_L，或是 I_L 的细分。引理 5.2 关系 I_L 对连接运算具有右不变性（right invariant），即对任何字符串 x 和 y，字符a，如果 xI_Ly，则 xaI_Lya，即如果x=y，则xa=ya。定理 5.1 对于语言 L，如果 Q_L 是全集*上的一个划分，并且是有限集，则可以构造接受语言 L 的有限自动机如下：M_L=(Q_L, , q0, A_L, )，其中 q0=，A_L=q Q_L | qL， : Q_LxQ_L， (x, a)=xa。更进一步可以证明，M_L 是接受语言 L 的最少状态的有限自动机。证明：即任给字符串 xL，*(q0, x)A_L ，即要证明*( , x)A_L。先用结构归纳法证明*(x, y)=xy。容易得到字符串 y 的递归定义，因此对 y 实施结构归纳法。1）归纳基础 *(x, )=x，显然x=x，另外根据 *定义，*(x, )=x，因此成立。2）归纳推理 *(x, ya)= (*(x, y), a)= (xy, a)=xya因此，*(, x)=x=x，由于 xL，显然xL，因此x A_L，因此 x 被 M_L 接受。另外，如果 Q_L 的元素数为 n，则 L 至少有 n 个可区分的字符串，根据定理 3.2 容易得到接受L 的有限自动机至少有 n 个状态，因此 M_L 是状态数最少的接受 L 的有限自动机。推论 5.1（也称 Myhill-Nerode 定理）L 是正则语言当且仅当关系 I_L 的等价类是有限的。139 页例子 5.2 说明了如何利用定理 5.1 和推论 5.1 证明 L=0-n1-n | n=0不是正则语言。往往首尾呼应的语言不是正则语言。语言与计算理论导引 正则语言和非正则语言陶晓鹏 Copyright 2003 115.2 最小有限自动机定理 5.1 和推论 5.1 告诉我们，对于正则语言 L，存在状态数目最少的有限自动机。现在要寻找构造识别正则语言的最小有限自动机的形式化方法。第四章提供了工作基础，如何构造识别正则语言的有限自动机，现在只需要找到简化第四章结果的形式化方法。一种方法是删除不可到达状态法。即如果不存在一个字符串 x，使得*(q0, x)=q，则 q 称为不可到达状态。容易找到一个递归方法发现所有的可到达状态（作为课后练习），然后删除所有的不可到达状态。另一种方法是合并状态法。我们从第四章得到的普通有限自动机开始，设法找到等价关系 I_L的划分。根据有限自动机的每个状态得到的划分 L_q 是 I_L 的划分的细分，因此设法合并L_q，得到 I_L 的划分，进而得到最小有限自动机。划分的合并等价于状态的合并，因此问题转换成寻找形式化合并状态的方法。设 p 和 q 是有限自动机的两个状态，如果 L_p 和 L_q 是 I_L 的同一个等价类的子集，则称 p和 q 等价，记为 pq，反之，则称 p 和 q 不等价，记为 p/q。引理 5.3 状态 p 和 q 不等价，当且仅当，存在字符串 z，*(p, z)和*(q, z) 只有一个在 A 中。递归定义关系 S，由不等价的状态对(p, q)组成：1）任给状态 p 和 q，如果只有一个在 A 中，则(p, q)S。2）任给状态 r 和 s，如果存在字符 a，使得 (r, a)=p，(s, a)=q，且(p, q) S，则(r, s)S。3）S 中没有其他的状态对。算法 5.1 递归计算 S。列出所有的状态对（一般采用三角形，见 142 页例子 5.6），依序逐个扫描状态对，根据上述两个规则判断是否属于 S，如果是则作标记。当一趟扫描结束后，没有增加状态对，则计算停止。计算结束后，没有标记的状态对则是等价状态，因此可以合并。状态合并后的转移函数的合并相对简单。5.3 泵引理由于有限自动机的状态数是有限的，不妨设为 n，当它识别一个长度大于 n 的字符串时，所得到的转移状态链上必定有重复的状态，即状态链上存在回路（根据鸽笼原理）。而且回路无论重复多少次不会影响字符串最后的接受状态，因此不会影响字符串的识别。定理 5.2 L 是状态数为 n 的 FA 识别的正则语言，则对于任何长度大于 n 的 L 中的字符串 x，可以由三个字符串连接而成，即 x=uvw，它们满足下列条件：1）|uv| 03）uv-mw L， m=0字符串 x 中的 v 部分，仿佛是不断涌动的泵，可以产生许多新的 L 中的字符串。定理 5.2 可以简化，以便使用。定理 5.2a（泵引理）L 是一个正则语言，则存在一个正整数 n，对于 L 中任何长度=n 的字符串 x，存在三个字符串 u、v、w ，满足下面条件：1）x=uvw2）|