递归可枚举语言和递归语言.doc

《递归可枚举语言和递归语言.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途10递归可枚举语言和递归语言10.1递归可枚举和递归在本章和后面一章,我们集中讨论图林机识别的语言的外部特征，并且详细研究图林机接受的语言的性质。我们首先形式化说明9.4节提到的图林机接受语言和识别语言的区别。前面讲到,对于图林机T,记号L（Ｔ)表示由导致T停机的字符串组成的语言。定义１0.1ＬÍå＊是一个语言，图林机T的输入字母表是å，如果L＝L(T），则称T接受Ｌ（ａcｃept)。ｘＬ:　å*®｛0，1}是L的特征函数，如果T计算ｘＬ,则称T识别Ｌ或判定L(rｅcoｇniｚｅ,decide）,即å＊上的任意字

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

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

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

5、分，因此Ｔ’在第一个磁带上保存了所有导致崩溃的序列的历史,每当T’完成某个长度,比如n,的所有序列的模拟(如果Ｔ转移的最大可能数是k，则最后一个长度为n的数字串为n个k－１数字组成,比如k＝2，则由ｎ个1组成）,T’搜索第一个磁带看是否所有长度为ｎ的序列都在第一个磁带上，如果是,则找到整数ｎ,擦掉第一个磁带的内容,输出D0;否则继续下一个长度的搜索。下面给出一些判定语言是否是递归可枚举和递归语言的条件。其中一些结果基于构造能够同时模拟其他两个图林机的图林机的方法。定理１0.2如果L1和L2是字母表å上的递归可枚举语言,则L1ÈＬ２和Ｌ１

6、ÇL2也是递归可枚举语言。证明:设接受L1和L2的图林机分别是T1=(Ｑ1，å,G1,　ｑ1,　d１）和T２=(Q2,å,　G个人收集整理勿做商业用途２,q1,d２)，现在分别构造接受Ｌ１ÈＬ2和L1ÇL2的图林机。构造思路与定理3.4的证明很相似，我们引入了２元组状态Ｑ1´Ｑ２,分别跟踪T1和T2的状态转移。我们在前面也讲到,由于PDA的栈的限制,这个方法不能用于PＤA的类似的构造。由于图林机的磁带具有极大的灵活性,我们可以使用2带图林机分别模拟T1和T2的磁带。下面以接受Ｌ1ÈL2的图林机为例说明。T=(Q,å，G,ｑ,d)是一个2

7、带图林机，Q＝Q１´Q２,转移函数如下,d(（p1,ｐ2）,(ａ１,ａ2))=((q1，q2)，（b1，ｂ２),　（D1,D２）)其中,(qi,ｂi,Di)=di(pi,ai),i=１，2。T首先将输入字符串从第一个磁带复制到第二个磁带，并且在两个磁带的左端都插入符号#。Ｔ满足下面的条件:1.T1和T2都不停止，则T不停止;2.Ｔ１和T2至少有一个停机,则T停机；3.如果Ｔ1和T２同时崩溃，则T崩溃;如果其中一个崩溃，则Ｔ放弃这个模拟(忽略相应磁带)，继续模拟另一个，如果它停止在停机或崩溃,则T以相同方式停止。上面的构造使得T停机时当且

8、仅当T１和T２中至少有一个停机，因此能够推断Ｔ接受语言L1ÈL2。语言L1ÇＬ２以相似的方式处理，不同的是,T１和T2中只要有一个崩溃，则T就崩溃,而只有当Ｔ1和T２都停机，T才停机。并集和交集还保持语言的