计算理论习题解答

| PPDA没状态}构造判定器D：
D输入

P(QSGdF)PDA
1) P中状态q重复步骤
2) 构造PDA P1(QSGdF1)中F1{q}
3) 检测L(P1)否空L(P1)Æ拒绝
4) 没空接受

428设A某图灵机描述构成图灵识语言{¼}中Mi判定器求证：存判定语言D描述A中出现判定器判定
证：设EA枚举器考虑判定器F：
F＝输入串x
1) 初始化令y＝e
2) 运行EE输出串(判定器)时计算y字典序串串记yy¹x继续运行E
3) yx相记E时输出判定器
4) 串x运行MiMi接受拒绝Mi拒绝接受
L(F)求语言
1) w运行M2M2接受接受M2拒绝拒绝
M识AÇB图灵识语言类运算封闭

321
1) cmax³|c1|知|x|£1欲判定等式明显成立
2) |x|>1时
c1xn + c2xn1 + …+ cnx + cn+1 0
Þ c1x －(c2 + …+ cnx2n + cn+1x1n)
Þ |c1| |x| |c2 + …+ cnx2n + cn+1x1n|
< |c2| +…+ |cn||x|2n + |cn+1| |x|1n
£ |x|>1a<0时|x|a <1
|c2| +……|cn| + |cn+1||x0|
£ n cmax
< (n + 1) cmax
Þ |x| < (n + 1) cmax |c1|
(1)(2)知结成立

322 解：A判定
帝存s0A{0}判定
帝存s1A{1}判定

51 证明EQCFG判定
解：须证明ALLCFG≤mEQCFG
构造CFG G1L(G1)∑*设计ALLCFGEQCFG约函数：
F输入＜G＞中GCFG：
1） 输出＜GG1＞
＜G＞ÎALLCFGÎEQCFG
＜G＞ÏALLCFGÏEQCFG
FALLCFG 约EQCFG ALLCFG≤mEQCFG
∵ALLCFG判定
∴EQCFG判定

52证明EQCFG补图灵识
证明：注意ACFG{|G派生串wCFG}判定构造TM：
F输入中GHCFG
1) 字符串S1 S2¼重复步骤
2) 检测Si否GH派生
3) GH中派生w接受
F识EQCFG补

53 略

54 果A£mBB正语言否蕴涵着A正语言？什？
解：否例：
非正语言A{0n1n|n³0}正语言B{0}构造计算函数f：
f(w)
wÎAÛf(w)ÎBA£mB

55 证明ATM映射规约ETM
证明：反证法
假设ATM£mETM ATM补图灵识知ETM补图灵识
面构造识ETM补图灵机S：
S输入MTM
1) i12…重复步
2) S1S2…Si模拟M运行i步接受接受
S识ETM补ETM补图灵识面假设ETM补图灵识矛盾ATM映射规约ETM

56 略
57证明：果A图灵识A≤mA判定
证：∵A≤m≤mA
A图灵识
∴图灵识
∴A图灵识知A判定

58 解：构造相应骨牌簇时添加类骨牌：
M中左移d(qa)(rbL)添加张骨牌：

第张骨牌改

问题

5x 证明图灵识问题映射规约ATM
证明：设问题A图灵识M识ATM构造计算函数ff(w)
wÎAÛf(w)Î ATM
说明A≤m ATM

59 证明S{|MTM满足：接受w接受wR}判定
证明：意中MTMw串令f()TM：
F输入x
1) x¹0110拒绝
2) x01接受
3) x10w运行MM接受接受
ÎATMÛ f()ÎSATM≤mSS判定

510 证明S{|双带TM M输入w运行时会第二条带写非空白符}判定
证明：意中M单带确定TMw字符串令f()中D双带TM：
D输入x
1) 初始化x放第带第二带空
2) 第带模拟M运行
3) M接受第二带写非空白符接受M拒绝拒绝
D构造出ÎATMÛÎSATM≤mSS判定

513 USELESSTM {| NTMN状态}
求证USELESSTM判定
证明：构造ETMUSELESSTM规约函数
F输入M(QSGdq0qacceptqreject)TM
1) 构造TM N
N(QS1G1d1q0qacceptqreject)中
S1SÈ{}G1G1È{}设Q{q0q1q2¼qnqreject qaccept }
意qÎQaÎG1：

2) 输出
意TM M构造TM N接受状态外状态均非状态(输入运行NN遍历q0q1q2¼qn进入qreject停机)构造N目消M中非接受状态状态：
ÎETMÞ ÎUSELESSTM
ÏETMÞ ÏUSELESSTM
ETM≤mUSELESSTMETM判定USELESSTM判定

514 考虑样问题：检查图灵机输入w读写头处带左方格时否试图读写头左移问题形式化语言证明判定
解：问题形式化语言S：
S{ | TM M输入w读写头处带左方格时试图读写头左移}
证明S判定证明ATM≤mS构造计算函数f∑*®∑*中MTMw串f()中
M’输入x
1) 工作带容改x
2) 读写头置x第字符模拟M运行
3) 读写头移保持状态右移格
4) M进入接受状态读写头左移左移次停机接受M进入拒绝状态拒绝
ÎATMÛÎS

515 证明S{|图灵机M输入w运行时左移}判定
证明：构造TM F：
F输入MTMw串
1) 计算M状态数记p
2) w模拟M直左移停机已运行|w|+p步
3) 左移接受停机左移拒绝左移停机拒绝
需说明|w|+p步运行中左移停机情况左移M运行|w|步进入空白区域右移次读写头指空格运行p步少会状态出现两次停机意味着M进入循环会出现左移总F判定S

517 证明PCP元字母表字母表∑{1}判定
证明：构造识该语言图灵机
S输入骨牌序列

扫描骨牌序列骨牌面1数面1数面1数拒绝否接受
S判定样PCP

518证明PCP二元字母表字母表Σ{01}判定
证明：想证明该PCP(记PCP2)判定须证明ATM≤mPCP2需利定理511证明程规约传递性：
首先书中PCP实例P映射PCP2实例P2
设计PP2规约函数：
F输入

中PPCP：
1) 造 PCP P2P中骨牌中包含字符串进行Huffman编码形成应含01字符串(进行定长编码)
2) 输出
FPCP映射规约PCP2PCP≤mPCP2
次定理511ATM≤mPCP
根规约传递性知ATM≤mPCP2
∵ATM判定
∴PCP2判定

521 设AMBIGCFG＝{|G歧义CFG}证明AMBIGCFG判定
证明：设AMBIGCFG判定R判定AMBIGCFG构造S判定PCP
S＝PCP输入p＝{[t1b1][t2b2][tkbk]}
1) 利规构造CFG G：
S®T|B
T®t1Ta1|t2Ta2||tkTak|t1a1||tkak
B®b1Ba1|b2Ba2||bkBak|t1a1||bkak
2) 运行R果R接受接受果R拒绝拒绝
中ai保证T®t1Ta1|t2Ta2||tkTak|t1a1||tkak歧义CFG
样果AMBIGCFG判定PCP判定PCP判定导出矛盾AMBIGCFG判定

5x 证明：举反例：
令A{|M图灵机}A满足问题xxx中条件a满足条件bA判定证明否符合图灵机形式定义满足条件a满足条件b导出判定
令B{M1}中M1台图灵机B满足问题xxx中条件b满足条件aB判定满足条件b满足条件a导出判定
524证明：意字符串x令f1(x)0xxÎATMÛf1(x)0x∈JATM≤m J进步£m图灵识知图灵识
意字符串x令f2(x)1xxÏATMÛf2(x)1x∈J£mJ图灵识知J图灵识

525出判定语言B例子B≤m
解：利第10题结果令B524中JJ≤m构造约函数
F输入w
1） w第位取反0变11变0
2） 输出w
FJ映射约J 判定

526证明：
(a) 判定A2DFA算法：
L输入中M2DFAx串
1) 计算M状态数qx长度n
2) x模拟M qn2步直停机
3) M停机M接受时接受拒绝时拒绝未停机拒绝
Mq状态长度n输入Mqn2格局(注意：带容会改变)模拟qn2步未停机必定进入循环该情况应拒绝
(b) 构造ATME2DFA补映射约函数意定f()2DFA描述：
B输入x
x#C1#C2#…#Cm# 检查x满足：
a) C1Mω起始格局
b) Ci+1Ci合法结果
c) CmM接受格局
接受
条件ac较容易验证验证b时B两读头分CiCi+1相应位置移动验证结果否适B构造
ÎATMÛ f()ÏE2DFA
ATM映射约E2DFA补ATM判定知E2DFA判定

527 证明EQ2DIMDFA判定
证明：面证明ATM映射约EQ2DIMDFA补：
意f()两2DIMDFA描述中H满足L(H)Æ构造G记格局序列C1C2…Cm编码格局序列C1C2…Cm组成矩形串分C1C2…Cm格局行较短右边补适数量空格四周#围成方框
G输入串x
xx满足：
a) C1Mw起始格局
b) Ci+1Ci合法结果
c) CmM接受格局
接受
GH构造
ÎATMÛ f()ÏEQ2DIMDFA
ATM映射约EQ2DIMDFA补ATM判定知EQ2DIMDFA判定

73 a
Operation
X
Y

1274
10505
X mod Y®X
1274
10505
X«Y
10505
1274
X mod Y®X
313
1274
X«Y
1274
313
X mod Y®X
22
313
X«Y
313
22
X mod Y®X
5
22
X«Y
22
5
X mod Y®X
2
5
X«Y
5
2
X mod Y®X
1
2
X«Y
2
1
X mod Y®X
0
1
X«Y
1
0
Y0时输出X1127410505互素
b略

74 字符串wbaba面文法CFG G试填写定理814中识文关语言项式时间算法中描述表
S®RT
R®TR|a
T®RT|b
解：
T
RT
S
RTS

R
S
S


T
RT



R


75 面公式满足？
f(xÚy)Ù(xÚ)Ù(Úy)Ù( Ú)
解(xy)四种取值：(true true)(true false)(false true)(false false)分带入公式：
(xy)(true true)f(trueÚtrue) Ù (trueÚfalse) Ù (falseÚtrue) Ù (falseÚfalse)false
(xy)(true false)f(trueÚfalse) Ù (trueÚtrue) Ù (falseÚfalse) Ù (falseÚtrue)false
(xy)(false true)f(falseÚtrue) Ù (falseÚfalse) Ù (trueÚtrue) Ù (trueÚfalse)false
(xy)(false false)f(falseÚfalse) Ù (falseÚtrue) Ù (trueÚfalse) Ù (trueÚtrue)false
原公式满足

76 证明P连接补运算封闭
(1) ：
意 L1 L2ÎP设na时间图灵机M1nb时间图灵机M2 判定cmax{ab}
L1ÈL2 构造判定器M
M输入字符串w
1) w运行M1w运行M2
2) 接受接受否拒绝
时间复杂度：设M1O(na)M2O(nb)令cmax{ab}
第步时O(na+nb) 总时间O(na+ nb)O(nc)
L1ÈL2属P类 P运算封闭

(2) 连接：
意 L1 L2 属P 类设na时间图灵机M1nb时间图灵机M2 判定cmax{ab}L1L2 构造判定器M
M输入字符串ww1w2…wn
1) k012…n重复列步骤
2) w1w2…wk运行M1wk+1wk+2…wn运行M2
3) 接受接受否继续
4) 分法接受拒绝
时间复杂度：(n+1)×(O(na)+O(nb))O(na+1)+O(nb+1)O(nc+1)L1L2属P类 P连接运算封闭

(3)补：
意 L1属P 类设时间O(na)判定器M1判定构造判定器M
M输入字符串w
(1) w运行M1
(2) M1接受拒绝M1拒绝接受
时间复杂度：O(na)属P类 P补运算封闭

77 证明NP连接运算封闭
(1) ：
意 L1 L2ÎNP设分na时间非确定图灵机M1nb时间非确定图灵机M2 判定cmax{ab}
构造判定L1ÈL2非确定图灵机M
M输入字符串w
1) w运行M1w运行M2
2) 接受接受否拒绝
非确定计算分支第步时O(na)+O(nb)总时间O(na+nb)O(nc) L1ÈL2ÎNP NP运算封闭
(2) 连接：
意 L1 L2ÎNP设分na时间非确定图灵机M1nb时间非确定图灵机M2 判定cmax{ab}
构造判定L1L2非确定图灵机M
M输入字符串w
1) 非确定分成两段xywxy
2) x运行M1y运行M2
3) 接受接受否拒绝
非确定计算分支第步时O(n)第二步时O(na)+O(nb)总时间O(na+ nb)O(nc) L1L2ÎNPNP连接运算封闭

88 证明果数采进制编码二进制编码素数判定项式时间解换句话说证明语言UNARYPRIME{1n|n素数}属P
证明设x判定数 构造判定器M
M输入1nn正整数
1) k23…n1重复列步骤
2) 1n次消k1刚消完拒绝
3) 刚消完接受
时间分析
1) 执行n2次次1步
2) k值执行步数n
3) 需步
整判定程需时间 (n2)(1+n)n2n2运行时间O(n2)UNARYPRIMEÎP

78 令CONNECTED＝｛|G连通图｝分析432节出算法证明语言属P
证明：判定CONNECTEDTM M高水描述：
M输入图G编码：
1)选择G第顶点作标记
2)重复步骤(3)直没新顶点作标记
3)G顶点果存条边连已作标记顶点标记该顶点
4)扫描G顶点确定否已作标记果接受否拒绝
分析该算法执行步骤1)执行次n顶点连通图n(n1)2条边次执行步骤3运行时间O(n2)标记n顶点步骤3需执行n次标记总运行时间O(n3)步骤4需执行n步
该算法总步数1+ O(n3)+nO(n3)该语言属P


79 图中三角形3团证明TRIANGLEÎP中
TRIANGLE＝{|G包含3团}
证明思路：采相邻矩阵形式存储图n结点图G存储矩阵Rn×n中满足：R[ii]0 R[ij]1(结点i结点j间条边)R[ij]∞(结点i结点j间存边)矩阵第行开始逐行扫描矩阵行行中找两1元素假设前扫描第i行R[ij]1 R[ik]1检查矩阵中 R[jk]否1成立接受否继续搜索
证明：算法D实现思路
D输入
1） 计算R结点数nn≤2拒绝否转2）
2） For i1 to n
3） For ji+1 to n
4） R[ij]1
5） For kj+1 to n
6） R[ik]1 检查矩阵中R[jk]否1接受
7） ijk时n拒绝
分析D步项式时间运行步骤2运行n次步骤2运行次步骤3运行ni次步骤3运行次步骤4运行nj次总计D执行O(n3)步

711
证明：构造NTM：
N输入
1) 较GH节点数相拒绝
2) 非确定G节点进行重排
3) GH完全相接受否拒绝
Nn计算分支长度nNTM项式时间ISO∈NP

问题

712 证明MODEXPÎP
设二进制整数b kmkm1…k1k0bk020+k121+k222+…+km2m(ki 01)构造判定MODEXP图灵机：
M输入abcp二进制整数
(1) k0k1…kn记b低位高位1n+1位
(2) 令d0ai12…n计算didi1×di1 mod p
(3) i01…nki1令cidiki0令ci1
(4) 计算ec0×c1×…×cn mod p
(5) ec mod p接受否拒绝
设两n位二进制整数相模n位二进制整数需运行时间T第二步时间nT第四步nT总运行时间O(nT)意味着MODEXP∈P


714 证明P星号运算封闭
证明：设M判定A时间f(n)图灵机妨设f(n)³n设计TM：
D输入yy1y2…yn
1) yε接受
2) ij＝12…n重复(3)
3) yiyi+1…yj运行M接受令T(i j)yes
4) 重复面步骤直表T改变
5) ij＝12…n重复面步骤
6) T(ij)yes转(5)否继续
7) k ii+1…j1 T(ik)T(k+1j)yes令T(ij)yes
8) T(1 n)yes接受否拒绝
运行时间：设O(n2f(n))+O(n3)＝O(n2f(n))

715 证明NP星号运算封闭
证明：设M判定A时间f(n)非确定图灵机妨设f(n)³n设计NTM：
D输入yy1y2…yn
1) yε接受
2) 非确定选择y划分yx1x2…xk中x1x2…xk字符串
3) i12…k重复步骤：
4) xi运行MM拒绝拒绝
5) 接受接受

略兴趣讨刘庆晖(qhliu@biteducn)联系
81 证明意函数fN®N中f(n)³n单带TM模型两带读输入TM模型定义空间复杂性类SPACE(f(n))总相
证明：区记单带TM模型f(n)空间判定语言类SPACE1(f(n)) 记双带读输入TM模型f(n)空间判定语言类SPACE2(f(n))该题证明SPACE1(f(n))＝SPACE2(f(n))
首先SPACE1(f(n))ÍSPACE2(f(n))设AÎSPACE1(f(n))设M设f(n)空间判定A单带TM构造双带TM读输入TM N
N输入串w：
1) w复制工作带
2) 工作带模拟M直停机
3) M接受接受否拒绝
Nf(n)空间运行L(N)L(M)AAÎSPACE2(f(n))
首先SPACE2(f(n))ÍSPACE1(f(n))设AÎSPACE2(f(n))Nf(n)空间判定A双带读输入TM单带TM模拟带TM常规方式构造M：
M＝输入串w：
1) 初始化工作带＃w1’w2…wn#’中’标记N两读写头
2) 模拟N运行直停机步模拟两次扫描带子第次扫描确定读写头符号第二次扫描根N转移函数完成改写移动读写头工作
3) N接受接受否拒绝
L(M)L(N)Af(n)³nM运行空间f(n)+n+2＝O(f(n))

83 考虑广义理学游戏中起始节点源箭头指入节点选手I必胜策略？选手II呢？出理

1
2
3
4
5
6







I
II
I
II
I
Winner
2
3
6
´

I
4
5
6
´
II

表选手II必胜策略
I2®II4(选3)®I5®II6(选2)®I´

84 证明PSPACE补星号运算封闭
证明：(1) ：
意 L1 L2ÎPSPACE设na空间图灵机M1nb空间图灵机M2 判定cmax{ab}
L1ÈL2 构造判定器M
M输入字符串ww1w2…wn
3) 初始化带子改写w1w1 w2w2…wnwn
4) w分运行M1M2奇数格运行M1偶数格运行M2
5) 接受接受否拒绝
空间复杂度：na+nbO(nc)
L1ÈL2属PSPACE PSPACE运算封闭
(2) 补：
意 L1属PSPACE设空间na判定器M1判定令L2L1补构造L2判定器M
M输入字符串w
1) w运行M1
2) M1接受拒绝M1拒绝接受
空间复杂度：naL2属PSPACE类PSPACE补运算封闭
(3)星号：
设M判定A空间na图灵机设计TM：
D输入yy1y2…yn
9) yε接受
10) ij＝12…n(i³j)重复(3)
11) yiyi+1…yj运行M接受令T(i j)yes
12) 重复面步骤直表T改变
13) ij＝12…n(i³j)重复面步骤
14) T(ij)yes转(5)否继续
15) k i…j1T(ik)T(k+1j) yes令T(ij)yes
16) T(1 n)yes接受否拒绝
运行空间：第3)步模拟M运行需na空间存储表T需n2空间A*属PSPACE

85 证明NL补星号运算封闭
证明：(1) ：
意 L1 L2ÎNL设O(logn)空间图灵机M1M2 判定cmax{ab}
L1ÈL2 构造判定器M
M输入字符串ww1w2…wn
1) 初始化带子改写w1w1 w2w2…wnwn
2) w分运行M1M2奇数格运行M1偶数格运行M2
3) 接受接受否拒绝
空间复杂度：2O(logn)O(logn)
L1ÈL2属NL NL运算封闭
(2) ：
意 L1 L2ÎNL设O(logn)空间图灵机M1M2 判定cmax{ab}
L1ÇL2 构造判定器M
M输入字符串ww1w2…wn
1) 初始化带子改写w1w1 w2w2…wnwn
2) w分运行M1M2奇数格运行M1偶数格运行M2
3) 两接受接受否拒绝
空间复杂度：2O(logn)O(logn)
L1ÇL2属NL NL交运算封闭
(3)星号：
设M判定A空间O(logn)图灵机设计TM：
D输入yy1y2…yn
1) 令i1
2) i£n非确定选取j£n重复步骤
3) 二进制ij存储工作带
4) yiyi+1…yj运行M
5) M拒绝拒绝M接受令ij+1
6) 接受
运行空间：第4)步模拟M运行需O(logn)空间存储ij需2logn空间A*属NL

86证明PSPACE难语言NP难
证明称BPSPACE难意A属PSPACEA£PB称BNP难意A属NPA£PB
现设BPSPACE难意A属NPNPÍPSPACEA£PB说明BNP难

87 证明ADFA属L
证明：构造双带读输入TM：
P输入MDFAw串：
1) w模拟M运行次二进制记录前状态编号前读符号数
2) w读完M接受接受否拒绝
设M状态数加w长度nP需2logn空间存储前状态编号已读符号数

829 证明ANFANL完全
证明：首先证明ANFA属NL构造图灵机
N输入中MNFA ww1w2…wn串
1) 设置前状态起始状态二进制记录编号
2) i12…nn+1重复步骤
3) 非确定选取0£j£k中kM状态数根转移函数e箭头转移j次次非确定选择状态
4) i£n根转移函数前状态wi非确定选择状态
5) 前状态接受状态接受
证明ANFANL完全PATHNL完全需证明PATH项式约
中G图stG两节点构造NFA N
GN状态转移图边标es起始状态{t}接受状态集构造约令
f()
f构造知ÎPATHÛÎANFA
91 证明TIME(2n)TIME(2n+1)
证明：2nO(2n+1)Þ TIME(2n)ÍTIME(2n+1)
2n+1O(2n)Þ TIME(2n+1)ÍTIME(2n)
TIME(2n)TIME(2n+1)
92证明TIME(2n)ÌTIME(22n)注：里Ì严格包含
证明：令f(n)22nf(n)logf(n)22n2n 时间层次定理
TIME(o(22n2n))ÌTIME(22n)
2no(22n2n)TIME(2n)ÍTIME(o(22n2n))
TIME(2n)ÌTIME(22n)
93 证明NTIME(n)ÌPSPACE
证明：NTIME(n)ÍNSPACE(n)ÍSPACE(n2)ÌSPACE(n3)ÌPSPACE
96 证明AÎPPA＝P
证明：首先PÍPA带谕示面证明PAÍP
取AÎP存项式图灵机T判定A
设BÎPA存带语言A谕示项式时间图灵机MA判定B构造带谕示图灵机D：
D输入串w
1) w运行MA
2) MA谕示带写某字符串xx运行TT接受代谕示回答x属A否代谕示回答x属A
3) MA接受接受否拒绝
设MA运行时间naT运行时间nb谕示带写字符串长度会超na询问谕示带次数会超naD运行时间na (na)bna+abAÎP
97 出带指数正表达式产生字母表{01}语言：
a 长500字符串 (0È1)500
b 长度超500字符串(0È1Èe)500
c 少500字符串 (0È1)500(0È1)*
d 长度等500字符串 (0È1Èe)499È(0È1)501(0È1)*
e 恰包含5001字符串 0*(10*)500
f 包含少5001字符串 (0È1)*(1(0È1)*)500
g 包含5001字符串 0*((eÈ1)0*)500
h 长度少500第500位置0字符串 (0È1)4990(0È1)*
i 包含两0间少相隔500符号字符串(0È1)*0(0È1)500(0È1)*0(0È1)*
98 R正表达式令R{mn}代表表达式RmÈRm+1 È…ÈRn说明样通常指数算子实现算子R{mn}许…
答：设m99 证明NPPSATNPCoNP
证明：AÎNPÞAÎPSATÞAcÎPSATÞAcÎNPÞCoNPÍNP
AÎCoNPÞAcÎNPÞAcÎPSATÞAÎNPÞNPÍCoNP
NPCoNP

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档