形式语言与自动机

1计算理论2前言在第4章已经确定采用图灵机作为通用计算器机的模型，并介绍了几个在图灵机上可解的问题，还给出了一个计算机不可解的问题，即ATM。本章讨论另外几个不可解的问题。在讨论过程中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。3前言例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。可归约性总是涉及两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。在上述例子中，A是城市认路问题，B是得到地图问题。注意，可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。4主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性5.3.1可计算函数5.3.2映射可归约性的形式定义5语言理论中的不可判定问题ATM是不可判定的，即确定个图灵机是否接受一个给定的输入问题是不可判定的。下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。若将ATM归约到HALTTM，就可以利用ATM的不可判定性证明HALTTM的不可判定性。设:HALTTM={M,w|M是一个TM,且对输入w停机}6语言理论中的不可判定问题定理5.1HALTTM是不可判定的。为得到矛盾，假设TMR判定HALTTM，由之可以构造TMS来判定ATM,其构造如下：S=“在输入M，w上，此处M，w是TMM和串w的编码：1)在输入M，w上运行TMR。2)如果R拒绝，则拒绝。3)如果R接受，则在w上模拟M，直到它停机。4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的，故HALTTM也必定是不可判定的。反证法，假设可判定，证明ATM是可判定的。7语言理论中的不可判定问题定理5.2ETM是不可判定的。先用标准术语来写在证明思路中描述的那上修改型机器M1.M1=“在输入x上：1)如果x≠w，则拒绝。2)如果x=w，则在x上运行M，当M接受时，就接受。”这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很显然，即扫描输入并用一个字符一个字符地将它与w进行比较，就可确定它们是否相同。反证法，假设可判定，证明ATM是可判定的。除w外M1拒绝所有串8语言理论中的不可判定问题再假设TMR判定ETM。如下构造判定ATM的TMS:S=“在输入M，w上，此处M，w是TMM和串w的编码：1)用M和w的描述来构造上述TMM1。2)在输入M1上运行R。3)如果R接受，则拒绝；如果R拒绝，则接受。”不空，M接受w说明L(M1)是空集，因此M1不接受w9语言理论中的不可判定问题另一个与图灵机有关的计算问题也很有意思，该问题是：给定一个图灵机和一个可由某个更简单的计算模型识别的语言，测定此图灵机是否识别此语言。例如：令REGULARTM是测定一个给定的图机是否有一个与之等价的有穷自动机问题，则这个问题与测定一个给定的图灵机是否识别一个与此正则语言的问题相同。设：REGULARTM={M|M是一个TM，且L(M)是一个正则语言}10语言理论中的不可判定问题定理5.3REGULARTM是不可判定的。设R是判定REGULARTM的一个TM，下面构造判定ATM的TMS。S的运行方式如下：S=“对于输入M，w，其中M是TM，w是串：1)构造下述TMM2：M2=“在输入x上：a)如果x具有形式0n1n，则接受。b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。”2)在输入M2上运行R。3)如果R接受，则接受；如果R拒绝，则拒绝。”11语言理论中的不可判定问题定理5.4EQTM是不可判定的。设TMR判定EQTM。如下构造判定ETM的TMS：S=“对于输入M，其中M是TM：1)在输入M，M1上运行R，其中M1是拒绝所有输入的图灵机。2)如果R接受，则接受；如果R拒绝，则拒绝。如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。12语言理论中的不可判定问题定义5.5设M是一个图灵机，w是一个串。M在w上的一个接受计算历史是一个格局序列C1，C2，．．．,Cl，其中C1是M在w上的起始格局，Cl是M的一个接受格局，且每个Ci都是Ci-1的合法结果，即符合M的规则。M在w上的一拒绝计算历史可类似定义，只是Cl应是一个拒绝格局。13定义5.6线性界限自动机是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就保持在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式一样。语言理论中的不可判定问题定义5.6ababa控制器14定义5.6设M是有q个状态和g个带符号的LBA。对于长度为n的带子，M恰有qngn个不同的格局。语言理论中的不可判定问题引理5.7M的格局就像计算中间的一快照。格局由控制状态、读写头位置和带内容组成。这里，M有q个状态。它的带长度是n，所以读写头可能处于n个位置之一，且gn多个带符号串可能出现在带上。此三个量的乘积就是带长为n的M的格局总数。15定义5.6ALBA是可判定的。语言理论中的不可判定问题定理5.8证明判定ALBA的算法如下：L=“对于输入M，w，其中M是LBA，w是串：1)在w上模拟Mqngn步，或者直到它停机。2)如果M停机，则当它接受时接受，拒绝时拒绝。如果它还没有停机，就拒绝。”如果M在w上运行qngn步还没有停机，根据引理5.7，它必定在重复某个格局，即陷入了循环。这就是算法为什么在此情形下拒绝的原因。16定义5.6ELBA是不可判定的。语言理论中的不可判定问题定理5.9现在构造从ATM到ELBA的归约。假设TMR判定ELBA。如下构造判定ATM的TMS：S=“对于输入M，w，其中M是TM，w是串：1)如在证明思路中所描述的那样从M和w构造LBAB。2)在输入B上运行R。3)如果R拒绝，则接受；如果R接受，则拒绝。”####…##C1C2C3Cl17如果R接受B，则L(B)=。这样，M在w上就没接受计算历史，M也就不接受w.因此，S也就拒绝M，w。类似地，如果R拒绝B，则B的语言不空。B能够接受的唯一串是M在w上的接受计算历史。这样，M必定接受w。相应地，S也就接受M，w。下图是检查这样一个TM计算历史的示意图。语言理论中的不可判定问题q3ab#xxq5b#……#xBCiCi+118使用利用计算历史的归约技术，还能建立有关上下文无关文法和下推自动机问题的不可判定性。加快一下，定理4.7介绍了一个算法来判定一个上下文无关文法是否派生串，即判定L(G)=是否成立。与此相关，现在要证明问题“测定一个上下文无关文法是否派生所有可能的串”是不可判定的。证明这个问题不可判定是证明上下文无关文法等价性问题不可判定的重要步骤。设:ALLCFG={G|G是一个CFG且L(G)=*}语言理论中的不可判定问题19定义5.6ALLCFG是不可判定的。语言理论中的不可判定问题定理5.10用反证法。为得到矛盾，假设ALLCFG是可判定的，用这个假设来证明ATM是可判定的。其证明与定理5.9的证明类似，只是稍微复杂一些，绕了一点点弯。这是一个从ATM出发利用计算历史的归约。但由于技术上的原因，对计算历史的表示做了些修改，后面将解释这样做的原因。现在来描述怎样运用ALLCFG的判定过程来判定ATM。对于TMM和输入串w，首先构造一个CFGG，使得它派生所有串当且仅当M不接受w。所以，如果M接受w，则存在一个特别的串，G不派生它。这个串应该是M在w上的计算历史。即：设计G，使之派生所有不是M在w上接受计算历史的串。20语言理论中的不可判定问题为了使得CFGG派生所有不是M在w上接受计算历史的串，采用下的策略。一个串不能成为M在w上的接受计算历史的原因可能有多个。将M在w上的接受计算历史表示成#C1#C2#...#Cl#，其中Ci是M在w上计算的第i步的格局。然后G派生出满足下述条件的所有串：1)不以Cl开始。2)不以一个接受格局结束3)在M的规则下，某个Ci不恰好派生Ci+1。如果M不接受w，就没有接受计算历史存在，故所有串都因为这样或那样的问题而不能成为接受计算历史，因此G将派生所有串，这正是所希望的。21语言理论中的不可判定问题这个思路存在的问题是：当D将Ci弹出栈时，它处于相反的左右为难，因而不适合与Ci+1比较。前面提到的绕弯就在此处。换一种方法来写接受计算历史，使得每隔一个格局就以相反的顺序出现。奇数位置保持以向前的顺序写，但偶数位置向后写。这种形式的一个接受计算历史如下图所示：####…##C1C2RC3C4R#Cl22主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性5.3.1可计算函数5.3.2映射可归约性的形式定义23本节将证明：不可判定性现象不仅能仅能局限于有限自动机的问题，我们将给出一个关于串操作的不可判定问题，称为波斯特对应问题。可以很容易地将这个问题描述成一种游戏，多米诺骨牌。每个骨牌由两个串构成，一边一个，单个骨牌看上去像一簇骨牌看起来像任务是将这些骨牌进行排列(允许重复)，使得在总计顶部符号后得到的串与总计询问符号后得到的串相同。这样的排列称为一个匹配。例如，下面的排列就是这个游戏的一个匹配。一个简单的不可判定问题aabbcaaabcaaabcc,,,24一个简单的不可判定问题aabbcacaaaababcc阅读顶部后得到的串abcaaabc，与总计询问后得到的本同。可以将骨牌变形使得和询问对应符号整齐地排列，以此更容易表示匹配。aabbccaaaaaabbcc25一个简单的不可判定问题对某些骨牌簇，不可能找到这样的匹配。例如，簇不可能包含匹配，因为顶部的每个串都比询问对应的串长。波斯特对应问题是：确定一簇骨牌是否有一个匹配。这个问题在算法上是不可解的。abcabcacaccba,,26一个简单的不可判定问题在形式描述这个问题和给出它的证明之前，先来精确地描述这个问题，然后表示成一个。骨牌簇P是pcp的一个实例：匹配是一个序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil.问题是确定P是否有匹配。令PCP={G|P是波斯特对应问题的一个实例，且P有匹配}t1b1t2b2tkbk,,P=,…27定义5.6PCP是不可判定的。一个简单的不可判定问题定理5.11假设TMR判定PCP。构造S来判定ATM。令M=(Q,,,,q0,qaccept,qreject)其中Q,,,分别是M的状态集、输入字母表、带字母表和转移函数。S构造PCP的一个实例P，使得P有一个匹配当且仅当M接受w。为此，S首先构造MPCP的一个实例P’。下面以七个部分来描述这个构造。每个部分完成在w上模拟M的一个特定方面。在构造过程中，为了解释我们正在做什么，用一个例子插在构造中。28一个简单的不可判定问题第1部分：构造以下方式开始：将放入p’作为第一张骨牌因为P’是MPCP的一个实例，故匹配必须以这张骨牌开始。底部串以M在w上接受计算历史中的第一个格局C1=q0w1w2．．．wn开始。如图所示:##q0w1w2…wn#t1b1##…q0w1w2wn#29一个简单的不可判定问题到目前为止，只得到一个部分匹配，其询问串由C1=＃q0w1w2．．．wn＃构成，顶部串只有#。为获得匹配，盘面扩展串来匹配询问串。用新骨牌来作这样的扩展。这些新的骨牌强迫模拟M的一次单步运行，使得M的一下个格局出现在询问串的扩展中。第2、3、4部分在P’中增加的骨牌在模拟中起主要作用。第2部分处理读写向右运动，第3部分处理读写头向左运动，第4部分处理不与读写关相邻的带方格。30一个简单的