您好、欢迎来到现金彩票网!
当前位置:秒速快三投注平台 > 双带图灵机 >

计算理论习题答案CHAP5new

发布时间:2019-06-07 07:26 来源:未知 编辑:admin

  5.4 如果A?mB且B是正则语言,这是否蕴涵着A也是正则语言?为什么? 解:否。例如:

  对非正则语言A={0n1nn?0}和正则语言B={0},可以构造一个可计算函数f使得:

  假设ATM?mETM, 则有ATM?mETM。而ATM的补不是图灵可识别的,从而可知ETM的补也不是图灵可识别的。 下面构造一个识别ETM的补的图灵机S: S=“输入,M是TM,

  2) 对S1,S2,?,Si模拟M运行i步,若有接受,则接受。” S可识别ETM的补,所以ETM的补是图灵可识别的,与上面由假设得到的ETM

  的补不是图灵可识别的矛盾。所以ATM不可映射规约到ETM。 5.7证明:如果A是图灵可识别的,且A≤mA,则A是可判定的。 证:∵A≤mA?A≤mA

  ∴由A和A都是图灵可识别的可知A是可判定的. 5.8 解:在由构造相应骨牌簇时,添加如下一类骨牌:

  5.9 证明S={M是TM且满足:只要它接受w,就接受wR}不可判定。 证明:对任意,其中M是TM,w是串,令f()是如下TM: F=“输入x,

  5.10 证明S={双带TM M在输入w上运行时会在第二条带上写下一个非空白符}是不可判定的。

  证明:对任意,其中M是单带确定TM,w是字符串。令f()=,其中D是如下的双带TM: D=“输入x,

  1) 初始化,x放在第一带上,第二带为空。 2) 在第一带上模拟M运行。

  对于任意TM M,如上构造的TM N,除接受状态外,每个状态均非无用状态(若在输入$上运行N,则N遍历q0,q1,q2,?,qn,最后进入qreject并停机)。构造N的目的就是消除M中任何非接受状态为无用状态的可能。因此有:

  5.14 考虑这样的问题:检查图灵机在输入w上,当其读写头处于带最左方格时,是否曾经试图将读写头向左移。将这个问题形式化为一个语言,并证明它是不可判定的。

  为证明S是不可判定的,可以证明ATM≤mS。构造一个可计算函数f:∑*?∑

  2) 读写头置于x的第一个字符,模拟M运行。 3) 每当读写头移到$,保持状态,右移一格。

  5.15 证明S={图灵机M在输入w上运行时有左移}可判定。 证明:构造如下TM F:

  2) 在w上模拟M,直到有左移,或停机,或已运行了w+p步。 3) 若有左移,则接受;若停机但无左移,则拒绝;若无左移且不停机,

  需要说明的是在w+p步运行中无左移也不停机的情况。由于无左移,M运行w步以后进入空白区域。由于此后右移使得每次读写头所指向的都是空格,而且此后运行的p步至少会有一个状态出现两次,所以不停机意味着M进入了循环,也就不会出现左移。总之,F判定S。

  5.17 证明PCP在一元字母表上,即在字母表∑={1}上,是可判定的. 证明:构造识别该语言的图灵机如下:

  扫描骨牌序列。若所有的骨牌的上面的1的个数都大于下面的1的个数,或都小于下面的1的个数,则拒绝。否则,接受。”

  5.18证明PCP在二元字母表上,即在字母表Σ={0,1}上,是不可判定的。 证明:要想证明该PCP(记为PCP2)是不可判定的,只须证明ATM≤mPCP2。为此需要利用定理5.11的证明过程和规约的传递性:

  首先,把书中的PCP任一实例P映射到PCP2的实例P2 设计从P到P2的规约函数如下: F=“对输入

  1) 造 PCP P2,对P中所有骨牌中包含的字符串进行Huffman编码,形成一一对应的只含0和1的字符串(也可进行定长编码)。

http://fundacionsabugo.com/shuangdaitulingji/168.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有