下载文档原格式
计算复杂性理论计算复杂性理论是计算机科学中重要的一个分支，它研究了计算问题的难度和可解性。
通过对问题的复杂性进行分析和分类，计算复杂性理论为我们提供了解决问题的指导原则和限制条件。
本文将介绍计算复杂性理论的基本概念、主要研究内容以及其在实际应用中的重要性。
一、基本概念1. P和NP问题在计算复杂性理论中，最基本的概念是P问题和NP问题。
P 问题是指可以在多项式时间内解决的问题，即存在一个算法可以在多项式时间内给出问题的正确答案。
而NP问题则是指可以在多项式时间内验证答案的问题，但尚未找到多项式时间内解决的算法。
P问题是NP问题的子集，即所有的P问题也是NP问题，但目前尚不清楚P问题和NP问题是否是相同的类。
2. NP完全性NP完全性是计算复杂性理论中的一个关键概念，它指的是一类最困难的NP问题。
一个问题被称为是NP完全的，如果它既是一个NP问题，又满足以下条件：对于任何一个NP问题，都可以用多项式时间的算法将其约化为该问题。
换句话说，如果我们能够找到一个多项式时间算法来解决一个NP完全问题，那么我们也可以用同样的算法来解决所有的NP问题。
3. NP难度除了NP完全性概念，计算复杂性理论还引入了NP难度的概念。
一个问题被称为是NP难度的，如果对于任何一个NP问题，都可以用多项式时间的算法将其约化为该问题。
虽然NP难度问题不一定是NP问题，但它们和NP完全问题一样，都是十分困难的问题。
二、主要研究内容1. 多项式时间算法计算复杂性理论的一个主要研究内容是寻找和分析多项式时间算法。
多项式时间算法是指可以在多项式时间内解决的算法，即其执行时间与输入规模呈多项式关系。
研究多项式时间算法的目标是寻找高效的解决方法，从而提高问题的可解性。
2. 算法复杂性分析算法复杂性分析是计算复杂性理论中的另一个重要内容。
通过对算法的复杂性进行全面的分析，我们可以预测算法在实际应用中的性能表现。
算法复杂性分析的主要方法包括时间复杂性分析和空间复杂性分析，通过对算法的时间和空间需求进行测量和评估，我们可以判断算法在给定条件下的可行性和效率。
第1章计算机文化和计算思维基础一、选择题1.____ 是现代通用计算机的雏形。
A.宾州大学于1946年2月研制的ENIACB.查尔斯•巴贝奇于1934年设计的分析机C.冯•诺依曼和他的同事们研制的EDVACD.艾兰•图灵建立的图灵机模型2.世界上第一台电子计算机ENIAC诞生于 ______ 年。
A.1939B. 1946C. 1952D. 19583.计算机科学的奠基人是oA.查尔斯•巴贝奇B.艾兰•图灵C.莫奇莱和埃克特D.冯•诺依曼4.在下列关于图灵机的说法中，错误的是oA.现代计算机的功能不可能超过图灵机B.图灵机不可以计算的问题现代计算机也不能计算C.图灵机是真空管机器D.只有图灵机能解决的计算问题，实际计算机才能解决5.在计算机运行时，把程序和数据一样存放在内存中，这是1946年由 ____ 领导的小组正式提出并论证的。
A.冯•诺依曼B.布尔C.艾兰•图灵D.爱因斯坦6.计算机从其诞生至今已经历了4个时代，这种对计算机划代的原则是根据oA,计算机所采用的电子器件 B.计算机的运算速度C.程序设计语言D.计算机的储存量7.物理器件采用晶体管的计算机被称为oA.第一代计算机B.第二代计算机C.第三代计算机D.第四代计算机8.专门为某种用途而设计的计算机，称为 ______ 计算机。
A. -专用B.通用C.特殊D.模拟9.计算机最早的应用领域是oA.科学计算B.数据处理C.过程控制D. CAD/CAM/CIMS10.计算机辅助制造的简称是。
A. CADB. CAMC. CAED. CBE11.在电子商务中，企业与消费者之间的交易称为oA. B2BB. B2CC. C2CD. C2B12.下列不属于人类三大科学思维的是oA.理论思维B.逻辑思维C.实验思维D.计算思维13.下列关于计算思维的说法中，正确的是 ______ oA.计算机的发明导致了计算思维的诞生B.计算思维的本质是计算C.计算思维是计算机的思维方式D.计算思维是人类求解问题的一条途径14.下列关于可计算性的说法中，错误的是 ______ oA.所有问题都是可计算的B.图灵机可以计算的就是可计算的C.图灵机与现代计算机在功能上是等价的D. 一个问题是可计算的是指可以使用计算机在有限步骤中解决15.下列关于计算机复杂性的说法中，错误的是oA.时间复杂度为指数阶0(2》的问题是不可计算的问题B.肘间复杂度为指数阶0(2》的问题当n值稍大时就无法计算了C.0(r?)的时间复杂度小于0(2?D.计算复杂性度量标准是时间复杂性和空间复杂性第2章计算机系统一、选择题1.下列的不属于计算环境的发展经历的主要历史阶段。
计算机算法面试题及答案一、算法基础知识算法是计算机科学的核心内容之一，它是解决实际问题的有效工具。
在计算机算法面试中，考官通常会涉及算法的基础知识，因此我们需要对一些常见的算法和数据结构有所了解。
1. 算法的定义及特性算法是解决问题的一系列有序步骤的描述。
算法应该具备的特性包括：输入、输出、确定性、有限性、可行性。
2. 时间复杂度与空间复杂度在面试中，评估算法性能的指标通常是时间复杂度和空间复杂度。
时间复杂度是指算法运行所需时间与问题规模的关系，通常用大O记法表示。
空间复杂度是指算法所需的额外空间与问题规模的关系。
3. 常见数据结构在面试中，我们需要对一些常见的数据结构有所了解，比如数组、链表、栈、队列、树、图等。
我们需要了解它们的特点、操作方法以及常见的应用场景。
4. 常见算法在面试中，会考察一些常见的算法，比如排序算法（冒泡排序、插入排序、选择排序、快速排序、归并排序等），查找算法（线性查找、二分查找等），图算法（深度优先搜索、广度优先搜索等），动态规划算法等。
二、面试题及答案下面我将列举一些常见的算法面试题，并给出对应的答案及解析。
1. 请实现一个二分查找算法。
答案：```pythondef binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return -1```解析：二分查找算法是一种高效的查找算法，它的时间复杂度为O(logn)。
在有序数组中查找目标元素，我们通过不断缩小查找范围，直到找到目标元素或范围为空。
2. 请实现一个快速排序算法。
答案：```pythondef quick_sort(nums):if len(nums) <= 1:return numspivot = nums[0]left = [x for x in nums[1:] if x <= pivot]right = [x for x in nums[1:] if x > pivot]return quick_sort(left) + [pivot] + quick_sort(right)```解析：快速排序算法是一种高效的排序算法，它的时间复杂度为O(nlogn)。
一、单选题1、主存按字节编址，地址从3000H到AFFFH。
若用存储容量为1K x 4位的存储芯片构成该主存，至少需要（）片。
A.16B.32C.64D.128正确答案：C2、假定用若干个1K x 4位的芯片组成一个8K x 8位的存储器，则地址 14FFH 所在芯片的最小地址是（）A.0400HB.0800HC.1000HD.1400H正确答案：D3、某计算机主存容量为128KB，其中ROM区为16KB，其余为RAM区，按字节编址。
现要用2K x 4位的ROM芯片和4K x 8位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是（）A.8, 14B.16，14C.8，28D.16，28正确答案：D4、某程序执行过程中访存1050次，其中访问Cache缺失50次，则Cache的命中率是（）A.4.8%B.5.0%C. 95.0%D.95.2%正确答案：D5、假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。
若Cache的内容初始为空，采用基本二路组相联映射方式（即主存的第0块和第2块属于第0组）和LRU替换算法，当访问的主存地址依次是0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是（）。
若采用另一种改进的二路组相联映射方式（即主存的第0块和第1块属于第0组），则命中Cache的次数可达到（）A.1, 3B.2, 3C.1, 4D.2, 4正确答案：A6、某计算机的Cache共有32块，采用8路组相联映射方式。
每个主存块大小为16字节，按字节编址。
主存133号单元所在主存块应装入到的Cache组号是（）A.0B.1C.2D.3正确答案：A7、假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为800x600，颜色深度为16位，帧频为60Hz，显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（）A.245MbpsB.461MbpsC.922MbpsD.1843Mbps正确答案：C8、下列关于闪存（Flash Memory）的叙述中，错误的是A.信息可读可写，并且读、写速度一样快B.存储元是一种半导体存储器，擦写次数有限C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可替代计算机外部存储器正确答案：A9、下列因素中，与Cache的命中率无关的是（）A.主存的存取时间B.块的大小C.Cache的组织方式D. Cache的容量正确答案：A10、在主存和Cache构成的两极存储体系中，Cache的存取时间是100ns，主存的存取时间是2us，Cache访问失败后CPU才开始访存。
大学计算机根底第九章习题与解析第9章怎样研究算法:遗传算法例如1、P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。
关于P、NP和NPC类问题，答复以下问题。
(1)以下说法不正确的选项是_____。
(A) P类问题是计算机可以在有限时间内能够求解的问题；(B) NP类问题是计算机可以在有限时间内能够验证“解〞的正确性的问题；(C) NPC类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解〞的正确性的问题，被称为NP完全问题；(D)上述说法有不正确的；答案：D解释：此题考核P类问题、NP类问题、NPC类问题的概念。
P类问题指计算机可以在有限时间内求解的问题，(A)正确；NP类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题，(B)正确；NPC 问题指NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算，称为NP-Complete问题，(C)正确；(A)(B)(C)都正确，所以(D)错误。
具体内容请参考第九章视频之“可求解与难求解问题〞以及第九章课件。
(2)可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。
以下说法不正确的选项是_____。
(A) P类问题是可解性问题，NP类问题是难解性问题。
(B) NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题；(C) NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题；(D)上述说法有不正确的；答案：A解释：此题考核对可解性问题和难解性问题概念的理解。
P类问题指计算机可以在有限时间内求解的问题，所以是可解性问题；NP类问题指虽然在多项式时间内难于求解但不难判断给定一个解的正确性问题，但P 类问题是NP类问题的一个子集，所以NP类问题不一定是难解性问题；NPC问题指NP问题的所有可能答案都可以在多项式时间内进行正确与否的验算，称为NP-Complete问题，是难解性问题，综上，(A)错误。
大学计算机基础(文经医外类)习题参考答案大学计算机基础（第2版）习题参考答案第一章习题及参考答案一．单选题（附参考答案）(1) 我们讨论的计算思维中的计算一词，指英语中的：（a）computation (b) computing(c) computation and computing (d) neither computation no computing 参考答案:C(2) 移动通信与地理信息系统的结合，产生了新的计算模式：(a)与位置有关的计算 (b)与时间有关的计算 (c)与空间有关的计算 (d)与人群有关的计算参考答案:A(3) 当交通灯会随着车流的密集程度，自动调整而不再是按固定的时间间隔放行时间时，我们说，这是计算思维___________的表现。
(a)人性化 (b)网络化 (c)智能化 (d)工程化参考答案:C(4) 计算思维服务化处于计算思维层次的：(a)基础层次 (b)应用层次 (c) 中间层次 (d) 工程技术层参考答案:B(5) 计算思维的智能化处于计算思维层次的：(a)基础层次 (b)应用层次 (c) 顶层层次 (d) 工程技术层参考答案:D(6) 以下列出的方法哪一项不属于科学方法：(a) 理论 (b) 实验 (c) 假设和论证 (d) 计算参考答案:C(7) 以下列出的哪一项不属于公理系统需要满足的基本条件？(a) 无矛盾性 (b) 独立性 (c) 完备性 (d) 不完备性参考答案:D(8) 以下哪一项不属于伽利略的实验思维方法的基本步骤之一：(a)设计基本的实验装置 (b)从现象中提取量的概念 (c)导出易于实验的数量关系 (d)通过实验证实数量关系参考答案:A(9) 对于实验思维来说，最为重要的事情有三项，但不包括以下的：(a) 设计实验仪器 (b)制造实验仪器 (c) 保证实验结果的准确性 (d) 追求理想的实验环境参考答案:C(10) 计算思维最根本的内容为：(a) 抽象 (b) 递归 (c) 自动化 (d) a和c 参考答案:D(11) 计算机科学在本质上源自于：(a) 数学思维 (b) 实验思维 (c) 工程思维 (d) a和c 参考答案:D(12) 计算理论是研究使用计算机解决计算问题的数学理论。
电子计算机的诞生1物理器件采用晶体管的计算机称为第（）代计算机。
A、一B、二C、三D、四正确答案：B2时至今日，计算机仍采用存储程序原理，原理的提出者是（）。
A、莫尔B、冯.诺依曼C、比尔.盖茨D、图灵正确答案：B3计算机科学的奠基人是（）。
A、查尔斯.巴贝奇B、莫奇利和埃克特C、阿兰.图灵D、冯.诺依曼正确答案：C4世界上第一台电子计算机诞生于（）年。
A、1939B、1946C、1952D、1958正确答案：B5计算机的发展经历了 4 个时代，各个时代划分的原则是根据（）。
A、计算机所采用的电子器件B、计算机的运算速度C、程序设计语言D、计算机的存储量正确答案：A6（）是现代计算机的雏形。
A、查尔斯.巴贝奇于 1834 年设计的分析机B、宾夕法尼亚大学于 1946 年 2 月研制的 ENIACC、冯.诺依曼小组研制的 EDVACD、阿兰.图灵建立的图灵机模型正确答案：A计算机系统的发展1下列（）是衡量微处理器的主要指标。
A、主频B、字长C、速度D、工艺正确答案：A2计算机系统的发展趋势不包括（）。
A、巨型化B、微型化C、智能化D、复合化正确答案：D3将 CPU 集成在一块芯片上所形成的元器件称为（）。
A、微处理器B、ROMC、CMOSD、Cache正确答案：A4下列（）不属于输入设备。
A、扫描仪B、键盘C、硬盘D、体感设备正确答案：C5负责解释和执行程序的部件称为（）。
A、内存B、中央处理单元C、输入设备D、输出设备正确答案：B6下面对计算机特点的说法中，不正确的是（）。
A、运算速度快B、计算精度高C、具有逻辑判断能力D、随着计算机硬件设备及软件的不断发展和提高，其价格也越来越高正确答案：D计算机系统的组成1计算机系统由（）组成。
A、运算器、控制器、存储器、输入设备和输出设备B、主机和外部设备C、硬件系统和软件系统D、主机箱、显示器、键盘、鼠标、打印机正确答案：C2组成计算机 CPU 的两大部件是（）。
1.6画出识别下述语言的DFA的状态图a){w | w从1开始以0结束}b){w | w 至少有3个1}c){w | w 含有子串0101}d){w | w 的长度不小于3,且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}0,10,1j) {w | w 至少含有2个0,且至多含有1个1}k) { & ,0}g) {w | w 的长度不超过5}0,1 「：0,10 01I) {w | w 含有偶数个0,或恰好两个1}1.29利用泵引理证明下述语言不是正则的。
n n na. A 1={0 1 2 | n 0}。
证明：假设A 是正则的。
设p 是泵引理给出的关于 A 的泵长度。
-ppp令 S=01 2 ,••• S 是A 1的一个成员且S 的长度大于P ,所以泵引理保证S 可被分成3段 S=xyz 且满足泵引理的3个条件。
根据条件3, y 中只含0, xyyz 中，0 比1、2多，xyyz 不是A 的成员。
违反泵引理的条件1,矛盾。
••• A 不是正则的。
*b. A 2={www | w {a,b} }.证明：假设A 是正则的。
设p 是泵引理给出的关于 A 的泵长度。
ppp令 S=aba bab,••• S 是A 的一个成员且S 的长度大于P ,所以泵引理保证S 可被分成3段 S=xyz 且满足泵引理的3个条件。
根据条件3, y 中只含a ,所以xyyz 中 第一个a 的个数将比后两个a 的个数多，故xyyz 不是A 的成员。
违反泵 引理的条件1,矛盾。
m)空集 n)一 CP 。
，11 1除空串外的所有字符串• A不是正则的。
2n2n nc. A 3={a2 | n 0}.（在这里，a2表示一串 2 个 a .）证明：假设A3是正则的。
设p是泵引理给出的关于A的泵长度令S= a2••• S是A的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S=xyz 且满足泵引理的3个条件。
即对任意的i 0，xy'z都应在A中，且xy'z与xy'+1z 的长度都应是2的幕.而且xy'+1z的长度应是xy'z的长度的n i n2倍(n 1) o于是可以选择足够大的i，使得|xy z|=2 >p.但是|xy'+1z|-|xy 'z|=|y| p.即|xy'+1z|<2 ,矛盾。
••• A不是正则的。
1.46证明：n m n p q pa)假设{0 1 0|m,n > 0}是正则的，p是由泵引理给出的泵长度。
取s = 010,q>0。
由泵引理条件3知，|xy| < p，故y —定由0组成，从而字符串xyyz中1前后0 的数目不同，即xyyz 不属于该语言，这与泵引理矛盾。
所以该语言不是正则的。
b)假设{0n1n|n > 0}的补集是正则的，则根据正则语言在补运算下封闭可得{0n1n|n >0}是正则的，这与已知矛盾，故假设不成立。
所以该语言不是正则的。
c)记c={0m1 n|m M n}，门 c 为 c 的补集，门 c A 0*1*={0n1n|n > 0}，已知{0n1n|n > 0}不是正则的。
若门c是正则的，由于0*1*是正则的，那么门c A 0*1*也应为正则的。
这与已知矛盾，所以门c不是正则的。
由正则语言在补运算下的封闭性可知c 也不是正则的。
d){w | w {0,1} *不是一个回文}的补集是{w | w {0,1} *是一个回文}，设其是p q p正则的，令p 是由泵引理给出的泵长度。
取字符串s=010 ，显然s 是一个回文且长度大于p。
由泵引理条件3知|xy| < p，故y只能由0组成。
而xyyz不再是一个回文，这与泵引理矛盾。
所以{w | w {0,1} *是一个回文}不是正则的。
由正则语言在补运算下的封闭性可知{w | w {0,1} *不是一个回文} 也不是正则的。
2.4和2.5给出产生下述语言的上下文无关文法和PDA 其中字母表={0,1}a. {w | w 至少含有3个1}S — A1A1A1A A — 0A|1A|b. {w | w 以相同的符号开始和结束}e. {w | w 中1比0多}S — 0A0|1A1 A — 0A|1A|c. {w | w 的长度为奇数}S — 0A|1A A — 0B|1B| B — 0A|1Ad. {w | w 的长度为奇数且正中间的符号为 0}S — 0S0| 1S1|0S1|1S0|0O1 o 1仁aa1.0, 1, 10,10, 0$S — A1A,$f.{w | w=wS—0S0|1S1|1|0g.空集2.15用定理2.6中给出的过程，把下述CFG专换成等价的乔姆斯基范式文法。
A BAB|B|B 00|解：添加新起始变元S0, 去掉BS A S c AA BAB|B| A BAB|AB|BA|B|B 00| B 00去掉A , 去掉A BS A S0 AA BAB|AB|BA|B|BB A BAB|AB|BA|00|BBB 00 B 00去掉S0 A, 添加新变元S0 BAB|AB|BA|00|BB S D VB|AB|BA|UU|BBA BAB|AB|BA|00|BB A VB|AB|BA|UU|BBB 00 B UUV BAU 03.15证明可判定语言类在下列运算下封闭。
S—Sa.并。
证明：设M, M为识别可判定语言A I,A2的判定器。
构造图灵机M帖“输入w,1）分别在w上运行M和M，每运行一步M就运行一步M。
2）若M和M中有一个接受，则接受。
若都拒绝，则拒绝。
”M为识别A I A的判定器。
所以可判定语言类对并运算封闭。
b.连接。
证明：设M, M为识别可判定语言A I,A2的判定器。
构造图灵机MM= “输入w,1）列出所有将w分成两段的方式（|w|+1种）.2）对于每一种分段方式，在第一段上运行M,在第二段上运行M。
若都接受，则接受。
3）若没有一种分段方式被接受则拒绝。
”M为识别A I A的判定器。
所以可判定语言类对连接运算封闭。
c.星号。
证明：设M为识别可判定语言A的判定器。
M= “输入w,1）列出w的所有分段的方式（2|w|-1种）。
2）对于每一种分段方式，重复下列步骤：3）分别在每一段上运行M,若每一段都能被M接受，则接受。
4）若没有一种分段方式被接受则拒绝。
”* 、M为识别A的判定器。
所以可判定语言类对星号运算封闭。
d.补。
证明：设M=（Q, , , ,q°, q 1, q 2）为识别可判定语言A的判定器，其中q1为接受状态，q2为拒绝状态。
令M=（Q, , , ,q o, q 2, q 1），其中q2为接受状态，q1为拒绝状态。
则M为识别A的判定器。
所以可判定语言类对补运算是封闭e.交。
证明：设M, M为识别可判定语言A,A2的判定器。
构造图灵机MMh “输入w,1)分别在w上运行M和M，每运行一步M就运行一步M。
2)若M和M中都接受，则接受。
若M1 和M2 中有一个拒绝,则拒绝。
”M为识别A i A2的判定器。
所以可判定语言类对交运算是封闭的。
3.16 证明图灵可识别语言类在下列运算下封闭：a.并b •连接c •星号d •交证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。
设A和B是图灵可识别语言，A=L(M) , B=L(M) , M和M是两个图灵机。
a.并M= “对于输入w:1)在输入w 上并行运行M1 和M2；2)M和M中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。
”M识别A A2。
所以图灵可识别语言类对并运算是封闭的。
b.连接帖“输入w,1)出所有将w分成两段的方式(|w|+1种).2)对于i=1,2, 重复以下步骤：3)对于每一种分段方式，在第一段上运行M1i 步，在第二段上运行M2i 步，或者直到停机。
若都接受，则接受。
”M识别A A。
所以图灵可识别语言类对连接运算是封闭的。
c.星号帖“输入w,1)列出w的所有分段的方式(2|w|-1种).2)对于i=1,2, 重复以下步骤：3)对于每一种分段方式，分别在每一段上运行M1 i 步，或者直到停机。
若M接受所有段，则接受M识别A*。
所以图灵可识别语言类对星号运算是封闭的。
d.交M= “对于输入w:1)在输入w上运行M。
若M接受，则转⑵；若M拒绝，则拒绝2)在w上运行M。
若M接受，则接受；若M拒绝，则拒绝。
”M识别A B。
所以图灵可识别语言类对并运算封闭。
3.211)由C max|C l|知，当|X| 1,则欲判定不等式明显成立。
2)当|x|>1时，由n n-1 小C1X + C 2X + …+ C n X + C n+1 = 02-n 1-n、C1X = —(C2 + …+ C n X + C n+1X )2-n 1-n|C 1| |X| = |C 2 + …+ C n X + C n+1X |2-n 1-n<|C 2| + …+ |C n||X| + |C n+1| |X||C 2| + .. .|C n| + |C n+1||x o|A C maX<(n + 1) C maX|X| < (n + 1) C max / |C 1|.4.11设A=｛<M>|M是DFA它不接受任何包含奇数个1的字符串｝。
证明A是可判定的。
证明：构造DFA N使L(N)=｛含奇数个1的字符串｝。
构造图灵机F= “对于输入<M>其中M是DFA1)构造DFA D 使L(D)=L(M) A L(N)。
2)检测L(D)是否为空。
(E DFA可判定检测)。
3)若L(D)=，则接受；否则拒绝。
”4.13 “检查一个CFG是否派生1*中某个串问题”解：LX={<G>|G 是{0，1}* 上的CFG 且1*A L(G)工}证明：构造TM TT二“对于输入<A>, A为CFG1）将终结符“ T和“”做标记。
2）重复下列步骤，直至无可做标记的变元。
3）如G有规则A UU2…U,且UU2…u n中每个符号都已做过标记，则将A做标记，其中U为终结符或非终结符。
4）如果起始变元没有被标记则拒绝，否则接受。
”T判定LX05.7证明：如果A是图灵可识别的，且A< m A，则A是可判定的。
证：••• A< m A A < m A且A为图灵可识别的••• A也为图灵可识别的•••由A和A都是图灵可识别的可知A是可判定的.5.1证明EQ FG是不可判定的。
解：只须证明ALL C FG<H EQ F G即可。
构造CFG G,使L（G）=刀*0设计从ALS到EQ FG的归约函数如下:F= “对于输入v G>，其中G是CFG1）输出v G,G>。
