计算理论导引23

5.1 证明EQ CFG 是不可判定的。

解：只须证明ALL CFG ≤m EQ CFG 即可。

构造CFG G 1，使L(G 1)=∑*。

设计从ALL CFG 到EQ CFG 的归约函数如下： F=“对于输入＜G ＞，其中G 是CFG ：1）输出＜G ,G 1＞。

”若＜G ＞ALL CFG ，则<G ,G 1>EQ CFG 。

若＜G ＞ALL CFG ，则<G , G 1>EQ CFG 。

F 将ALL CFG 归约到EQ CFG 即ALL CFG ≤m EQ CFG∵ALL CFG 是不可判定的，∴EQ CFG 是不可判定的。

5.2证明EQ CFG 是补图灵可识别的。

证明：注意到A CFG ={<G,w>|G 是能派生串w 的CFG}是可判定的。

构造如下TM ： F=“输入<G ,H>，其中G ,H 是CFG ，1) 对于字符串S 1, S 2,，重复如下步骤。

2) 检测S i 是否可以由G 和H 派生。

3) 若G 和H 中有一个能派生w ，而另一个不能，则接受。

”F 识别EQ CFG 的补。

5.3 略。

5.4 如果A m B 且B 是正则语言，这是否蕴涵着A 也是正则语言？为什么？ 解：否。

例如：对非正则语言A={0n 1n |n 0}和正则语言B={0}，可以构造一个可计算函数f 使得：f(w)=⎩⎨⎧≠=n n nn 10w 1,10w 0, 于是w A f(w)B,故A m B 。

5.5 证明A TM 不可映射规约到E TM 。

证明：反证法假设A TM m E TM ， 则有TM m TM E A ≤。

而A TM 的补不是图灵可识别的，从而可知E TM 的补也不是图灵可识别的。

下面构造一个识别E TM 的补的图灵机S ：S=“输入<M>，M 是TM,1) 对i=1,2,…重复下一步。

2) 对S 1,S 2,…,S i 模拟M 运行i 步，若有接受，则接受。

计算机技术硕士专业学位培养方案专业代码:0852１1一、培养目标计算机技术工程硕士得培养目标就是面向国民经济信息化建设与发展需要、面向企业事业单位对各类计算机应用人才需求,培养高层次实用型、高素质复合型得计算机技术人才。

二、研究方向(1)软件自动化与形式化方法(２)分布计算与并行处理及新型网络（3)系统软件及其信息安全(４)新型程序设计与软件方法学（5)多媒体技术(6)人工智能与知识工程(７)机器学习与数据挖掘(8)数据库技术(9)语言信息处理四、招生对象三、招生对象１.计算机科学与技术专业及相近专业得本科毕业生;2.从事计算机相关工作或相近专业工作,有实践经验得同等学历人员;四、学习年限ﻩ计算机技术专业硕士实行３年学制。

最长年限为４年。

五、课程设置本专业学分构成为:学位课（Ａ＋B)= 16学分;选修课（D)≧（16)学分；总分≧3２学分。

1.根据中宣部、教育部得相关通知,Ａ类中“自然辩证法等选修课程”就是指“《自然辩证法概论》或《马克思主义与社会科学方法论》或《马克思主义原著选读》”3门,我校要求硕士生须在其中任选1门。

2.非计算机类专业本科及同等学力入学者为36学分，须补修本科专业核心课与指定选修课(具体课程可咨询本科教务员),合计4学分。

六、教学方式ﻩ课堂讲授、课堂讨论、课程论文、课程实习、实习实践(不少于12个月)。

七、考核方式1.笔试、口试、读书报告、实习报告、课程论文。

ﻩ2.中期考核安排在第三学期，考核专业基础理论、对学科动态与前沿得了解、分析问题与解决问题得能力、综合素养、外语水平等。

根据考核成绩向进入硕士毕业设计阶段或中止研究生学习等方向分流。

八、毕业设计ﻩ1．选择具有较强应用价值得设计课题。

2．严格开题报告制度。

3．加强毕业设计得指导与监督。

4．进行毕业设计得规范性教育。

九、答辩与学位授予ﻩ根据学位委员会规定得程序与要求,审阅毕业设计,组织答辩委员会,进行答辩、建议就是否授予学位。

计算机技术硕士专业学位培养方案专业代码：085211一、培养目标计算机技术工程硕士的培养目标是面向国民经济信息化建设和发展需要、面向企业事业单位对各类计算机应用人才需求，培养高层次实用型、高素质复合型的计算机技术人才。

二、研究方向（1）软件自动化与形式化方法（2）分布计算与并行处理及新型网络（3）系统软件及其信息安全（4）新型程序设计与软件方法学（5）多媒体技术（6）人工智能与知识工程（7）机器学习与数据挖掘（8）数据库技术（9）语言信息处理四、招生对象三、招生对象1．计算机科学与技术专业及相近专业的本科毕业生；2．从事计算机相关工作或相近专业工作，有实践经验的同等学历人员；四、学习年限计算机技术专业硕士实行3年学制。

最长年限为4年。

五、课程设置本专业学分构成为：学位课（A+B）= 16学分；选修课（D）≧（16）学分；总分≧32学分。

1.根据中宣部、教育部的相关通知，A类中“自然辩证法等选修课程”是指“《自然辩证法概论》或《马克思主义与社会科学方法论》或《马克思主义原著选读》”3门，我校要求硕士生须在其中任选1门。

2.非计算机类专业本科及同等学力入学者为36学分，须补修本科专业核心课和指定选修课（具体课程可咨询本科教务员），合计4学分。

六、教学方式课堂讲授、课堂讨论、课程论文、课程实习、实习实践（不少于12个月）。

七、考核方式1．笔试、口试、读书报告、实习报告、课程论文。

2．中期考核安排在第三学期，考核专业基础理论、对学科动态和前沿的了解、分析问题和解决问题的能力、综合素养、外语水平等。

根据考核成绩向进入硕士毕业设计阶段或中止研究生学习等方向分流。

八、毕业设计1．选择具有较强应用价值的设计课题。

2．严格开题报告制度。

3．加强毕业设计的指导和监督。

4．进行毕业设计的规范性教育。

九、答辩和学位授予根据学位委员会规定的程序和要求，审阅毕业设计，组织答辩委员会，进行答辩、建议是否授予学位。

计算机科学与技术系二〇一四年六月。

定义概念题目：第三章：1. 图灵机：是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为，它的核心是转移函数δ，它说明了机器如何从一个格局走到下一个格局。

对于图灵机，δ的形式如下：Q×Γ→Q×Γ{L,R},图灵机是一个7元组（Q，∑，Γ，δ，q 0,q accept,q reject）.其中Q，∑，Γ都是有穷集合，并且1）Q是状态集；2）∑是输入字母表，不包括特殊空白符号凵，3）Γ是带字母表，其中凵∈Г，∑∈Г4）δ2. 格局：图灵机的计算过程中，当前状态，当前内容和读写头当前位置组合在一起。

例如：1011q701111：当前状态q7，当前读写头位置在第二个0上。

定义3.2 如果一个语言能被某一个图灵机识别，则称该语言是图灵可识别的（递归可枚举语言）定义3.2 如果一个语言能被某一个图灵机判定，则称该语言是图灵可判定的简称可判定的（递归语言）3.图灵机的变形：多带图灵机、非确定型图灵机、枚举器。

每个4.枚举器：他是图灵机的一种变形，是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串，每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。

一个语言是图灵可识别的，当且仅当有枚举器枚举它。

5.图灵机的术语：形式化描述，实现描述，高水平描述。

第四章：1.可判定的语言有：（A DFA、A NFA、A REX、E DFA、EQ DFA 是正则语言）、（A CFG、E CFG 是上下无关语言）❶每个上下文无关语言都是可判定的。

2.不可判定的语言有:：EQ CFG、A TM 、停机问题、HALT TM 、E TM、REGULAR TM 、EQ TM 、 E LBA 、ALL CFG 、PCPA TM =｛<M,ω>｜M是TM，ω是串，M接受ω｝是不可判定的。

证明：假设证A TM 是可判定的，下面将由之导出矛盾。

设H是A TM 的判定器。

令M是一个TM，ω是一个串。

8.1 证明对于任意函数f:N 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接受，则接受；否则，拒绝。

”N在f(n)空间内运行，L(N)=L(M)=A，所以A SPACE2(f(n))。

首先SPACE2(f(n))SPACE1(f(n))。

设A SPACE2(f(n))，且N 为在f(n)空间内判定A的双带只读输入TM。

按照用单带TM模拟多带TM的常规方式构造M：M＝“对于输入串w：1)初始化工作带为＃w1’w2…w n#’.其中以’标记N的两个读写头。

2)模拟N运行直到停机。

每一步模拟，要两次扫描带子。

第一次扫描确定读写头下符号，第二次扫描根据N的转移函数完成改写和移动读写头的工作。

3)若N接受，则接受；否则，拒绝。

”L(M)=L(N)=A。

由于f(n)n，M的运行空间是f(n)+n+2＝O(f(n))。

8.3 考虑广义地理学游戏，其中起始节点就是又无源箭头指入的节点。

选手I有必胜策略吗？选手II呢？给出理由。

1 2 34 5 6I II I II I Winner2 3 6 I4 5 6 II由表上来看选手II有必胜策略I2II4(不能选3)I5II6(不能选2)I。

8.4 证明PSPACE在并、补和星号运算下封闭。

证明：(1) 并：对任意L1, L2PSPACE，设有n a空间图灵机M1和n b空间图灵机M2判定它们，且c=max{a,b}。