下载文档原格式
第三章 上下文无关语言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 的个数的两倍的所有字符串组成的集合。
![计算理论导引习题答案[第2版]CHAP5new](https://img.taocdn.com/s1/m/14a23d6565ce0508773213a8.png)
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 步，若有接受，则接受。
第1章概述习题(答案)一．选择题1. D2. B3. CD4. C5. ABC6. A7. B8. B9. ABCD 10. ABCDE二．简答题1．什么是计算机系统？计算机系统是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统，由计算机硬件系统和计算机软件系统两大部分组成。
2．请解释冯•诺依曼所提出的“存储程序”概念。
把程序和数据都以二进制的形式统一存放在存储器中，由机器自动执行。
不同的程序解决不同的问题，实现了计算机通用计算的功能。
3．控制器的主要功能是什么？控制器基本功能就是从内存中取出指令和执行指令，即控制器按程序计数器指出的指令地址从内存中取出该指令进行译码，然后根据该指令功能向有关部件发出控制命令，执行该指令。
另外，控制器在工作过程中，还要接受各部件反馈回来的信息。
4．简述CPU和主机的概念。
通常把运算器、控制器做在一个大规模集成电路块上称为中央处理器，又称CPU(Central Processing Unit)。
通常把内存储器、运算器和控制器合称为计算机主机，也可以说主机是由CPU与内存储器组成的，而主机以外的装置称为外部设备，外部设备包括输入/输出设备，外存储器等。
5．什么是计算机软件？计算机软件的分类有哪些？软件是指用来指挥计算机运行的各种程序的总和以及开发、使用和维护这些程序所需的技术文档。
计算机软件系统分为系统软件和应用软件。
计算机系统软件由操作系统、语言处理系统、以及各种软件工具等组成，指挥、控制计算机硬件系统按照预定的程序运行、工作，从而达到预定的目标。
应用软件是用户利用计算机软、硬件资源为解决各类应用问题而编写的软件，包括用户程序及其说明性文件资料。
6．计算机有哪些主要的特点？(1)运算速度快、精度高计算机的字长越长，其精度越高，现在世界上最快的计算机每秒可以运算几十万亿次以上。
一般计算机可以有十几位甚至几十位(二进制)有效数字，计算精度可由千分之几到百万分之几，是任何计算工具所望尘莫及的。
计算机导论(第 2 版)【清华大学出版社】课后习题答案第一章绪论一、简答题1.什么是计算机？（P1）计算机是一种能够按照事先存储的程序，自动、高速的对数据进行输入、处理、输出和存储的系统。
一个计算机系统包括硬件和软件两大部分。
2.解释冯•诺依曼所提出的“存储程序”概念。
（P6）把计算机程序与数据都以二进制的形式统一存放在存储器中，由机器自动执行。
不同的程序解决不同的问题，实现了计算机通用计算的功能。
3.计算机有哪些主要的特点？（P3-P4）○1运算速度快○2运算精度高○3具有记忆能力○4具有逻辑判断能力○5存储程序4．计算机有哪些主要的用途？（P4-P5）○1科学计算○2数据处理○3实时控制○5人工智能○5计算机辅助工程和辅助教育○6娱乐与游戏5．计算机发展中各个阶段的主要特点是什么？（P6-P8）第一代计算机（1946 年—1957 年）○1逻辑器件使用电子管○2用穿孔卡片机作为数据和指令的输入设备○3用磁鼓或磁带作为外存储器○4使用机器语言编译第二代计算机（1958 年—1964 年）○1用晶体管代替了电子管○2内存储器采用了磁心体○3引入了寄存器和浮点运算硬件○4利用I/O处理机提高了输入输出能力○5在软件方面配置了子程序库和批处理管理程序，并且推出了FORTRAN、COBOL、ALGOL 等高级程序设计语言及相应的编译程序第三代计算机（1965 年—1971 年）○1用小规模或中小规模的集成电路来代替晶体管等分立元件○2用半导体存储器代替磁心存储器○3使用微程序设计技术简化处理机的结构○4在软件方面则广泛引入多道程序、并行处理、虚拟存储系统以及功能完备的操作系统，同时还提供了大量的面向用户的应用程序第四代计算机（1972 年至今）○1使用了大规模和超大规模集成电路○2使用了大容量的半导体存储器作为内存储器○3在体系结构方面进一步发展了并行处理、多机系统、分布式计算机系统和计算机网络系统○4在软件方面则推出了数据库系统、分布式操作系统以及软件工程标准等第五代计算机主要特征是人工智能，具有一些人类智能的属性。
第三章上下文没关语言略。
a. 利用语言 A={a m b n c n | m,n0} 和 A={a n b n c m | m,n0} 以及例，证明上下文没关语言在交的运算下不关闭。
b.利用 (a) 和 DeMorgan律( 定理，证明上下文没关语言在补运算下不关闭。
证明： a. 先说明 A,B 均为上下文没关文法，对 A 结构 CFG C1S aS|T|T bTc|对 B, 结构 CFG C2S Sc|R|R aRb由此知 A,B 均为上下文没关语言。
0} 不是上下文没关语言，所以上下文无可是由例 , A ∩B={a n b n c n|n 关语言在交的运算下不关闭。
b. 用反证法。
假定 CFL在补运算下关闭，则对于 (a) 中上下文没关语言A,B，A , B也为 CFL，且 CFL对并运算关闭，所以A B也为 CFL，从而知道 A B 为CFL，由DeMorgan定律 A B ＝A∩B，由此A∩B是CFL,这与 (a) 的结论矛盾，所以 CFL对补运算不关闭。
略。
和给出产生下述语言的上下文没关文法和PDA，其中字母表={0,1} 。
a.{w | w起码含有3个1}0,1,1S→A1A1A1A,1,1,1 A→0A|1A|b.{w | w以同样的符号开始和结束}S→0A0|1A10,1,A→0A|1A|0,00,01,11,1c. {w | w的长度为奇数}0,1,0,1,S →0A|1AA →0B|1B|B →0A|1Ad. {w | w 的长度为奇数且正中间的符号为 0}S →0S0|1S1|0S1|1S0|00, 0 0,0 1,1,0,$ 0,,$e. {w | w 中 1 比 0 多}1,00,1 0S →A1A0, ,11,1 ,$,1,$A →0A1|1A0|1A|AA|f. {w | w=w R }S →0S0|1S1|1|00, 0 0,0 1, 1 1,1 ,1, ,$$ 0,,g. 空集S →S给出产生下述语言的上下文没关文法：a ．字母表 {a,b} 上 a 的个数是b 的个数的两倍的全部字符串构成的会合。
定义概念题目：第三章：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，ω是一个串。
Operation X Y127410505 X mod Y X127410505X Y105051274 X mod Y X3131274X Y1274313 X mod Y X22313X Y31322X mod Y X522X Y225X mod Y X25X Y52X mod Y X12X Y21X mod Y X01X Y10当Y=0时，输出X=1，所以1274和10505是互素的。
对于字符串w=baba和下面的文法CFG G，试填写定理中识别上下文无关语言的多项式时间算法中所描述的表。
S RTR TR|aT RT|bT R,T S R,T,SR S ST R,TR下面的公式是可满足得吗=(x y)(x y)(x y)( x y)解:(x,y)共有四种取值：(true, true),(true, false),(false, true),(false, false).分别将其带入公式得：若(x,y)=(true, true)，=(true true) (true false) (false true) (false false)=false若(x,y)=(true, false)，=(true false) (true true) (false false) (false true)=false若(x,y)=(false, true)，=(false true) (false false) (true true) (true false)=false若(x,y)=(false, false),=(false false) (false true) (true false) (true true)=false所以原公式不可满足。
证明P在并、连接和补运算下封闭。
(1) 并：对任意 L1, L2P，设有n a时间图灵机M1和n b时间图灵机M2判定它们，且c=max{a,b}。
对L1L2构造判定器M:M=“对于输入字符串w :1)在w上运行M1，在w上运行M2。
9.1 证明TIME(2n)=TIME(2n+1).证明：2n=O(2n+1)TIME(2n)TIME(2n+1).2n+1=O(2n)TIME(2n+1)TIME(2n).所以TIME(2n)=TIME(2n+1).9.2证明TIME(2n)TIME(22n)。
注：这里“”是严格包含。
证明：令f(n)=22n,则f(n)/logf(n)=22n/2n, 由时间层次定理有TIME(o(22n/2n))TIME(22n).又由于2n=o(22n/2n)，TIME(2n)TIME(o(22n/2n))，所以TIME(2n)TIME(22n).9.3 证明NTIME(n)PSPACE.证明：NTIME(n)NSPACE(n)SPACE(n2)SPACE(n3)PSPACE.9.6 证明若A P，则P A＝P。
证明：首先P P A。
这是因为不带谕示即可。
下面证明P A P。
任取A P，则存在多项式图灵机T判定A。
设B P A，则存在带语言A的谕示的多项式时间图灵机M A判定B。
如下构造不带谕示的图灵机D：D=“对于输入串w:1)在w上运行M A。
2)每当M A要在谕示带上写下某个字符串x，则在x上运行T，若T接受，则代替谕示回答x属于A，否则代替谕示回答x不属于A。
3)若M A接受，则接受；否则，拒绝。
”设M A的运行时间是n a，T的运行时间是n b。
谕示带上写下的字符串的长度不会超过n a，询问谕示带的次数也不会超过n a。
D的运行时间是n a (n a)b=n a+ab，所以A P。
9.7 给出带指数的正则表达式，产生如下在字母表{0,1}上的语言：a.所有长为500的字符串. (01)500。
b.所有长度不超过500的字符串.(01)500.c.所有不少于500的字符串. (01)500(01)*.d.所有长度不等于500的字符串. (01)499(01)501(01)*.e.所有恰好包含500个1的字符串. 0*(10*)500.f.所有包含至少500个1的字符串. (01)*(1(01)*)500.g.包含至多500个1的字符串. 0*((1)0*)500.h.所有长度不少于500并且在第500个位置上是0的字符串. (01)4990(01)*.i.所有包含两个0并且其间至少相隔500个符号的字符串。
