正则语言和非正则语言.doc

语言与计算理论导引 正则语言和非正则语言
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, 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的等价类个数相等，则两个划分完全相同，且FA M是接受L的最少状态数的有限自动机。
现在增加问题的难度。如果我们知道了一个正则语言，不知道接受它的有限自动机，那么如何找到它呢？在第3章，我们认识到FA中的每个状态q代表在识别字符串过程中需要记住的一定的信息量，状态q表示了一类具有相同判定特征的字符串。这里我们看到IL形成的等价类中的字符串就具有相同的判定信息。因此我们可以用等价类表示状态。
字符串x的等价类记为[x]，则转移函数可以写成，d ([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。

定理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接受。因此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={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。因此只存在三个等价类。
构造FA ML=(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.3 L是所有合法的、只有一个标识符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章讲述了从正则表达式得到相应的有限自动机的方法，本节将讲述简化有限自动机的方法，或回答是否存在状态数更少的自动机这样的问题。
设FA M=(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-2a FA对应的划分，图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。
更通用的方法是，给定一个FA M，我们判别两个状态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.3 FA的泵引理
每个正则语言都能够被仅有有限状态、无辅助空间的自动机识别，我们能够利用状态的有限性推导出正则语言的另外一些特性。类似推论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<=i<i+p<=n，即
d*(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>=1 and j>=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无法判定一些需要记住超过固定数目信息的实例。单独讨论某个实例是否可判定意义不大，应该讨论更通用的情况。
有限自动机能够解决的通用的判定问题是正则语言的成员资格问题（membership problem），即给定一个字符串x和L，问x是否属于L？这个问题的一个实例就是字符串x。那么对于正则语言的成员资格问题是，给定一个FA M和字符串x，问x是否被M接受（或给定正则语言L和x，x是否属于L）？这个问题的一个实例是二元组(M, x)，解决这个问题的一个方法是将字符串x输入M，观察M最后的停止状态，如果最后停在接受状态，则x被M接受，回答“是”，否则回答“否”。由于M的行动是明确的，并能保证在|x|步给出答案，因此上述方法可视为一个算法。
除了成员资格问题，还有许多与有限自动机和正则语言相关的判定问题，其中一些已经有了判定算法，而有些还没有有效的判定算法。下面是一些判定问题的例子，
1. 给定一个FA M，是否有一个字符串被M接受（或L(M)=f）？
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)是否为f（因为L(M1)ÍL(M2)当且仅当L(M1)-L(M2)= f）。问题4可归结到问题5。有了问题5的算法，则根据第4章的定理，能够发现问题6的算法。
因此仅剩下问题1和问题2没有解决。先看问题1，显然如果一个FA的接受状态集为f，即没有接受状态，那么接受的语言为f，另外，如果FA有接受状态，但是接受状态从初始状态不可到达，那么接受的语言为f。我们可以用下面的递归公式计算FA的可到达状态，

问题1的判定算法 对每个k计算Tk，直到Tk包含一个接受状态或Tk=Tk-1，在前一种情况L(M)¹f，在后一种情况，如果Tk不包含接受状态，则L(M)=f。

如果M的状态数为n，则上面算法至多计算n步。它预示下面的算法也成立。
按照升序检查每个字符，如果在长度<=n的所有字符串中，没有一个被M接受，则L(M)= f。
注意，上面算法可以改进，比如检查完0101100后，在检查01011000，前面的7步不必重复。上面算法的关键是检查的字符串是有限的。

对于问题2，可以利用泵引理，如果一个FA M的状态数是n，且存在一个长度>=n的字符串被接受，则根据泵引理，能够找到无限多个被M接受的字符串。反过来，如果M接受的字符串无限多，则一定存在一个>=n的字符串被接受，更进一步，存在>=n，且<2n的字符串被接受。我们用反证法证明如下。
假设L(M)是无限集，且没有n<=|x|<2n的xÎL(M)，则一定有|x|>=2n的字符串x被M接受，设z是其中最短的字符串，根据泵引理得到，z=uvw，其中|uv|<=n，|v|>0，且uv0w=uw也属于L(M)，|uw|=|uvw|-|v|>=n，且|uw|<|uvw|=|z|，因此要么n<=|uw|<2n，要么2n<=|uw|<|z|，这两种情况都与假设矛盾，因此假设不成立。
有了上面的性质，很容易给出问题2的判定算法。

问题2的判定算法 设FA M的状态数为n，检查所有长度>=n，<=2n的字符串，如果有一个被M接受，则L(M)是无限集，否则是有限集。

至少有两个理由使得我们对这些判定问题的讨论有意义。一是这些解决算法是有用的，比如在考试中，不同的学生画出了不同的识别同一个正则语言的FA，因此需要知道他们是否解答正确。有关问题1的两种解决算法中，前者比后者效率高很多。
除了发现高效算法，另一个原因更有意义。以后我们将看到，不是所有的判定问题都是可解的。在1930年代，数学家图林形式化地表达了一个表述容易但无法用通用方法解决的判定问题。在第9章，我们将研究他提出的通用的抽象机模型，图林机，在两个方面比有限自动机复杂。一方面，图林机能够像有限自动机那样识别语言，他描述的未解问题是在更广泛的语言类上的成员资格问题（参见12.2节）。另一方面，图林机是一种通用的计算模型，我们可以以此为基础，将算法形式化，并精确地定义什么是“未解”。这些问题如此容易描述，反映了计算理论的本质，与计算的效率、采用的物理设备完全无关，本质地反映了计算机、或人类自身的计算能力的极限，极大推动了计算理论的发展。
我们将在以后更深入地研究各种判定问题，但应该记住，许多涉及正则语言的本质问题存在解决的算法。

5.5 正则语言和计算机
在计算机科学领域，术语“语言”常常指的是程序设计语言：C, Pascal等等。现在我们学习了本书最简单的语言，正则语言，那么正则语言与我们熟悉的程序设计语言有什么关系呢？显然，程序设计语言不是正则语言，比如C语言的程序框架为main(){m}m，前面我们已经利用推论5.1或泵引理证明了它不是正则语言。
尽管正则语言描述能力不够丰富，无法将程序设计语言包含进来，但在例子3.5和3.6我们看到正则语言能够用于程序设计语言中。程序设计语言用到的记号包括标识符、文字、运算符、保留字和标点符号。编译用高级程序设计语言写的程序的第一步是词法分析，即识别记号并对其分类。已经存在词法分析器的产生器程序，它的输入是一组描述记号结构的正则表达式，输出对应一个FA的程序，这个程序能够作为一个记号识别模板用于编译器。Lex是目前应用最广泛的词法分析的生成器之一，它是UNIX操作系统提供的一个工具。尽管lex能够用于许多需要处理输入符号结构的情况下，但它最通常的使用方式是与yacc程序一起使用，yacc也是UNIX提供的一个工具。Lex以字符串方式输出一个个记号，yacc根据一组语法规则去确定记号间的语法结构（yacc是yet another compiler compiler的缩写）。正则语言在UNIX系统中还得到其他一些应用，比如UNIX系统提供的文字编辑器允许用户根据正则表达式定义的模式在文本中查寻相应的文字。像grep（global regular expression print）和egrep（extended grep）搜索文本的行是否包含某个正则表达式表示的字符串。
如果正则语言不能是程序设计语言，这预示了有限自动机不能作为现代计算机的抽象模型。两者存在明显的差别，有些差别带来本质性的不同，比如是否带有存储空间，输出能力，以及是否可编程等等。前面已经见到了几个例子，那些语言不能被FA识别，但能够用程序设计语言写出它们的识别程序并在任何一台计算机上运行。
任何一台物理的计算机是一个有限装置，无论它的内存、磁盘，甚至通过网络可及的存储空间总是有限的，我们可以通过描述计算机内容、磁盘的每个数位的值，屏幕上每个像素的值来定义整个计算机的状态。从这个意义上讲，这仍然是一种有限状态的机器，仍然可以用有限自动机来描述。它的输入可以是一串连续的键盘敲击输入，也可以是磁盘文件的输入。因此从这个意义上讲，计算机仍然不能处理类似{0j1j | j>=0}这样的非正则语言。
但通常我们不以这种方式理解计算机，因为这样一种有限仅仅是一组凌乱元素的集合，找不到体现整个集合的规律，反而导致整个集合的复杂和难于使用。
因此我们常常不关心计算机内存的具备空间大小，认为它是足够大，在解决实际问题时，几乎是无限大，这导致它与FA有了根本的区别，因此我们可以编写程序识别类似{0j1j | 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 | d*(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, d)，其中q0=[L]，A_L={qÎQ_L | qÇL¹f}，d: Q_Lxå®Q_L，d([x], a)=[xa]。更进一步可以证明，M_L是接受语言L的最少状态的有限自动机。
证明：即任给字符串xÎL，d*(q0, x)ÎA_L，即要证明d*([L], x)ÎA_L。
先用结构归纳法证明d*([x], y)=[xy]。容易得到字符串y的递归定义，因此对y实施结构归纳法。
1）归纳基础 d*([x], L)=[xL]，显然[xL]=[x]，另外根据d*定义，d*([x], L)=[x]，因此成立。
2）归纳推理 d*([x], ya)= d(d*([x], y), a)= d([xy], a)=[xya]
因此，d*([L], x)=[Lx]=[x]，由于xÎL，显然[x]ÇL¹f，因此[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}不是正则语言。
往往首尾呼应的语言不是正则语言。

5.2 最小有限自动机
定理5.1和推论5.1告诉我们，对于正则语言L，存在状态数目最少的有限自动机。现在要寻找构造识别正则语言的最小有限自动机的形式化方法。第四章提供了工作基础，如何构造识别正则语言的有限自动机，现在只需要找到简化第四章结果的形式化方法。
一种方法是删除不可到达状态法。即如果不存在一个字符串x，使得d*(q0, x)=q，则q称为不可到达状态。容易找到一个递归方法发现所有的可到达状态（作为课后练习），然后删除所有的不可到达状态。
另一种方法是合并状态法。我们从第四章得到的普通有限自动机开始，设法找到等价关系I_L的划分。根据有限自动机的每个状态得到的划分L_q是I_L的划分的细分，因此设法合并L_q，得到I_L的划分，进而得到最小有限自动机。划分的合并等价于状态的合并，因此问题转换成寻找形式化合并状态的方法。
设p和q是有限自动机的两个状态，如果L_p和L_q是I_L的同一个等价类的子集，则称p和q等价，记为pºq，反之，则称p和q不等价，记为pº/q。
引理5.3 状态p和q不等