计算理论导引习题答案

计算理论习题解答练习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}; 3为：415） 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}; 3）δ为：32是起始状态 4） F 2={q 1,q 4}1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。

试画出此机器的状态图。

d1.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开始且为偶长度}f) {w | w 不含子串110}0,1g) {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 ，且要求符合规定的状态数。

0,10,11a. {w | w以00结束}，三个状态b. 语言｛w | w含有子串0101，即对某个x和y，w=x0101y｝，5个状态.c. 语言｛w | w含有偶数个0或恰好两个1｝，6个状态。

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 步，若有接受，则接受。

计算理论习题答案CHAP2new2.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 nb nc n|n ≥0}不是上下⽂⽆关语⾔，所以上下⽂⽆关语⾔在交的运算下不封闭。

b.⽤反证法。

假设CFL 在补运算下封闭，则对于(a)中上下⽂⽆关语⾔A,B ，A ,B也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进⽽知道BA ?为CFL ，由DeMorgan 定律B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论⽭盾，所以CFL 对补运算不封闭。

2.4和2.5 给出产⽣下述语⾔的上下⽂⽆关⽂法和PDA ，其中字母表∑={0,1}。

a. {w | w ⾄少含有3个1}S →A1A1A1A A →0A|1A|ε0, ε→εb. {w | w 以相同的符号开始和结束}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|0e. {w | w 中1⽐0多}S →A1A0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε 0,ε→0 0,0→εA →0A1|1A0|1A|AA|εf. {w | w=w R }S →0S0|1S1|1|0g. 空集S →S2.6 给出产⽣下述语⾔的上下⽂⽆关⽂法：a ．字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。

第三章 上下文无关语言与下推自动机a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数}0, ε→ε0,ε→ε 0,ε→ε1,ε→ε0,ε→εS →0A|1A A →0B|1B|ε B →0A|1Ad.{w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0e.{w | wS →A1AA →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|Ta T →aT|bT|εc ．{w#x | w, x ∈{0,1}*且w R 是x 的子串}。

S →UV0,ε→0,0→0,ε→1,0→0,1→0,ε→0,0→U→0U0|1U1|WW→W1|W0|#V→0V|1V|εd．{x1#x2#⋯#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.14解：添加新起始变元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去掉S0→A, 添加新变元S0→BAB|AB|BA|00|BB S0→VB|AB|BA|UU|BBA→BAB|AB|BA|00|BB A→VB|AB|BA|UU|BBB→00 B→UUV→BAU→03.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭---答案。

计算方法引论课后答案第一章误差1.什么是模型误差，什么是方法误差？例如，将地球近似看为一个标准球体，利用公式 $A=4\pi r$ 计算其表面积，这个近似看为球体的过程产生的误差即为模型误差。

在计算过程中，要用到 $\pi$，我们利用无穷乘积公式计算 $\pi$ 的值：pi=2\cdot\frac{2}{1}\cdot\frac{2}{3}\cdot\frac{4}{3}\cdot\f rac{4}{5}\cdot\frac{6}{5}\cdot\frac{6}{7}\cdot\frac{8}{7}\cdot\ frac{8}{9}\cdot\cdots我们取前9项的乘积作为 $\pi$ 的近似值，得$\pi\approx3.xxxxxxxx5$。

这个去掉 $\pi$ 的无穷乘积公式中第9项后的部分产生的误差就是方法误差，也称为截断误差。

2.按照四舍五入的原则，将下列各数舍成五位有效数字：816.956，76.000，.322，501.235，.182，130.015，236.23.解：816.96，76.000，.501.24，.130.02，236.23.3.下列各数是按照四舍五入原则得到的近似数，它们各有几位有效数字？81.897，0.008，136.320，050.180.解：五位，三位，六位，四位。

4.若 $1/4$ 用 0.25 表示，问有多少位有效数字？解：两位。

5.若 $a=1.1062$，$b=0.947$，是经过舍入后得到的近似值，问：$a+b$，$a\times b$ 各有几位有效数字？已知 $da<\frac{1}{2}\cdot10^{-4}$，$db<\frac{1}{2}\cdot10^{-3}$，又 $a+b=0.\times10$。

begin{aligned}d(a+b)&=da+db\leq da+db=\frac{1}{2}\cdot10^{-4}+\frac{1}{2}\cdot10^{-3}=0.55\times10^{-3}<\frac{1}{2}\cdot10^{-2}end{aligned}所以 $a+b$ 有三位有效数字；因为 $a\timesb=0.xxxxxxxx\times10$。

第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)运算速度快、精度高计算机的字长越长，其精度越高，现在世界上最快的计算机每秒可以运算几十万亿次以上。

一般计算机可以有十几位甚至几十位(二进制)有效数字，计算精度可由千分之几到百万分之几，是任何计算工具所望尘莫及的。

Solutions for Section 2.2Exercise 2.2.1(a)States correspond to the eight combinations of switch positions, and also must indicate whether the previous roll came out at D, i.e., whether the previous input was accepted. Let 0 represent a position to the left (as in the diagram) and 1 a position to the right. Each state can be represented by a sequence of three 0's or 1's, representing the directions of the three switches, in order from left to right. We follow these three bits by either a indicating it is an accepting state or r, indicating rejection. Of the 16 possible states, it turns out that only 13 are accessible from the initial state, 000r. Here is the transition table:杠杆可能出现8种情况，影响着最终状态。

并且也要说明，前面一个大理石球是否从D滚出，也就是说，前一个输入是否被接受。

令0 代表向左方的状态（如图表），1 代表向右方。

这三个杠杆的每一个状态都可以用三个数（0或1）组成的序列表示。

这个序列后面跟着字母a或者r。