下载文档原格式
3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。
证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。
现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器M。
模拟过程使用深度搜索。
设N的不确定性分支的最大个数为b。
M有三个带：一个输入带，一个工作带，一个地址带。
M按深度优先方式搜索N的不确定计算分支树。
M= “输入w，1)初始化，第一带上为w, 第二带为空，第三带为1;2)将第一带的内容复制到第二带上，3)按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N运行一步；4)若当前地址位为i<b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为i+1, 转第2步；5)若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空格, 左移并将当前地址位改为空格直到找到一个地址位其值<b，将当前地址位改为i+1, 转第2步；若到了地址带的最左端仍有当前地址位为b，则拒绝；6)若N进入接受状态，则接受；否则，右移一格，将空格上写入1，转第三步。
”由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。
3.4给出枚举器的形式定义。
解：枚举器E=(Q,∑,Γ,δ,q0,qaccept,qreject), 其中转移函数δ为：δ：Q×Γ→Q×Γ×{L,R}×∑*δ (q,a)=(r,b,s1,c)表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于ε，则不打印。
另外E的起始格局只能是qv，这里v表示一个空格。
3.5检查图灵机的形式定义，回答下列问题并解释你的推测：a．图灵机能在它的带子上写下空白符吗b．带字母表Γ和输入字母表∑能相同吗？c．图灵机的读写头能在连续的两步中处于同一个位置吗？d．图灵机能只包含一个状态吗？解：a．能。
《大学计算机基础与计算思维》课后习题参考答案第1章计算、计算机与计算思维............................. 第2章数据的计算基础计算机硬件系统第4章操作系统基础 (11)第5章算法与数据结构 (13)第6章程序设计及软件工程基础 (17)第7章数据库技术 (19)第8章计算机网络 (22)第9章信息安全与职业道德 (24)第10章计算软件第11章办公软件Office 2010算机科学与技术学院计算机基础教学部28 292015年9月第1章计算、计算机与计算思维1.1举例说明可计算性和计算复杂性的概念。
答：对于给定的一个输入，如果计算机器能在有限的步骤内给出答案，这个问题就是可计算的。
数值计算、能够转化为数值计算的非数值问题（如语咅、图形、图像等）都是可计算的。
汁算复杂性从数学上提出计算问题难度大小的模型，判断哪些问题的讣算是简单的，哪些是困难的，研究计算过程屮时间和空间等资源的耗费情况，从而寻求更为优越的求解复杂问题的有效规则，例如著名的汉诺塔问题。
1.2列举3种电子计算机岀现之前的计算工具，并简述其主要特点。
答:（1）算盘通过算法口诀化，加快了计算速度。
（2）帕斯卡加法器通过齿轮旋转解决了自动进位的问题。
（3）机电式计算机Z・l,全部采用继电器，第一次实现了浮点记数法、二进制运算、带存储地址的指令等设计思想。
1.3简述电子计算机的发展历程及各时代的主要特征。
答：第一代一一电子管计算机（1946—1954年）。
这个时期的计算机主要釆用电子管作为运算和逻辑元件。
主存储器采用汞延迟线、磁鼓、磁芯，外存储器采用磁带。
在软件方面，用机器语言和汇编语言编写程序。
程序的编写与修改都非常繁琐。
计算机主要用于科学和工程计算。
第二代一一晶体管计算机（1954—1964年）。
计算机逻辑元件逐步由电子管改为晶体管, 体积与功耗都有所降低。
主存储器采用铁脸氧磁芯器，外存储器釆用先进的磁盘，汁算机的速度和可靠性有所提高。
计算理论期末练习题（2015）复习重点1、集合序列元组函数关系图串：字母表中符号的有穷序列语⾔:是字符串的集合2、DFA、NFA、NFA到DFA的转换，DFA、NFA的形式化五元组表达3、正则表达式、正则表达式和NFA之间的转换、利⽤泵引理证明不是正则语⾔4、上下⽂⽆关⽂法下推⾃动机乔姆斯基范式（基本概念）CFG到下推⾃动机的转换从右⾄左压⼊栈中5、利⽤泵引理证明不是上下⽂⽆关语⾔6、图灵机、图灵可识别语⾔：接受、拒绝、循环判定器：对所有输⼊都停机的图灵机，永不循环。
图灵可判定语⾔：能让图灵机停机的语⾔，接受或者拒绝要求可以做简单的判定性证明（例如：A DFA、A CFG、HALT-TM、E TM）7、可归约性。
要求可以利⽤规约，完成简单的定理证明。
计算理论练习题1、画出识别下述语⾔的DFA 状态图，其中，字母表为{0,1}。
1）{w|w 从1开始且以0结束}；2）{w|w含有⾄少3个1}；3）{w|w含有⼦串0101}；q1的0⾃循环处考虑004）{w|w的长度不⼩于3，并且第3个符号为0}；5）{w|w从0开始且长度为奇数}；6）{w | w是除11和111以外的任何字符}；7）{w | w不含⼦串110}；2、写出下述语⾔的正则表达式。
1）{w|w不含⼦串110}；(0∪10)*1*2）{w|w的长度不超过5}；ε∪∑∪∑∑∪∑∑∑∪∑∑∑∑∪∑∑∑∑∑3）{w|w是除11和111外的任意串}；ε∪0∑*∪10 ∑*∪110 ∑*∪111 ∑∑*包含11或111的串仍属于题设4）{w|w的奇数位均为1}；(1Σ)*(ε? 1)前⼀个括号为串长为偶数，加后⼀个则奇偶都可以5）{w|w含有⾄少2个0，并且⾄多含1个1}。
0*(00?010?001?100) 0*确保两个0⼀定在，并且最多1个1，不能在外⾯，即有可能为空3、利⽤泵引理证明下述语⾔不是正则的。
1）A1={0n1n2n|n≥0};证明：假设A1是正则的。
第1章习题一、填空题1．计算机科学是主要研究（）、（）和（）的学科。
计算理论、计算机，信息处理2．在模型建立的前提下，利用计算机求解问题的核心工作就（）设计。
算法3．算法是一组规则，它的主要特性是（）、（）、（）、（）和（）。
有限性、可执行性、机械性、确定性，终止性或：有穷性，确定性，能行性，0个或多个输入输入，1个或多个输出4．要使一个问题能够用计算机解决，其必要条件是（）。
具有确定算法或：可以在确定、有限步骤内被解决5．在计算机内，一切信息都是以（）形式表示的。
二进制6．如果说图灵机A能够完全模拟图灵机B，则意味着（）。
如果A和B能够相互模拟，则表示（）。
在给定输入时，A和B有相同的输出 // A和B计算等价7．图灵机中的纸带可以相当于计算机中的（）。
存储器8．第一代计算机的主要部件是由（）和（）构成的。
电子管，继电器9．未来全新的计算机技术主要指（），（）和（）。
光子计算机，生物计算机，量子计算机10．未来电子计算机的发展方向是（）、（）、（）和（）。
巨型化，微型化，网络化，智能化11．目前国际上广泛采用的西文字符编码是标准（），它是用（）位二进制码表示一个字符。
ASCII，712．采用16位编码的一个汉字存储时要占用的字节数为（）。
213．位图文件的存储格式为（），用数码像机拍摄的照片的文件格式一般为（）。
BMP，JPG14．若处理的信息包括文字、图片、声音和电影，则其信息量相对最小的是（）。
文字15．模拟信号是指（）都连续变化的信号。
时间和幅值16．计算机中对信息的组织和管理方式有两种，即（）和（）。
文件，数据库17．软件的测试方法包括（）和（）。
白盒测试，黑盒测试18．普适计算的主要特点是（）。
无处不在的计算模式二、简答题：1．简述计算机采用二进制的原因。
答：主要原因是：①二进制只有0和1两个基本符号，任何两种对立的物理状态都可以归结为二进制表示。
②算术运算规则简单，且适合逻辑运算。
计算机考博试题计算理论及答案计算理论字母表：⼀个有穷的符号集合。
字母表上的字符串是该字母表中的符号的有穷序列。
⼀个字符串的长度是它作为序列的长度。
连接反转Kleene星号L* ，连接L中0个或多个字符串得到的所有字符串的集合。
有穷⾃动机：描述能⼒和资源极其有限的计算机模型。
有穷⾃动机是⼀个5元组M=(K,∑,δ,s,F),其中1）K是⼀个有穷的集合，称为状态集2）∑是⼀个有穷的集合，称为字母表3）δ是从KX∑→K的函数，称为转移函数4）s∈K是初始状态5）F?K是接收状态集M接收的语⾔是M接收的所有字符串的集合，记作L(M).对于每⼀台⾮确定型有穷⾃动机，有⼀台等价的确定型有穷⾃动机有穷⾃动机接受的语⾔在并、连接、Kleene星号、补、交运算下是封闭的。
每⼀台⾮确定型有穷⾃动机都等价于某⼀台确定型有穷⾃动机。
⼀个语⾔是正则的当且仅当它被有穷⾃动机接受。
正则表达式：称R是⼀个正则表达式，如果R是1）a，这⾥a是字母表∑中的⼀个元素。
2）ε，只包含⼀个字符串空串的语⾔3），不包含任何字符串的语⾔4)(R1∪R2),这⾥R1和R2是正则表达式5）(R10R2),这⾥R1和R2是正则表达式6）(R1*),这⾥R1*是正则表达式⼀个语⾔是正则的当且仅当可以⽤正则表达式描述。
2000年4⽉1、根据图灵机理论,说明现代计算机系统的理论基础。
1936年，图灵向伦敦权威的数学杂志投了⼀篇论⽂，题为《论数字计算在决断难题中的应⽤》。
在这篇开创性的论⽂中，图灵给“可计算性”下了⼀个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。
“图灵机”不是⼀种具体的机器，⽽是⼀种思想模型，可制造⼀种⼗分简单但运算能⼒极强的计算机装置，⽤来计算所有能想像得到的可计算函数。
这个装置由下⾯⼏个部分组成：⼀个⽆限长的纸带，⼀个读写头。
（中间那个⼤盒⼦），内部状态（盒⼦上的⽅块，⽐如A,B,E,H），另外，还有⼀个程序对这个盒⼦进⾏控制。
最优化方法-习题解答张彦斌计算机学院2014年10月20日Contents1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、412第二章线搜索算法-P27习题2、4、643第三章最速下降法和牛顿法P41习题1，2，374第四章共轭梯度法P51习题1，3，6(1)105第五章拟牛顿法P73-2126第六章信赖域方法P86-8147第七章非线性最小二乘问题P98-1，2，6188第八章最优性条件P112-1，2,5,6239第九章罚函数法P132，1-(1)、2-(1)、3-(3),62610第十一章二次规划习题11P178-1（1），5291第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、4 1.验证下列各集合是凸集:(1)S={(x1,x2)|2x1+x2≥1,x1−2x2≥1};需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)∈S及任意的实数λ∈[0,1],都有λx+(1−λ)y∈S.即,(λx1+(1−λ)y1,λx2+(1−λ)y2)∈S证：由x(x1,x2),y(y1,y2)∈S得到，{2x1+x2≥1,x1−2x2≥12y1+y2≥1,y1−2y2≥1(1)1把(1)中的两个式子对应的左右两部分分别乘以λ和1−λ,然后再相加，即得λ(2x1+x2)+(1−λ)(2y1+y2)≥1,λ(x1−2x2)+(1−λ)(y1−2y2)≥1(2)合并同类项，2(λx1+(1−λ)y1)+(λx2+(1−λ)y2)≥1,(λx1+(1−λ)y1)−2(λx2+(1−λ)y2)≥1(3)证毕.2.判断下列函数为凸（凹）函数或严格凸（凹）函数：(3)f(x)=x21−2x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5，f在凸集上是（I）凸函数的充分必要条件是∇2f(x)对一切x为半正定；（II）严格凸函数的充分条件是∇2f(x)对一切x为正定。
计算理论答案汇总第⼀章练习1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题.a. M 1的起始状态是q 1b. M 1的接受状态集是{q 2}c. M 2的起始状态是q 1d. M 2的接受状态集是｛q 1，q 4｝e. 对输⼊aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1f. M 1接受字符串aabb 吗？否g. M 2接受字符串ε吗？是1.2 给出练习2.1中画出的机器M 1和M 2的形式描述.M 1=(Q 1,Σ,δ1,q 1,F 1) 其中1）Q 1={q 1,q 2,q 3,};2）Σ={a,b};3415）F 1={q 2}M 2=(Q 2,Σ,δ2,q 2,F 2) 其中1）Q 2={q 1,q 2,q 3,q 4};2）Σ={a,b};3324）F 2={q1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。
试画出此机器的状态图。
db){w | w ⾄少有3个1}c) {w | w 含有⼦串0101}d) {w | w 的长度不⼩于3，且第三个符号为0}e) {w | w 从0开始且为奇长度，或从1开始且为偶长度}或f) {w | w 不含⼦串110}g) {w | w 的长度不超过5}h){w | w 是除11和111以外的任何字符}i){w | w 的奇位置均为1}j) {w | w ⾄少含有2个0，且⾄多含有1个1}k) {ε,0}l) {w | w 含有偶数个0，或恰好两个1}m) 空集 n) 除空串外的所有字符串1.7 给出识别下述语⾔的NFA ，且要求符合规定的状态数。
a. {w | w 以00结束}，三个状态b. 语⾔｛w | w 含有⼦串0101，即对某个x 和y ，w=x0101y ｝，5个状态. 1c. 语⾔｛w | w 含有偶数个0或恰好两个1｝，6个状态。
第三章 上下文无关语言3.1 略。
3.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20，证明上下文无关语言在交的运算下不封闭。
b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。
证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1S →aS|T|εT →bTc|ε对B,构造CFG C 2S →Sc|R|εR →aRb由此知 A,B 均为上下文无关语言。
但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
b.用反证法。
假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL ，且CFL 对并运算封闭，所以B A ⋃也为CFL ，进而知道B A ⋃为CFL ，由DeMorgan 定律B A ⋃＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。
3.3 略。
3.4和3.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。
a. {w | w 至少含有3个1} S →A1A1A1AA →0A|1A|εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数} S →0A|1A A →0B|1B|εB →0A|1A0, ε→ε0,ε→ε 0,ε→ε 1,ε→ε 0,ε→εd. {w | w 的长度为奇数且正中间的符号为0}S →0S0|1S1|0S1|1S0|0e. {w | wS →A1A A →0A1|1A0|1A|AA|εf. {w | w=w R }S →0S0|1S1|1|0g.空集S →S3.6 给出产生下述语言的上下文无关文法：a ． 字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。
S →bSaSaS|aSbSaS|aSaSbS|εb ．语言{a n b n |n ≥0}的补集。
见问题3.25中的CFG:S →aSb|bY|TaT →aT|bT|εc ．{w#x | w, x ∈{0,1}*且w R 是x 的子串}。
S →UVU →0U0|1U1|WW →W1|W0|#V →0V|1V|εd ．{x 1#x 2#⋯#x k |k ≥1, 每一个x i ∈{a,b}* , 且存在i 和j 使得x i ＝x j R }。
S →UVWU →A|εA →aA|bA|#A|#V →aVa|bVb|#B|#B →aB|bB|#B|#W →B|ε3.7 略。
0,ε→0 0,0→ε 0,ε→0 1,0→ε 0,1→ε 0,ε→0 0,0→ε3.8 证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。
<句子>⇒<名词短语><动词短语>⇒<复合名词><动词短语>⇒<冠词><名词><动词短语>⇒a_<名词><动词短语>⇒a_girl_<动词短语>⇒a_girl_<复合名词>⇒a_girl_<动词>< 名词短语>⇒a_girl_touches_< 名词短语>⇒ a_girl_touches_<复合名词><介词短语>⇒a_girl_touches_<冠词><名词><介词短语>⇒a_girl_touches_the_<介词><复合名词>⇒a_girl_touches_the_boy_<介词短语>⇒a_girl_touches_the_boy_<介词><复合名词>⇒a_girl_touches_the_boy_with_<复合名词>⇒a_girl_touches_the_boy_with_<冠词><名词>⇒a_girl_touches_the_boy_with_the_<名词>⇒a_girl_touches_the_boy_with_the_flower含义是：女孩碰这个带着花的男孩<句子>⇒<名词短语><动词短语>⇒<复合名词><动词短语>⇒<冠词><名词><动词短语>⇒a_<名词><动词短语>⇒a_girl_<动词短语>⇒a_girl_<复合动词><介词短语>⇒a_girl_<动词>< 名词短语><介词短语>⇒a_girl_touches_< 名词短语><介词短语>⇒a_girl_touches_<冠词><名词><介词短语>⇒a_girl_touches_the_< 名词><介词短语>⇒a_girl_touches_the_boy_<介词短语>⇒a_girl_touches_the_boy_<介词><复合名词>⇒a_girl_touches_the_boy_with_<复合名词>⇒a_girl_touches_the_boy_with_<冠词><名词>⇒a_girl_touches_the_boy_with_the_<名词>⇒a_girl_touches_the_boy_with_the_flower含义是：女孩用花碰这个男孩3.9 给出产生语言A={a i b j c k| i,j,k≥0且或者i=j或者j=k}的上下文无关文法。
你给出的文法是歧义的吗？为什么？解：下面是产生A的一个CFG:S→UV|ABU→aUb|εV→cV|εA→aA|εB→bUc|ε这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：S⇒UV⇒aUbV⇒abV⇒abcV⇒abcS⇒AB⇒aAV⇒aV⇒abVc⇒abc3.10 给出识别3.9中语言A的下推自动机的非形式描述。
解：其非形式描述为：此PDA有两个非确定性的分支：一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。
另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c, 每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。
开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。
3.13 设有上下文无关文法G:S→TT|UU→0U00|#T→0T|T0|#a.用普通的语言描述L(G)。
b.证明L(G)不是正则的。
解： a. A={0i#0j#0k | i, j, k≥0}⋃{0i#02i | i≥0}。
b. 取s=0p#02p, 则对于任意划分s=xyz(|xy|≤p, |y|>0), xy n z=0p+i#02p∉A,所以不是正则的。
3.14 用定理3.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。
A→BAB|B|εB→00|ε解：添加新起始变元S0, 去掉B→εS0→A S0→AA→BAB|B|εA→BAB|AB|BA|B|εB→00|εB→00去掉A→ε, 去掉A→BS0→A S0→AA→BAB|AB|BA|B|BB A→BAB|AB|BA|00|BBB→00 B→00去掉S 0→A,添加新变元 S 0→BAB|AB|BA|00|BBS 0→VB|AB|BA|UU|BB A →BAB|AB|BA|00|BBA →VB|AB|BA|UU|BB B →00B →UUV →BAU →0问题3.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭。
a. A ⋃B方法一：CFG 。
设有CFG G 1＝(Q 1,∑,R 1,S 1)和G 2=(Q 2,∑,R 2,S 2)且L(G 1)=A, L(G 2)=B 。
构造CFG G=(Q,∑,R,S 0)，其中Q= Q 1⋃Q 2⋃{S 0}, S 0是起始变元，R= R 1⋃R 2⋃{S 0→ S 1|S 2}.方法二：PDA 。
设P 1=(Q 1,∑,Γ1,δ1,q 1,F 1)识别A ，P 2=(Q 1,∑,Γ2,δ2,q 2,F 2)是识别B 。
则如下构造的P=(Q,∑,Γ,δ,q 0,F)识别A ⋃B ，其中1) Q=Q 1⋃Q 2⋃{q 0}是状态集，2) Γ＝Γ1⋃Γ2，是栈字母表，3) q 0是起始状态，4) F ＝F 1⋃F 2是接受状态集，5) δ是转移函数，满足对任意q ∈Q, a ∈∑ε,b ∈Γεδ(q,a,b)=.,)(,,)(,,,,),,,(),,,()},,(),,{(221102121else b Q q b Q q b a q q b a q b a q q q εεεδδεεΓ∈∈Γ∈∈===⎪⎪⎩⎪⎪⎨⎧∅若若若 b. 连接AB方法一：CFG 。
设有CFG G 1＝(Q 1,∑,R 1,S 1)和G 2=(Q 2,∑,R 2,S 2)且L(G 1)=A, L(G 2)=B 。
构造CFG G=(Q,∑,R,S 0)，其中Q= Q 1⋃Q 2⋃{S 0}, S 0是起始变元，R= R 1⋃R 2⋃{S 0→ S 1S 2}.方法二：PDA 。
设P 1=(Q 1,∑,Γ1,δ1,q 1,F 1)识别A ，P 2=(Q 1,∑,Γ2,δ2,q 2,F 2)是识别B ，而且P 1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。
则如下构造的P=(Q,∑,Γ,δ,q 1,F)识别A ⋃B ，其中1) Q=Q 1⋃Q 2是状态集，2) Γ＝Γ1⋃Γ2，是栈字母表，3) q 1是起始状态，4) F ＝F 1⋃F 2是接受状态集，5) δ是转移函数，满足对任意q ∈Q, a ∈∑ε,b ∈Γεδ(q,a,b)=.,,)(,),,,(),,(),(,),,,(,,)},,{(),,(,)(,),,,(222111211111else b Q q b a q b a F q b a q b a F q q b a q b F Q q b a q ∅Γ∈∈≠∈==∈⋃Γ∈-∈⎪⎪⎪⎩⎪⎪⎪⎨⎧εεδεεδεεδδ若若若若c. A *方法一：CFG 。
