2022年递归可枚举语言和递归语言 .pdf

《2022年递归可枚举语言和递归语言 .pdf》由会员分享，可在线阅读，更多相关《2022年递归可枚举语言和递归语言 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 1 10 递归可枚举语言和递归语言10.1 递归可枚举和递归在本章和后面一章，我们集中讨论图林机识别的语言的外部特征，并且详细研究图林机接受的语言的性质。我们首先形式化说明9.4 节提到的图林机接受语言和识别语言的区别。前面讲到，对于图林机T，记号 L(T) 表示由导致T 停机的字符串组成的语言。定义 10.1 L*是一个语言，图林机T 的输入字母表是，如果 L=L(T) ，则称T 接受 L（accept）。xL: *0,1 是 L 的特征函数， 如果 T 计算 xL，则称 T 识别 L 或判定 L（recogniz

2、e, decide），即*上的任意字符串x 都能导致T 停机，且如果xL，输出 1，否则输出0。如果存在一个图林机接受语言L，则 L 被称为递归可枚举语言；如果存在一个图林机识别语言 L，则 L 被称为递归语言。显然，每个递归语言都是递归可枚举语言。如果存在一个识别语言L 的图林机T，那么很容易构造接受L 的图林机T ， 只要将输出0 的停机动作修改成进入崩溃的动作就可以了。但是，反过来的命题就比较复杂了。如果T 是接受 L 的图林机，那么可能存在不属于L 的字符串导致T 崩溃，而没有输出结果。本章后面，我们将讨论无法消除这种可能的语言。现在，我们只需要记住上面的部分结论。这个结论还有如下更通

3、用的形式。定理 10.1 如果 L 被一个非确定型图林机T 接受，并且T 上的每一个可能的移动都导致停机或崩溃，则L 是递归语言。证明：我们构造一个三带图林机T ，它是定理9.2 证明中构造的图林机T2的变形。在9.2定理的证明中， T2 模拟图林机T 的每一个可能的有限的移动序列，如果找到一个导致T 停机的序列，T2 则停机， 否则进入无限循环。我们现在需要的图林机必须在两个方面有所不同：首先，如果 T 发现了 T 的一个停机序列， 则 T 在停机之前应该在第一个磁带上输出1；其次的修改更重要，如果 T 上没有停机序列，则T 必须在适当的时机确定这一点，并且在第一个磁带上输出0，然后停机。下

4、面着重说明第二个修改。在定理 9.2 的证明中， T2 利用第二个磁带上的数字串来跟踪移动序列，其中的第i 个数字指示了第 i 步的选择。显然，如果没有发现停机序列，但是发现一个整数n，每个长度为n 的数字串所表示的移动序列都导致崩溃，则可以判定输入字符串不会被接受。因为如果被接受，则存在一个停机序列，如果停机序列长度小于n，则应该在发现n 之前就找到，矛盾；如果停机序列长度大于n，与长度为n 的序列都带来崩溃矛盾。因此问题转换成如何发现n。T 每次模拟完一个T 的导致崩溃的移动序列，将第二个磁带上表示这个移动序列的数字串复制到第一个磁带的空白部分，因此T 在第一个磁带上保存了所有导致崩溃的序

5、列的历史，每当T 完成某个长度，比如n，的所有序列的模拟（如果T 转移的最大可能数是k，则最后一个长度为n 的数字串为n 个 k-1 数字组成，比如k=2，则由 n 个 1 组成）， T 搜索第一个磁带看是否所有长度为n 的序列都在第一个磁带上，如果是，则找到整数n，擦掉第一个磁带的内容，输出0；否则继续下一个长度的搜索。下面给出一些判定语言是否是递归可枚举和递归语言的条件。其中一些结果基于构造能够同时模拟其他两个图林机的图林机的方法。定理 10.2 如果 L1 和 L2 是字母表上的递归可枚举语言，则 L1L2 和 L1L2 也是递归可枚举语言。证明： 设接受 L1 和 L2 的图林机分别是

6、T1=(Q1, , 1, q1, 1)和 T2=(Q2, , 2, q1, 2)，现在分别构造接受L1L2 和 L1L2 的图林机。 构造思路与定理3.4 的证明很相似， 我们引入了2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 2 元组状态 Q1 Q2，分别跟踪T1 和 T2 的状态转移。我们在前面也讲到，由于PDA 的栈的限制，这个方法不能用于

7、PDA 的类似的构造。由于图林机的磁带具有极大的灵活性，我们可以使用2带图林机分别模拟T1 和 T2 的磁带。下面以接受L1L2 的图林机为例说明。T=(Q, , , q, )是一个 2 带图林机， Q= Q1Q2，转移函数如下，(p1,p2), (a1,a2)=(q1,q2), (b1,b2), (D1,D2) 其中， (qi, bi, Di)= i(pi, ai), i=1,2 。T 首先将输入字符串从第一个磁带复制到第二个磁带，并且在两个磁带的左端都插入符号#。T 满足下面的条件：1.T1 和 T2 都不停止，则T 不停止；2.T1 和 T2 至少有一个停机，则T 停机；3.如果 T1

8、和 T2 同时崩溃，则T 崩溃；如果其中一个崩溃，则T 放弃这个模拟（忽略相应磁带），继续模拟另一个，如果它停止在停机或崩溃，则T 以相同方式停止。上面的构造使得T 停机时当且仅当T1 和 T2 中至少有一个停机，因此能够推断T 接受语言L1L2 。语言 L1L2 以相似的方式处理，不同的是， T1 和 T2 中只要有一个崩溃，则T 就崩溃，而只有当 T1 和 T2 都停机， T 才停机。并集和交集还保持语言的递归性，即两个递归语言的并集和交集仍然是递归语言，而且递归语言还保持补集的递归性。定理 10.3 如果 L 是一个递归语言，则补集L 也是递归语言。证明：如果T 是识别 L 的图林机，则

9、只要交换停机时的输出结果，得到的图林机就能识别L 。这个简单的构造证明不适用于递归可枚举语言；练习 9.10 没有明确说明递归可枚举语言的补集不一定是递归可枚举的，但是下面的定理预示了这个结果。定理 10.4 如果 L 是一个递归可枚举语言，它的补集也是递归可枚举语言，那么L 是递归语言。证明：设 T1 和 T2 分别是接受L 和 L 的图林机，我们构造一个2 带图林机接受L，首先利用定理 10.2 构造接受并集的图林机的方法，然后适当修改。我们已经知道，对于任意一个字符串， T1 和 T2 中有且只有一个停机，修改T 如下：当T1 或 T2 停机时， T 也停机，并且擦掉第一个磁带内容，如果

10、是T1 停机，输出1，否则输出0。10.2 枚举一个语言枚举一个集合的含义是逐个列出集合中的元素。因此如果称一个集合是可枚举的，意味着存在一个枚举这个集合的算法。事实上，根据这个思路，我们可以提出递归可枚举语言和递归语言相应的特征。首先，我们精确地描述图林机是如何枚举一个语言的。显然，使用多带图林机更方便，其中一个磁带用于输出枚举结果。定义 10.2 T 是一个 k 带图林机， k=2，语言 L*，如果 T 满足下面的条件，则称T 枚举L：1.第一个磁带的磁带头绝对不会左移；2.在任何时候，第一个磁带的内容形式是，x1#x2#.#xn#y ，其中n=0，每个xiL，且各不相同， y 是 L 的

11、另一个元素的前缀；3.对于每个xL，x 最终作为其中的某个xi 出现在第一个磁带上。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 3 根据上面的定义，如果 L 是一个有限语言，图林机枚举完所有L 中的字符串后， 或者停机，或者继续移动，不会在第一个磁带上打印任何内容；如果L 是一个无限语言，图林机枚举L 的过程不会停止。上面的定义显然是一种合理的形

12、式化“枚举集合元素”这个概念的方法。定义 10.1 说明能够被图林机接受的语言是递归可枚举语言，而这个名称隐含了递归可枚举语言是能够被图林机枚举的语言，证明的思路是简单的，但是详细证明有些繁琐。一方面，如果存在图林机T 枚举语言L，那么给定一个字符串x，我们能够等待观察x 是否在出现在T 的输出结果中，来判断x 属于 L。如果 x 属于 L，上面策略能够保证T 接受 x，如果不属于L，则保证不接受。另一方面，如果T 是接受L 的图林机，为了枚举L，我们先定义字符串的顺序，比如9.6节引入的规范顺序（canonical order），即短字符串先于长的，长度相同的按照字母表顺序。然后，我们根据这

13、个顺序考虑*上的所有字符串，逐个判定字符串x 是否属于 L，比较复杂的问题是， x 可能导致T 无限循环，下面的证明着重解决这个问题。定理 10.5 语言 L*是递归可枚举当且仅当L 能够被图林机枚举。证明：假设T 是枚举 L 的图林机，构造接受L 的图林机 T1 如下。 T1 的磁带比 T 多一个，第一个磁带是增加的那个磁带，作为输入磁带，然后T1 模拟 T，每当符号 #输出在第二个磁带上， T1 暂停，检查新输出的字符串是否与第一个磁带上的输入字符串相同，如果相同，T1 停机，如果不同，继续上面的“枚举-比较”过程。显然，T1 接受且只接受属于L 的字符串。更具体而言， T1 开始完全模仿

14、T 的动作，忽略第一个磁带，直到输出符号#，则只考虑第一个磁带和第二个磁带，忽略其他磁带，如果不匹配，则回到初始格局。反过来，如果T 接受 L，我们构造一个3 带图林机T1 枚举 L。第一个磁带是输出磁带，第二个磁带用于生成*上的每个字符串x，第三个磁带用于模拟T 处理 x 的动作。为了避免前面提到的难点， T1 模拟 T 的越来越长的有限移动序列，而不是试图完成单个字符串的所有移动。因此，第二个磁带不仅保存目前为止的所有生成的所有字符串，而且保存T 处理每个字符串的移动次数。我们采用*上的规范顺序，比如=a,b ，则字符串的生成顺序是，, a, b, aa, ab, ba, bb, aaa,

15、 aab, ., bbb, aaaa, aaab, . T1 做如下的多趟扫描。第一趟扫描，T1 生成字符串，并且模拟T 在这个输入字符串上的一步移动；第二趟扫描，T1 模拟在上的两步移动，并生成a，模拟 T 在 a 上的一步移动；第三趟扫描， T1 模拟在上的三步移动，模拟在a 上的两步移动，生成b，模拟在b 上的一步移动。第 i 趟扫描完成后，第二个磁带的内容的形式如下，1.1.111.111.1121xbaiii其中字符串后面的1 的数目表示T1 处理该字符串所用的步数。x 是规范顺序中的第i 个字符串。在下一趟扫描中，T1 给第二个磁带上的每个字符串增加一个1，即增加一次移动，然后复制

16、到第三个磁带，模拟 T 处理这个输入字符串的规定数目的前面过程，然后擦掉第三个磁带。如果 T 停机， T1 将这个字符串复制到第一个磁带，并添加符号#，第二个磁带上的内容都模拟完后，添加规范顺序中的下一个字符串（次处是x 的下一个字符串）到第二个磁带，并添加一个 1，复制到第三个磁带，然后类似上面的处理。我们没有明确写出T1 完成这些动作需要的簿记装置，但是它们能够很直观地实现，显然每个被 T 接受的字符串最终会出现在T1 的第一个磁带上，且只有这样的字符串出现在上面。定理 10.5 证明的第二部分，应该注意， 尽管*上的字符串按照规范顺序出现在第二个磁带上，但是 L 中的字符串不是按照规范顺

17、序列举在第一个磁带上。如果给予T 更强的假设，我们能够很容易构造出按照规范顺序列举接受字符串的图林机。这个更强的假设是，如果T 不仅接受 L，而且识别L。反过来可以说，如果存在图林机按照规范顺序列举枚举L，则 L 是递归语言。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 4 定理 10.6 L 是递归语言当且仅当存在一个图林机按照规范顺序枚举L。证

18、明：留作练习10.7。练习中还讨论了根据图林机可计算函数得到的一些递归可枚举语言的一些性质。10.3 非递归可枚举语言我们前面讨论的比较简单的计算模型，FA 和 PDA ，能够接受特定类型的语言，发现了一些它们无法接受的语言。对于图林机，我们也要研究是否存在不能接受的语言，但是由于不存在图林机的泵引理，因此图林机的这个问题要难得多。Church-Turing 论题预示了这一点，如果一个想象得到的算法能够被图林机实现，那么它不太可能必须遵循一些相似于FA 和 PDA 泵引理的规律性约束，因为图林机接受语言的能力太灵活了。我们很快将能够展示一个不是递归可枚举的语言。当然，并不是一定先有一个构造性证

19、明说明这种语言一定存在，然后才能讨论这种语言。但是先构造一个这种语言具有下面的好处：首先，证明的梗概很容易从直觉出发得到理解；其次，它表明不仅存在非递归可枚举语言，而且更严格地讲，大多数语言都是非递归可枚举的；第三，它引入了一种特别的方法，“对角线参数法” （diagonal argument），我们在后面章节还会用到这个方法，它是一个很有効的寻找一组特殊参数的方法。方法的思路很简单，如果存在的语言比图林机的个数多得多，那么就一定存在与图林机无关的语言。显然，存在无限多的语言和图林机，因此，为了得到一个精确的论证，我们需要定义一个精确比较两个无限集合大小的方法。说两个有限集合大小相等不困难，如

20、果比较方法得当，它还可以推广到更广泛的情况。为什么说集合 a,b,c 和x,y,z 具有相同的规模？当然，一个原因是它们的元素都是3 个，但是这种方法无法推广到无限集合，因此我们需要的方法是直接比较，而不是具体统计集合元素的个数。一个好的比较上面两个集合的方法是定义一个双射函数，函数定义域是一个集合，值域是另一个集合，这个方法很容易推广到任意的集合上。上面的思想陈述如下：如果存在一个从集合 A 到集合 B 的双射，则称A 和 B 的大小相同。集合的大小相同是一个等价关系（参见练习10.26a），因此具备自反、对称和传递等性质。尽管我们避免象谈论数量那样谈论集合的大小，但是我们希望能够像比较数量

21、那样比较集合的大小。比如说集合p,q,r,s,t 比 a,b,c 大，这是因为两个集合间存在一个一一映射，因此一个集合的大小与另一个集合的子集的大小相等，而集合本身大于或等于它的子集。显然，这个方法也可以推广到无限集合。实际上，不仅存在某些无限集大于另一些无限集，而且无限集有着许多不同的规模（参见练习 10.18 和 10.26）。本节，我们只需要区分两类无限集，一类是与自然数集N 大小相同的无限集，另一类是比自然数集大的无限集。（本文的自然数集包括0）定义 10.3 如果存在一个从自然数集到集合S的双射， 那么集合S 称为可数无限集。如果 S是可数无限集或有限集，那么S 称为可数集，或可数的

22、。一个不可数的集合，称为不可数无限集，或不可数集。说函数 f: NS 是一个双射函数意味着满足下面三个条件：1.对每个自然数n，都有 f(n)S；2.对任意两个不同的自然数m 和 n，f(m)f(n)；3.S 中的每个元素s，都存在一个自然数n，使得 s=f(n)。因此如果说S 是可数无限集，意味着S 中的元素能够以f(0), f(1), . 的方式列举，每个元素只在列表中出现一次，如果S是有限集，则这个列表的长度有限。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11

23、 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 5 存在两种错误理解术语“列举”的情况。第一种，显然不存在实际的、物理意义上的、完全的列举元素，仅仅证明了存在一个函数，对S 中的任意一个元素，都可以利用这个函数在列表中发现该元素；第二种，我们说“列举”，并没有说明一个明确的算法来“列举”，仅仅说明了存在一个双射函数，也没有说明发现或计算这个函数的算法。注意，任意两个可数无限集的大小相同，如果事实上无限集的规模有很多种，那么所有的不可数集不可能是同一个规模，而且任何一个不可数集的规模大于任何一个可数集。这个结论不是很明显，可

24、以从下面的事实推论得到。引理 10.1 每个无限集都有一个可数无限子集。证明：我们证明如果S 是一个无限集，那么存在一个从自然数集N 到 S 的子集的双射f。下面，我们逐个整数定义f 的映射。因为S 是无限集，则至少存在一个元素，选择这个元素，并定义为 f(0)。假设这个过程进行到了第n 步，从 S 中选择了 n 个不同的元素， 分别定义为f(0), f(1), ., f(n) 。由于 S 是无限的， 能够从中选择一个不同于上面n 个元素的元素，称为f(n+1) ，因此根据数学归纳法原理，我们能够在整个n=0 的自然数集上定义f(n)， 而且它是一个一一映射。另一个关于可数集的有用的事实是：可

25、数集的任意子集都是可数集。这个结论很明显，参见练习 10.12。最直接的可数无限集是自然数集本身，容易发现许多其他可数无限集，比如集合S=0, 1/2, 1, 3/2, 2, 5/2, . 是一个可数无限集，因为S=0, 1/2, 2/2, 3/2, 4/2, 5/2, . 它与自然数集存在明显的双射关系。当然，初步观察，S 似乎应该比自然数集N 大，因为S包含了 N 的所有元素，还含有一些其他元素。即存在一个从N 到 S的真子集的双射，如果它们是有限集，显然S 大于 N，但对于无限集，不能得出同样的结论，看起来似乎不符合直接，但它在数学意义上是正确的（参见练习10.13）。对于无限集，可能既

26、存在从一个集合到另一个集合的真子集的双射，也存在到另一个集合自身的双射。下面的结论将给出一大类可数无限集，它的含义是可数个可数集的并集仍然是可数集。定理 10.7 设 S0, S1, .是可数集，那么它们的并集S=0nnS也是可数集。证明：我们假设所有的集合Si 中没有空集（如果需要，可以重新命名），我们描述一种列举这个并集中所有元素的方法。每一行列举一个集合Si，第一行是集合S1，第 i 行是集合 Si，得到一个二维数组如下。其中，由于Si 可以是有限集或无限集，因此每行的长度可能不同，现在考虑图 10-1 所示的一个列举路线。显然，这个路线能够包含进并集S 的每个元素至少一次，如果元素s出

27、现在多个Si 中，则路径将多次包含这个元素。我们定义函数f 如下：f(i)=00_)1(),.,0(_0,0iipaththeoniffSofelementfirstthea则 f 是一个双射函数，如果S 是有限的，是从1.m 到 S的双射函数，否则是从N 到 S 的双射函数。由于有限个可数集的并集knnS0是 S的子集，因此有限个可数集的并集也是可数集。例子 10.1 S=N N 是所有自然数二元对组成的集合，S是可数集。分析：容易根据定理10.7 得到 S 是一个可数集，因为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

28、师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 6 0)(mNmNN而每个集合 mN 都是可数集，因为存在双射函数fm: NmN, fm(n)=(m,n) 。但是我们可以更直接地构造从N 到 N N 的双射函数f，采用类似定理10.7 和图 10-1 的方法。我们先给出它的逆函数f-1，即从 N N 到 N 的函数，也是图10-1 用到的枚举方法。我们再次考察图中的路径，设 j=0， 当路径循回到第j 次， 它命中的二元对(m,n)满足 m+n=j ，共有 j+1

29、 个这样的二元对。特别地，如果当前二元对是(m,n)，m+n=j ，则路径上包含所有(p,q)，p+q=2），如果T 满足下面的条件，则称T 枚举语言 L：第一个磁带的带头没有左移任何时刻，第一个磁带的内容都形如：x1#x2#.#xn#yxiL，各不相同， y 是一个不同于xi 的 L中的元素的前缀。L 中的每个元素，最终都会以某个xi 的形式出现在第一个磁带上。定理 10.5 语言 L 是递归可枚举的当且仅当它能够被某个TM 枚举。证明：？定理 10.6 L 是递归语言当且仅当存在一个TM T 按照 canonical 序枚举它。canonical 序：长度短的优先，如果长度相等，则按字母顺

30、序排列。10.3 不是所有的语言都是递归可枚举的定义 10.3 如果存在一个从集合S 到自然数集N 的双射，则称S 是可数无限集；如果S是有限集或可数无限集，则称S 是可数的；如果S 不是可数的，则称S是不可数无限集。引理 10.1 每个无限集都有一个可数无限的子集。定理 10.7 可数集的并集仍然是可数集。证明：？例子 10.2 对于任何一个有限字母表，*（上的所有字符串组成的集合）是可数集。证明：*=n=0-n 例子 10.3 所有 TM 组成的集合T，以及所有递归可枚举语言组成的集合RE，都是可数的。证明：根据前面对TM 的编码方法，可以构造一个双射函数，e: T0, 1* ，而集合 0

31、, 1* 是可数的，同样可以构造从RE 到 T的双射函数。如果我们能够证明所有语言构成的集合是不可数的，而递归可枚举语言的集合却是可数的，则表明存在不是递归可枚举的语言。定理 10.8 任给一个可数无限集S，则 S 的幂集是不可数无限集。特别地，任给一个非空字母表，则上所有语言组成的集合是不可数的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 10

32、 证明：只要证明自然数集N 的幂集 2-N 是不可数的。反证法。假设 2-N 是可数的，则存在一个从N 到 2-N 的一一映射，则可以表示成2-N=A0, A1, . ，现在定义一个N 的子集， A=iN | iAi ，由于 A 是 N 的一个子集，则存在一个自然数I，使得A=AI ，现在判定自然数I 是否属于A。如果 IA，则 IAI，根据 A 的定义，则IA ，矛盾。如果 IA，则 IAI，根据 A 的定义，则IA ，矛盾。因此，无论我们如何假设I，都会导致矛盾，因此初始假设2-N 是可数的不成立，即2-N 是不可数集。上所有语言组成的集合L是*的幂集，*可数无限集，因此L是不可数集。因此

33、存在不是递归可枚举的语言，即不能被TM 接受的语言。如果所有语言组成的集合相当于实数集，则TM能够处理的语言集合只相当于自然数集。推论 10.1 字母表 0, 1上的非递归可枚举语言组成的集合是不可数的，特别地，字母表0, 1上至少存在一个非递归可枚举语言。证明：根据定理10.8 和 10.7，一个不可数的集合与一个可数集合的差集是不可数的。定理 10.8 证明中，集合A 的定义用到了称为“对角参数”（diagonal argument）的方法。定理10.8 还似乎揭示了存在永远无法处理的语言，TM 可数的原因在于能够被编码成字符串，而能够被编码的原因在于能够被形式化定义，而能够被形式化定义则

34、是能够被计算机处理的必要条件，因此能够被计算机处理的语言一定是可数的，即一定存在无法被计算机处理的语言。10.4 一个不是递归可枚举的语言采用类似定理10.8 中的对角参数法。定义 10.4 非自接受集（not self-accepting） NSA=NSA1NSA2，其中NSA1=w0, 1* | TM T w=e(T) ，且 T 不接受 w NSA2=w0, 1* | TM T we(T) 自接受集 SA（self-accepting）是 NSA 在0, 1* 上的补集，即SA=w0, 1* | TM T w=e(T) ，且 T 接受 w 定理 10.9 语言 NSA 是非递归可枚举的。证

35、明：类似定理10.8，反证法。假设 NSA 是递归可枚举的，则存在一个TM T0 接受 NSA ，即 L(T0)=NSA 。现在判定字符串w0=e(T0) 是否被 T0 接受。如果 w0 不被 T0 接受，根据NSA1 定义， w0 属于 NSA1 ，也属于 NSA ，即 w0L(T0) ，矛盾。如果 w0 被 T0 接受，即w0L(T0)=NSA ，且知 w0=e(T0) ，因此 w0NSA1，则 w0 不被 T0 接受，矛盾。因此假设 NSA 是递归可枚举语言不成立。定理 10.10 语言 SA 是递归可枚举的，但不是递归的。即存在一个TM 接受 SA，但至少存在一个不属于 SA 的字符串

36、导致该TM 无限循环。证明：SA 的非递归性是显然的。如果 SA 是递归的， 则它的补集NSA 也是递归的， 与定理 10.9矛盾，因此SA 是非递归的。下面证明 SA 是递归可枚举的，需要构造一个接受SA 的 TM 。借用万能TM 的构造方法。？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 语言与计算理论导引递归可枚举语言和递归语言陶晓鹏Copyright 2003 11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -