自动机理论、语言和计算导论课后习题答案—翻译

Solutions for Section 2.2

Exercise 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。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。

A B

->000r 100r 011r

*000a 100r 011r

*001a 101r 000a

010r 110r 001a

*010a 110r 001a

011r 111r 010a

100r 010r 111r

*100a 010r 111r

101r 011r 100a

*101a 011r 100a

110r 000a 101a

*110a 000a 101a

111r 001a 110a

Exercise 2.2.2

The statement to be proved is δ-hat(q,xy) = δ-hat(δ-hat(q,x),y), and we proceed by induction on the length of y.

证明：通过对|y|进行归纳，来证明δ?(q , xy)=δ?(δ?(q , x) , y) ，具体过程如下：

Basis: If y = ε, then the statement is δ-hat(q,x) = δ-hat(δ-hat(q,x),ε). This statement follows from the basis in the definition of δ-hat. Note that in applying this definition, we must treat δ-hat(q,x)as if it were just a state, say p. Then, the statement to be proved is p = δ-hat(p,ε), which is easy to recognize as the basis in the definition of δ-hat.

基础: y=0，则y=ε。那么需证δ?(q,x)=δ?(δ?(q ,x),ε)，记p=δ?(q,x),命题变为

p=δ?(p ,ε), 由δ?的定义知这显然成立。

Induction: Assume the statement for strings shorter than y, and break y = za, where a is the last symbol of y. The steps converting δ-hat(δ-hat(q,x),y)to δ-hat(q,xy) are summarized in the following table:

归纳: 假设命题对于比y 短的串成立, 且y = za, 其中a是y的结尾符号。δ?(δ?(q,x),y)到δ?(q,xy)的变换总结在下表中:

Expression 表达式Reason 原因

δ?(δ?(q,x),y)Start 开始

δ?(δ?(q,x),za)y=za by assumption 由假设y=za

δ(δ?(δ?(q,x),z),a)Definition of δ-hat, treating δ-hat(q,x) as a state δ?的定义, 把δ?(q,x)看作是一个状态

δ(δ?(q,xz),a)Inductive hypothesis 归纳假设

δ?(q,xza)Definition of δ-hat δ?的定义

δ?(q,xy)y=za

Exercise 2.2.4(a)

The intuitive meanings of states A, B, and C are that the string seen so far ends in 0, 1, or at least 2 zeros.

状态 A, B，C分别表示以１,０和00结尾的串的状态。

0 1

B C A

*C C A

Exercise 2.2.6(a)

The trick is to realize that reading another bit either multiplies the number seen so far by 2 (if it is a 0), or multiplies by 2 and then adds 1 (if it is a 1). We don't need to remember the entire number seen --- just its remainder when divided by 5. That is, if we have any number of the form 5a+b, where b is the remainder, between 0 and 4, then 2(5a+b) = 10a+2b. Since 10a is surely divisible by 5, the remainder of 10a+2b is the same as the remainder of 2b when divided by 5. Since b, is 0, 1, 2, 3, or 4, we can tabulate the answers easily. The same idea holds if we want to consider what happens to 5a+b if we multiply by 2 and add 1.

对于一个二进制整数，如果读入一个比特０，其值等于原数乘以２；否则等于原数乘以２再加以1。而任意一个数均可写成形如5a+b，其中a任意，0<= b <=4，那么输入0，原数变为2(5a+b) = 10a+2b，由于10a是5的倍数,，因此10a+2b除以５的余数与2b相同。输入1，则得2(5a+b)+1类似。因此对于所有的数只要记住它被５除的余数就可以。由于b是 0, 1, 2, 3或者 4, 我们可以容易得到该DPA的转移表，具体如下：

The table below shows this automaton. State qi means that the input seen so far has remainder i when divided by 5.

其中状态qi代表输入串被５除的余数i的状态。

0 1

->*q0 q0 q1

q1 q2 q3

q2 q4 q0

q3 q1 q2

q4 q3 q4

There is a small matter, however, that this automaton accepts strings with leading 0's. Since the problem calls for accepting only those strings that begin with 1, we need an additional state s, the start state, and an additional ``dead state'' d. If, in state s, we see a 1 first, we act like q0; i.e., we go to state q1. However, if the first input is 0, we should never accept, so we go to state d, which we never leave. The complete automaton is:

但是上述自动机仍接受以０开头的字符串。因为题目要求只接受以１开头的串，可增加一个初始状态s和“死亡状态”d。在状态初始状态s, 若看到１，则转到状态q1；若看到０, 则直接转到状态d，识别终止。所求自动机如下:

->s d q1

*q0 q0 q1

q1 q2 q3

q2 q4 q0

q3 q1 q2

q4 q3 q4

d d d

Exercise 2.2.9

Part (a) is an easy induction on the length of w, starting at length 1.

Basis: |w| = 1. Then δ-hat(q0,w) = δ-hat(q f,w), because w is a single symbol, and δ-hat agrees with δ on single symbols.

Induction: Let w = za, so the inductive hypothesis applies to z. Then δ-hat(q0,w) = δ-hat(q0,za) = δ(δ-hat(q0,z),a) = δ(δ-hat(q f,z),a) [by the inductive hypothesis] = δ-hat(q f,za) = δ-hat(q f,w).

证明：a) 通过对w长度的归纳证明。

基础: 若|w| = 1，则w是一个符号，此时需证δ?(q0,w) = δ?(q f,w), 而对于单个符号扩展转移函数δ?与转移函数δ的作用是一样的，得证。

归纳: 令w = za, 假设对于z命题δ?(q0,z) = δ?(q f,z)成立。那么δ?(q0,w) = δ?(q0,za) = δ(δ?(q0,z),a) = δ(δ? (q f,z),a) [由归纳假设] = δ? (q f,za) = δ? (q f,w).

For part (b), we know that δ-hat(q0,x) = q f. Since xε, we know by part (a) that δ-hat(q f,x) = q f. It is then a simple induction on k to show that δ-hat(q0,x k) = q f.

Basis: For k=1 the statement is given.

Induction: Assume the statement for k-1; i.e., δ-hat(q0,xSUP>k-1) = q f. Using Exercise 2.2.2, δ-hat(q0,x k) = δ-hat(δ-hat(q0,x k-1),x) = δ-hat(q f,x) [by the inductive hypothesis] = q f [by (a)].

b) x是属于L(A)的非空串，也即串x被接收，因此δ?(q0,x) = q f，则由 a)知δ?(q f,x) =δ?(q0,x)= q f 。现在通过对k 的归纳来证明δ?(q0,x k) = q f 。

基础: k=1 时，需证δ?(q0,x) = q f ，由已知可得。

归纳：假设对于k-1命题成立，也就是说，δ?(q0,x k-1) = q f 。由练习 2.2.2,δ?(q0,x k) =δ?(δ?(q0,x k-1),x) = δ?(q f,x) [由归纳假设] = q f[由(a)]。

Exercise 2.2.10

The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's.

Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ?(A,w) = A.

Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.

Case 1: a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ? (A,z) = A. The transitions of the DFA tell us δ? (A,w) = A. If w has an odd number

of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.

Case 2: a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(A,z) = A, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case as well, δ-hat(A,w) = A if and only if w has an even number of 1's.

这个自动机表示，状态A表示偶数个1，状态B表示奇数个1，不管串有偶数个还是奇数个1，都会被接受。当且仅当串w中有偶数个1时，δ? (A,w) = A.。用归纳法证明如下

基础: |w| = 0。空串当然有偶数个 1 ，即0个 1，且δ? (A,w) = A.

归纳：假设对于比w 短的串命题成立。令 w = za, 其中 a 为 0 或1。

情形1： a = 0. 如果w有偶数个 1, 则z有偶数个1。由归纳假设，δ? (A,z) = A。由转

移表的DFA知δ?(A,w) = A.如果w有奇数个1, 则z有奇数个1. 由归纳假设，δ? (A,z) =

B, 由转移表的 DFA 知δ? (A,w) = B. 因此这种情况下δ?(A,w) = A 当且仅当 w 有偶数个1。

情形2： a = 1. 如果w有偶数个 1, 则z有奇数个1。由归纳假设，δ? (A,z) = B. 由转

移表的DFA知δ? (A,w) = A. 如果w有奇数个 1, 则z有偶数个1。由归纳假设, δ?(A,z) =

A, 由转移表的DFA知δ? (A,w) = B. 因此这种情况下δ?(A,w) = A 当且仅当 w 有偶数个 1. 综合上述情形，命题得证。

Solutions for Section 2.3

Exercise 2.3.1

Here are the sets of NFA states represented by each of the DFA states A through H: A = {p}; B = {p,q}; C = {p,r}; D = {p,q,r}; E = {p,q,s}; F = {p,q,r,s}; G = {p,r,s};

H = {p,s}.

下表就是利用子集构造法将NFA转化成的DFA。其中构造的子集有：A = {p}; B = {p,q}; C = {p,r}; D = {p,q,r}; E = {p,q,s}; F = {p,q,r,s}; G = {p,r,s}; H = {p,s}.

0 1

->A B A

B D C

C E A

D F C

*E F G

*F F G

*G E H

*H E H

Exercise 2.3.4(a)

The idea is to use a state qi, for i = 0,1,...,9 to represent the idea that we have seen an input i and guessed that this is the repeated digit at the end. We also have state qs, the initial state, and qf, the final state. We stay in state qs all the

time; it represents no guess having been made. The transition table:

记状态qi为已经看到i并猜测i就是结尾将要重复的数字，i = 0,1,...,9 。初始状态为qs，终止状态为qf。我们可以一直停留在状态qs，表示尚未猜测。转移表如下：

0 1 (9)

->qs {qs,q0} {qs,q1} ... {qs,q9}

q0 {qf} {q0} ... {q0}

q1 {q1} {qf} ... {q1}

... ... ... ... ...

q9 {q9} {q9} ... {qf}

*qf {} {} ... {}

Solutions for Section 2.4

Exercise 2.4.1(a)

We'll use q0 as the start state. q1, q2, and q3 will recognize abc; q4, q5, and q6 will recognize abd, and q7 through q10 will recognize aacd. The transition table is:

记q0为初始状态。q1, q2和q3识别 abc; q4, q5和q6 识别abd, q7 到q10 识别aacd. 转移表如下：

a b c d

->q0 {q0,q1,q4,q7} {q0} {q0} {q0}

q1 {} {q2} {} {}

q2 {} {} {q3} {}

*q3 {} {} {} {}

q4 {} {q5} {} {}

q5 {} {} {} {q6}

*q6 {} {} {} {}

q7 {q8} {} {} {}

q8 {} {} {q9} {}

q9 {} {} {} {q10}

*q10 {} {} {} {}

Exercise 2.4.2(a)

The subset construction gives us the following states, each representing the subset of the NFA states indicated: A = {q0}; B = {q0,q1,q4,q7}; C = {q0,q1,q4,q7,q8}; D = {q0,q2,q5}; E = {q0,q9}; F = {q0,q3}; G = {q0,q6}; H = {q0,q10}. Note that F, G and H can be combined into one accepting state, or we can use these three state to signal the recognition of abc, abd, and aacd, respectively.

由子集构造法可得以下DFA的状态，其中每一个状态都是NFA状态的子集： A = {q0}; B = {q0,q1,q4,q7}; C = {q0,q1,q4,q7,q8}; D = {q0,q2,q5}; E = {q0,q9}; F = {q0,q3}; G = {q0,q6}; H = {q0,q10}.注意到 F, G 和H 可以整合到一个接受状态中，或者我们可以用这三个状态来分别标记已识别abc, abd 和aacd。

a b c d

->A B A A A

B C D A A

C C

D

E A

D B A F G

E B A A H

*F B A A A

*G B A A A

*H B A A A

Solutions for Section 2.5

Exercise 2.5.1

For part (a): the closure of p is just {p}; for q it is {p,q}, and for r it is {p,q,r}.

(a): 根据状态的ε闭包的的性质。求得，

p的ε闭包：{p}； q的ε闭包：{p,q}； r的ε闭包：{p,q,r}。

For (b), begin by noticing that a always leaves the state unchanged. Thus, we can think of the effect of strings of b's and c's only. To begin, notice that the only ways to get from p to r for the first time, using only b, c, and ε-transitions are bb, bc, and c. After getting to r, we can return to r reading either b or c. Thus, every string of length 3 or less, consisting of b's and c's only, is accepted, with the exception of the string b. However, we have to allow a's as well. When we try to insert a's in these strings, yet keeping the length to 3 or less, we find that every string of a's b's, and c's with at most one a is accepted. Also, the strings consisting of one c and up to 2 a's are accepted; other strings are rejected.

b) 由于输入a状态总是保持不变，因此只需考虑输入b和c的情况。可以看出，从状态p

第一次到r且只经过b，c和ε转移的路径为bb, bεc和 c ；到r之后，读入b仍可回到r，读入c回到p ，则可通过继续读入串bb, bc和 c回到r。

因此，每一个由b和c组成的长度小于等于3的串可以被接受，除了串b不能接受。向这些串中插入a，并保持长度小于等于3，就会得到所有由a，b，c组成的，至多含有一个a的可被接受的串。由一个c和两个a组成的任意串也是可以被接受的。其它的串均被拒绝。

There are three DFA states accessible from the initial state, which is the εclosure of p, or {p}. Let A = {p}, B = {p,q}, and C = {p,q,r}. Then the transition table is:

由初始状态，即p的ε闭包或者{p}，有3个状态可以达到。令A = {p}, B = {p,q}, C = {p,q,r}。转移表如下：

a b c

->A A B C

B B

C C

*C C C C

Solutions for Section 3.1

Exercise 3.1.1(a)

The simplest approach is to consider those strings in which the first a precedes the first b separately from those where the opposite occurs. The expression: c*a(a+c)*b(a+b+c)* + c*b(b+c)*a(a+b+c)*

首先考虑第一个a在第一个b的前面，然后再考虑相反的情况。表达式为：

c*a(a+c)*b(a+b+c)* + c*b(b+c)*a(a+b+c)*

Exercise 3.1.2(a)

(Revised 9/5/05) The trick is to start by writing an expression for the set of strings that have no two adjacent 1's. Here is one such expression: (10+0)*(ε+1)

To see why this expression works, the first part consists of all strings in which every 1 is followed by a 0. To that, we have only to add the possibility that there is a 1 at the end, which will not be followed by a 0. That is the job of (ε+1).

首先写出没有两个1相邻的串的集合，如下：(10+0)*(ε+1)。表达式的第一部分表示每个1之后都紧跟一个0的这样的串组成。为了表示结尾可能是1的情况，则可在串尾处加上(ε+1)。

Now, we can rethink the question as asking for strings that have a prefix with no adjacent 1's followed by a suffix with no adjacent 0's. The former is the expression we developed, and the latter is the same expression, with 0 and 1 interchanged. Thus, a solution to this problem is (10+0)*(ε+1)(01+1)*(ε+0). Note that the ε+1 term

in the middle is actually unnecessary, as a 1 matching that factor can be obtained from the (01+1)* factor instead.

题目要求的串可由两部分组成，也就是，前缀没有相邻的1，后缀没有相邻的0。前半部分也就是已经给出的(10+0)*(ε+1)，根据对称性后半部分可将上式的1和0交换得到。所求即为(10+0)*(ε+1)(01+1)*(ε+0)。注意中间的ε+1 项没有作用，因为1可以由后面的(01+1)*项得到。因此最后得到的正则表达式为(10+0)*(01+1)*(ε+0)

Exercise 3.1.4(a)

This expression is another way to write ``no adjacent 1's.'' You should compare it with the different-looking expression we developed in the solution to Exercise 3.1.2(a). The argument for why it works is similar. (00*1)*says every 1 is preceded by at least one 0. 0* at the end allows 0's after the final 1, and (ε+1) at the beginning allows an initial 1, which must be either the only symbol of the string or followed by a 0. 你可以与练习3.1.2(a)中我们给出的不同样子的表达式作比较。为什么起作用的原因是类似的。

这个表达式是“没有相邻的1”的另一种描述方式。(00*1)*表示每个 1 的前面都至少有一个0做前缀。最后的0*允许在最后一个1后面有0。开头的(ε+1) 允许初始为1，要么串就只有这一个符号，要么后面跟着的就是0。

Exercise 3.1.5

The language of the regular expression ε. Note that ε* denotes the language of strings consisting of any number of empty strings, concatenated, but that is just the set containing the empty string.

正则表达式ε。ε*表示由任意多个空串组成的串，也是只包含空串的集合。

Solutions for Section 3.2

Exercise 3.2.1

Part (a): The following are all R0 expressions; we list only the subscripts. R11 = ε+1; R12 = 0; R13 = phi; R21 = 1; R22 = ε; R23 = 0; R31 = phi; R32 = 1; R33 = ε+0.

a) 下面就是所有 R0的表达式；我们只写出下标： R11 = ε+1；R12 = 0; R13 = Φ(phi); R21 = 1; R22 = ε; R23 = 0; R31 = Φ(phi); R32 = 1; R33 = ε+0.

Part (b): Here all expression names are R(1); we again list only the subscripts. R11 = 1*; R12 = 1*0; R13 = phi; R21 = 11*; R22 = ε+11*0; R23 = 0; R31 = phi; R32 = 1; R33 = ε+0.

b) 下面就是所有 R(1)的表达式；我们只写出下标：R11 = 1*; R12 = 1*0; R13 = phi; R21 = 11*; R22 = ε+11*0; R23 = 0; R31 = phi; R32 = 1; R33 = ε+0.

Part (e): Here is the transition diagram转移图:

If we eliminate state q2 we get:

如果消除状态q2，有:

Applying the formula in the text, the expression for the ways to get from q1 to q3 is: [1 + 01 + 00(0+10)*11]*00(0+10)*

由课本中的公式，q1到q3的正则表达式：[1 + 01 + 00(0+10)*11]*00(0+10)*

Exercise 3.2.4(a)

利用定理3。7每个用正则表达式来定义的语言也可用穷自动机来定义

Exercise 3.2.6(a)

(Revised修改 1/16/02) LL* or L+.

Exercise 3.2.6(b)

The set of suffixes of strings in L. (以)L中串(作为)后缀/下标的集合。

Exercise 3.2.8

Let R(k)ijm be the number of paths from state i to state j of length m that go through

no state numbered higher than k. We can compute these numbers, for all states i and j, and for m no greater than n, by induction on k.

令R(k)ijm为从状态i到状态j，长度为m，且没有经过编号大于k的路径的个数。对于所有状态I和j，以及m（m≤n），通过对k归纳来计算这个个数。

Basis: R0ij1 is the number of arcs (or more precisely, arc labels) from state i to state j. R0ii0 = 1, and all other R0ijm's are 0.

基础: k=0，R0ij1是由状态i到状态j的箭弧（更准确的说，是箭弧标号）的个数。R0ii0 = 1,其他的R0ijm's 都为0。

Induction: R(k)ijm is the sum of R(k-1)ijm and the sum over all lists (p1,p2,...,pr) of positive integers that sum to m, of R(k-1)ikp1 * R(k-1)kkp2 *R(k-1)kkp3 *...* R(k-1)kkp(r-1) * R(k-1)kjpr. Note r must be at least 2.

归纳: R(k)ijm是R(k-1)ijm的和，R(k-1)ikp1 * R(k-1)kkp2 *R(k-1)kkp3 *...* R(k-1)kkp(r-1) * R(k-1)kjpr。

(p1,p2,...,pr)是所有和为m的正整数序列，r大于等于2。

The answer is the sum of R(k)1jn, where k is the number of states, 1 is the start state, and j is any accepting state.

答案就是R(k)1jn的总和，其中k是状态个数，1为开始状态，j是任意接受状态。

Solutions for Section 3.4

Exercise 3.4.1(a)

Replace R by {a} and S by {b}. Then the left and right sides become {a} union {b} = {b} union {a}. That is, {a,b} = {b,a}. Since order is irrelevant in sets, both languages are the same: the language consisting of the strings a and b.

将R替换为{a}，S替换为{b}。等式变为{a} +{b} = {b} +{a}. 也就是{a,b} = {b,a}. 因为集合中元素的顺序是无关紧要的，所以，等式两边是一样的：由串a和b构成的语言。

Exercise 3.4.1(f)

Replace R by {a}. The right side becomes {a}*, that is, all strings of a's, including the empty string. The left side is ({a}*)*, that is, all strings consisting of the concatenation of strings of a's. But that is just the set of strings of a's, and is therefore equal to the right side.

将R替换为{a}。右边变为{a}*, 代表a组成的所有串，包含空串。左边是({a}*)*, 代表由a组成的串构成的串，也就是由a构成的串。当然相等。

Exercise 3.4.2(a)

Not the same. Replace R by {a} and S by {b}. The left side becomes all strings of a's and b's (mixed), while the right side consists only of strings of a's (alone) and strings of b's (alone). A string like ab is in the language of the left side but not the right.

不等。将R替换为{a}，S替换为{b}。左边表示所有由a和b（可混合）构成的串。而右边表示只有a构成的串和只有b构成的串。像ab这样的串就只属于左边的语言，而不属于右边。

Exercise 3.4.2(c)

Also not the same. Replace R by {a} and S by {b}. The right side consists of all strings composed of zero or more occurrences of strings of the form a...ab, that is, one or more a's ended by one b. However, every string in the language of the left side has to end in ab. Thus, for instance, ε is in the language on the right, but not on the left.

不等。举反例，将R替换为{a}，S替换为{b}。右边表示由0个或多个形如a...ab组成的串，也就是，一个或多个a后面紧跟一个结尾的b。但是，左边的串必须以ab结尾。因此，ε属于右边的语言，但不属于左边。

Solutions for Section 4.1

Exercise 4.1.1(c)

Let n be the pumping-lemma constant (note this n is unrelated to the n that is a local variable in the definition of the language L). Pick w = 0n10n. Then when we write w = xyz, we know that |xy| <= n, and therefore y consists of only 0's. Thus, xz, which must be in L if L is regular, consists of fewer than n 0's, followed by a 1 and exactly n0's. That string is not in L, so we contradict the assumption that L is regular.

令n为泵引理常数（这个n与语言L的定义中的局部变量n无关）。设w = 0n10n。把w打断为w = xyz，满足|xy| <= n, 则y只由 0构成。若L是正则的，那么xz一定在L中。但xz由少于n个0，后面跟着一个1和恰好n个0构成。这个串不在L中。所以L不是正则语言。

Exercise 4.1.2(a)

Let n be the pumping-lemma constant and pick w = 0n2, that is, n2 0's. When we write w = xyz, we know that y consists of between 1 and n0's. Thus, xyyz has length between n2 + 1 and n2 + n. Since the next perfect square after n2 is (n+1)2 = n2 + 2n + 1, we know that the length of xyyz lies strictly between the consecutive perfect squares n2and (n+1)2. Thus, the length of xyyz cannot be a perfect square. But if the language were regular, then xyyz would be in the language, which contradicts the assumption

that the language of strings of 0's whose length is a perfect square is a regular language.

令n为泵引理常数，设w = 0n2,也就是n2个0。将w打断为w = xyz。y是由大于1小于n个0组成的。因此xyyz的长度介于n2 + 1和n2 + n之间。n2的下一个完全平方数是(n+1)2 = n2 + 2n + 1。因为xyyz的长度介于n2和(n+1)2之间。所以xyyz的长度不是完全平方数。若语言是正则的，那么xyyz也应该是正则的。xyyz的长度应该是完全平方数。矛盾。所以语言不是正则的。

Exercise 4.1.4(a)

We cannot pick w from the empty language. 我们无法从空集中找到w，因为y非空。Exercise 4.1.4(b)

If the adversary picks n = 3, then we cannot pick a w of length at least n.

如果对手选择n=3，那么我们无法找到长度至少为n的w。

Exercise 4.1.4(c)

The adversary can pick an n > 0, so we have to pick a nonempty w. Since w must consist of pairs 00 and 11, the adversary can pick y to be one of those pairs. Then whatever i we pick, xy i z will consist of pairs 00 and 11, and so belongs in the language.

对手选择n > 0, 我们就要选择一个非空的w。因为w必须由成对的00 和 11组成，对手可以选择这些对中的一个。那么不管我们选择什么样的i，xy i z都由00 和 11组成，所以属于语言。

Solutions for Section 4.2

Exercise 4.2.1(a)

aabbaa.

Exercise 4.2.1(c)

The language of regular expression a(ab)*ba.

正则表达式语言a(ab)*ba

Exercise 4.2.1(e)

Each b must come from either 1 or 2. However, if the first b comes from 2 and the second comes from 1, then they will both need the a between them as part of h(2)

and h(1), respectively. Thus, the inverse homomorphism consists of the strings {110, 102, 022}.

每个b必须来自1或2 。如果第一个b来自2和第二个来自1，那么将需要两个a在他们之间分别作为h(2) 和 h(1)的一部分，这种情况不行。因此，逆同态组成的字符串{110, 102, 022} 。

Exercise 4.2.2

Start with a DFA A for L. Construct a new DFA B, that is exactly the same as A, except that state q is an accepting state of B if and only if δ(q,a)is an accepting state of A. Then B accepts input string w if and only if A accepts wa; that is, L(B) = L/a.

首先从L 的一个DFA A出发。我们构造一个DFA B，满足当且仅当δ(q,a)是 A的一个接受状态时，状态 q才是 B的一个接受状态。因此，当且仅当A 接受 wa时，B 接受输入串 w；即L(B) = L/a。(DFA的语言是正则的)

Exercise 4.2.5(b)

We shall use D a for ``the derivative with respect to a.'' The key observation is that if epsilon is not in L(R), then the derivative of RS will always remove an a from the portion of a string that comes from R. However, if epsilon is in L(R), then the string might have nothing from R and will remove a from the beginning of a string in L(S) (which is also a string in L(RS). Thus, the rule we want is:

我们用 D a表示导数a'。关键是，如果ε不在L(R)中, 则RS 的导数总是能从R 的字符串中去掉a。如果ε在L(R)中, 则R 可能是空，这时从L(S)的字符串头去掉a . 因此，总的规则就是:

If epsilon is not in L(R), then D a(RS) = (D a(R))S. Otherwise, D a(RS) = D a(R)S + D a(S). 如果ε不在L(R)，则 D a(RS) = (D a(R))S. 否则， D a(RS) = D a(R)S + D a(S).

Exercise 4.2.5(e)

L may have no string that begins with 0. L 中没有以0开始的字符串. Exercise 4.2.5(f)

This condition says that whenever 0w is in L, then w is in L, and vice-versa. Thus, L must be of the form L(0*)M for some language M(not necessarily a regular language) that has no string beginning with 0.

这个条件说明如果 0w在L中,则 w 就在L中, 反之亦然。因此，L 必须是这样的形式L(0*)M，其中语言M没有包含以0开始的串。

In proof, notice first that D0(L(0*)M = D0(L(0*))M union D0(M) = L(0*)M. There are two reasons for the last step. First, observe that D0 applied to the language of all strings of 0's gives all strings of 0's, that is, L(0*). Second, observe that because M has no string that begins with 0, D0(M)is the empty set [that's part (e)].

证明：首先 D0(L(0*)M)= ( D0(L(0*))M (union) D0(M) ) = L(0*)M 。存在两个条件。首先, D0是所有由0组成的字符串语言的导数得到的由0组成的串, 即 L(0*)。其次，由于M 没有以0开头的串, D0(M) 就是一个空集。

We also need to show that every language N that is unchanged by D0 is of this form. Let M be the set of strings in N that do not begin with 0. If N is unchanged by D0, it follows that for every string w in M, 00...0w is in N; thus, N includes all the strings of L(0*)M. However, N cannot include a string that is not in L(0*)M. If x were such a string, then we can remove all the 0's at the beginning of x and get some string y that is also in N. But y must also be in M.

仍需证没有被D0作用的每个语言N 都满足这种形式。令M 是N的一个不以0开头的子集。若N is unchanged by D0, 则对于每一个在M 中的w, 00...0w 存在于N中；因此，N 包含了所有 L(0*)M，N不能包含L(0*)M之外的串。如果x 是这样的串,我们去掉x串前面的

0得到y，则y在N中。并且y 必须存在于M中。

Exercise 4.2.8

Let A be a DFA for L. We construct DFA B for half(L). The state of B is of the form [q,S], where:

令 A 是L 的一个DFA 。我们为half(L)构造一个 DFA B 。状态 B 满足形式 [q,S]，其中：

q is the state A would be in after reading whatever input B has read so far.

q是这样一个状态： A在读入B已经读入的任意输入后将要进入的状态。

S is the set of states of A such that A can get from exactly these states

to an accepting state by reading any input string whose length is the same as the length of the string B has read so far.

S 是A的一个状态集，使得 A 能够通过读入任意的长度和B已经读入的串长一样的

串，从这些状态而到达一个接收状态。

It is important to realize that it is not necessary for B to know how many inputs it has read so far; it keeps this information up-to-date each time it reads a new symbol. The rule that keeps things up to date is: δB([q,S],a) = [δA(q,a),T], where T is the set of states p of A such that there is a transition from p to any state of S on any input symbol. In this manner, the first component continues to simulate A, while the second component now represents states that can reach an accepting state following a path that is one longer than the paths represented by S.

首先对于 B来说，没有必要知道已经输入多少个串；它要保证每次读入一个新的符号都要更新。保证更新的规则: δB([q,S],a) = [δA(q,a),T], 其中T 是A的一个状态集p 使得输入任意一个符号都能够使p 转换到状态S。在这种情况下，第一个条件继续模拟A,第二个条件表示一个接受状态，这是根据一个比S表示的路径还要长的路径。

To complete the construction of B, we have only to specify:

为了完成 B的构造，我们指出:

The initial state is [q

0,F], that is, the initial state of A and the accepting states of A. This choice reflects the situation when A has read 0 inputs: it is still in its initial state, and the accepting states are exactly the ones that can reach an accepting state on a path of length 0.

The accepting states of B are those states [q,S] such that q is in S. The

justification is that it is exactly these states that are reached by some string of length n, and there is some other string of length n that will take state q to an accepting state.

始状态 [q

0,F],也是, A的初始状态和接受状态。这满足了当A 的输入是0时的情况：它还是在初始状态，它的接收状态是能够通过0长度路经到达的接收状态。

B的接收状态是状态 [q,S]，使得 q 在 S中。这是因为这些状态是通过符号长度为

的串到达的状态，并且存在另一个长度为n的串使得状态 q 到达一个接受状态。Exercise 4.2.13(a)

Start out by complementing this language. The result is the language consisting of all strings of 0's and 1's that are not in 0*1*, plus the strings in L0n1n. If we intersect with 0*1*, the result is exactly L0n1n. Since complementation and intersection with a regular set preserve regularity, if the given language were regular then so would be L0n1n. Since we know the latter is false, we conclude the given language is not regular.

从补语言出发。补语言由所有的通过0's和1's组成的串，除了 0*1*, 加上 L0n1n中的串。如果我们和 0*1*作交运算，结果就是L0n1n。因为补运算和交运算保持正则, 如果给定的语言是正则的，则L0n1n也是正则的。因为后者不是正则的，所以我们得到给定的语言不是正则的。

Exercise 4.2.14(c)

Change the accepting states to be those for which the first component is an accepting state of A L and the second is a nonaccepting state of A M. Then the resulting DFA accepts if and only if the input is in L - M.

把接收状态转换成那些第一部分是 A L的接收状态并且第二部分是A M的非接受状态。当且仅

当输入是在L – M中是，接受得到的DFA 。

Solutions for Section 4.3

Exercise 4.3.1

Let n be the pumping-lemma constant. Test all strings of length between n and 2n-1 for membership in L. If we find even one such string, then L is infinite. The reason is that the pumping lemma applies to such a string, and it can be ``pumped'' to show an infinite sequence of strings are in L.

令 n 是泵引理中的常量。测试L中长度在n 和 2n-1 之间的所有符号串。如果能够找到一个串，则L 是无穷的。理由是把它作为“泵”得到了无穷的结果串，这些串都在 L中。

Suppose, however, that there are no strings in L whose length is in the range n to 2n-1. We claim there are no strings in L of length 2n or more, and thus there are only a finite number of strings in L.

假设L中不存在这样的串，其长度在n 到2n-1之间。我们称L中不存在长度大于等于2n 的串，因此L的串都是有穷的。

In proof, suppose w is a string in L of length at least 2n, and w is as short as any string in L that has length at least 2n. Then the pumping lemma applies to w, and we can write w = xyz, where xz is also in L. How long could xz be? It can't be as long as 2n, because it is shorter than w, and w is as short as any string in L of length 2n or more. n, because xz is at most n shorter than w. Thus, xz is of length between n and 2n-1, which is a contradiction, since we assumed there were no strings in L with a length in that range.

假设 w 是L 中一个长度至少为 2n的串，并且w 和 L中长度至少为2n的任意串的长度一样短。然后w作为“泵”， w = xyz, 其中 xz 在L中。xz 的长度不可能超过2n, 因为它比 w短而w和 L中长度为2n或者大于2n的串的长度相等,因为 xz 的长度最多比w短n，因此 xz 的长度在 n 和2n-1之间, 这与假设 L中不存在这样的串矛盾。

Solutions for Section 4.4

Exercise 4.4.1

Revised 10/23/01.

B|x

C|x x

D|x x x

E|x x x

F|x x x x

G| x x x x x

H|x x x x x x x

---------------

A B C D E F G

0 1

->AG B F A G

BF A G C E

CE D BF

*D D AG

H A G D

Note, however, that state H is inaccessible, so it should be removed, leaving the first four states as the minimum-state DFA.

Note, however, 状态 H 是从初始状态出发不可达的，所以它应该被去掉, 剩下前面四个状态为最小状态DFA.

Solutions for Section 5.1

Exercise 5.1.1(a)

S -> 0S1 | 01

Exercise 5.1.1(b)

S -> AB | CD

A -> aA | ε

B -> bBc | E | cD

C -> aCb | E | aA

D -> cD | ε

E -> bE | b

To understand how this grammar works, observe the following:

A generates zero or more a's.

D generates zero or more c's.

E generates one or more b's.

B first generates an equal number of b's and c's, then produces either one

or more b's (via E) or one or more c's (via cD). That is, B generates strings in b*c* with an unequal number of b's and c's.

Similarly, C generates unequal numbers of a's then b's.

Thus, AB generates strings in a*b*c*with an unequal numbers of b's and c's,

while CD generates strings in a*b*c* with an unequal number of a's and b's.

Exercise 5.1.1(b)

S -> AB | CD

A -> aA | ε

B -> bBc | E | cD

C -> aCb | E | aA

D -> cD | ε

E -> bE | b

意思如下:

A产生0或者一个或多个a。.

D 产生0或者一个或多个 c。

E产生一个或多个b。

B产生式中 b和 c的个数一样多，然后产生一个或多个b (通过E) 或一个或多个

c 通过cD)。即， B产生这样的字符串 b*c* ，其中b和 c的个数不相等。

同样， C产生 a和 b个数不相等的字符串。

因此，AB产生字符串 a*b*c* ，并且b和 c的数目不同； CD 产生字符串 a*b*c*

并且a和 b的数目不同。

Exercise 5.1.2(a)

Leftmost: S => A1B => 0A1B => 00A1B => 001B => 0010B => 00101B => 00101

Rightmost: S => A1B => A10B => A101B => A101 => 0A101 => 00A101 => 00101

Exercise 5.1.2(a)

最左推导： S => A1B => 0A1B => 00A1B => 001B => 0010B => 00101B => 00101

最有推导: S => A1B => A10B => A101B => A101 => 0A101 => 00A101 => 00101

Exercise 5.1.5

S -> S+S | SS | S* | (S) | 0 | 1 | phi | e

The idea is that these productions for S allow any expression to be, respectively, the sum (union) of two expressions, the concatenation of two expressions, the star of an expression, a parenthesized expression, or one of the four basis cases of expressions: 0, 1, phi, and ε.

Exercise 5.1.5

S -> S+S | SS | S* | (S) | 0 | 1 | phi | e

英语课后翻译答案新

U n i t1 1. 任何年满18岁的人都有资格投票。(be eligible to, vote) Anyone over the age of 18 is eligible to vote. 2. 每学期开学前，这些奖学金的申请表格就会由学校发给每一个学生。(apply for, scholarship) A form to apply for these scholarships is sent by the university to every student before the start of every semester. 3. 遵照医生的建议，我决定戒烟。(on the advice of) On the advice of my doctor, I decided to give up smoking. 4. 公园位于县城的正中央。(be located in) The park is located right in the center of town. 5. 这所大学提供了我们所需的所有材料和设备。(facilities) The university provides all the materials and facilities we desire. 1. 他们花了多年的时间寻找内心的平静，但是收效甚微。(search for) They spent many years searching for peace of mind, but with little success. 2. 这种新药的成功研制已经使许多疾病的治疗发生了根本性的变革。

计算机组成原理_第四版课后习题答案(完整版)[]

第一章 1．比较数字计算机和模拟计算机的特点 解：模拟计算机的特点：数值由连续量来表示，运算过程是连续的；数字计算机的特点：数值由数字量（离散量）来表示，运算按位进行。两者主要区别见 P1 表 1.1 。 2．数字计算机如何分类？分类的依据是什么？ 解：分类：数字计算机分为专用计算机和通用计算机。通用计算机又分为巨型机、大型机、 中型机、小型机、微型机和单片机六类。分类依据：专用和通用是根据计算机的效率、速度、价格、运行的经济性和适应性来划分的。 通用机的分类依据主要是体积、简易性、功率损耗、性能指标、数据存储容量、 指令系统规模和机器价格等因素。 3．数字计算机有那些主要应用？（略） 4．冯 . 诺依曼型计算机的主要设计思想是什么？它包括哪些主要组成部分？ 解：冯 . 诺依曼型计算机的主要设计思想是：存储程序和程序控制。存储程序：将解题的程序（指令序列）存放到存储器中；程序控制：控制器顺序执行存储的程序，按指令功能控制全机协调地完成运算任务。 主要组成部分有：控制器、运算器、存储器、输入设备、输出设备。 5．什么是存储容量？什么是单元地址？什么是数据字？什么是指令字？ 解：存储容量：指存储器可以容纳的二进制信息的数量，通常用单位KB MB GB来度量，存储 容 量越大，表示计算机所能存储的信息量越多，反映了计算机存储空间的大小。单元地址：单元地址简称地址，在存储器中每个存储单元都有唯一的地址编号，称为单元地 址。 数据字：若某计算机字是运算操作的对象即代表要处理的数据，则称数据字。指令字：若某计算机字代表一条指令或指令的一部分，则称指令字。 6．什么是指令？什么是程序？ 解：指令：计算机所执行的每一个基本的操作。程序：解算某一问题的一串指令序列称为该问题的计算程序，简称程序。 7．指令和数据均存放在内存中，计算机如何区分它们是指令还是数据？ 解：一般来讲，在取指周期中从存储器读出的信息即指令信息；而在执行周期中从存储器中读出的信息即为数据信息。

翻译理论与实践课后习题答案

第一章翻译概论 第一节中外翻译史简介 四、课练习 1. 东汉至唐宋时期。 2. 玄奘不仅译出了 75 部佛经，而且还把老子的部分著作译成梵文，成为第一个向国外介绍汉语著作的中国人。 3. 20 世纪初的“五四”新文化运动，开创了白话文学和白话翻译的新纪元，语言从文言正宗转为白话本位。五四运动前后，东西方各国的优秀文学作品，特别是俄国和苏联的作品开始被介绍进来，《共产党宣言》等一批马克思主义著作的译文就发表在“五四”时期，为中国后来的革命做了充分的理论和思想准备。 4. 圣经的翻译成为了西方翻译研究的重要源头之一。 5. 中外悠久的翻译历史已为我们积累了一份宝贵的文化遗产。我们应当认真总结前人的翻译经验，借鉴吸收前人从实践中总结出的理论、方法，以便继续提高我们的翻译水平，为中外文化交流做出自己的贡献。 五、课后练习 （一）将下列段落译成中文： 一百年前的今天：一些海鸥；北卡罗来纳州杀魔山海岸警卫队的三个队员；救生站以及一些本地人，见证了威尔帕·莱特(Wilbur Wright)和奥维尔·莱特(Orville Wright)兄弟的第一次机动飞机飞行。 1903 年 12 月 17 日，莱特兄弟第一次用比空气重的飞行器进行了有动力的持续飞行。 1932 年， 90 英尺高的杀魔山顶立起了一座 60 英尺高的花岗岩纪念碑，用以纪念这两个来自俄亥俄州代顿市的梦想家。莱特兄弟来自于美国中部。他们有着天空般广阔的眼界，也有着十分务实的作风。1892 年，他们在俄亥俄州的代顿开创了自己的自行车企业：莱特自行车公司。虽然在当时世纪之交的美国，有着数不清的自行车公司，但只有一个在造轮子的同时造出了翅膀。当莱特兄弟在 1903 年最终着眼于动力载人飞行器，他们成功地使世界变小了…… （二）将下列段落译成英文： As Jia baoyu，Xue Baoqin，Xing youyan and Ping’er had birthdays on the same day，the young ladies held a hilarious drinking party in the hall of the peony garden for them. When it was Xiangyun’s turn to compose a verse amid a drinking game，she made fun of the maids by saying， holding a duck head in hand，“This ya tou （referring to the duck head in hand） is not that ya tou （referring to the maids around， as both are homophones in Chinese）， for this ya tou has applied no hair oil….” Everybody roared with laughter. Some maids protested， laughing，“You made fun of us， so you have to drink another cup. Let’s pour a full cup her….”As the party went on drinkers’ games continued with ceaseless laughter and people suddenly noticed that Xiangyun had disappeared. While they looked this way and that，a maid rushed in laughing，“ Young ladies. Hurry to have a look at the Lady Xiangyun. She’s sleeping on the stone bench over there.” The group tiptoed over，and sure enough，saw Xiangyun sleeping soundly. Fallen flowers scattered on her body，her hair and her face. Her fan had dropped on the ground aside. Bees danced in the air around her. Under her head was a make-shift pillow of peony flowers wrapped with

大学英语三课后习题翻译及答案

Unit 1 From her accent I guess she’s from the Northeast. 从她的口音我猜她是来自东北地区的。 It was very clever of her to turn his argument against himself. 她很聪明，使他对自己的论点 I found a couple of shoes under the bed but they don’t make a pair. 我在床下发现了一双鞋，但他们不做一双 4. Dr. Bright always takes his time as he examines his patients and treats them with extreme care. Bright博士总是把他的时间用于他检查他的病人，并把他们的极端护理 5. British companies are trying to avoid the fate their American counterparts have already suffered. 英国公司正试图避免他们的美国同行已经遭受的命运。 6. Wilfred’s remarks confirmed me in my opinion that he was an honorable young man. 威尔弗雷德的话证实了我在我看来，他是一个光荣的年轻人 7. The key witness for the prosecution was offered police protection after she received death threats. 检察机关的主要证人在收到死亡威胁后提供了警方的保护 8. I thought that was the end of the matter but subsequent events proved me wrong. 我认为这是事情的结束，但随后的事件证明我错了。 9. Having practiced for so long, the New York baseball team stands a chance winning the World Series this year. 经过这么长时间的练习，纽约棒球队赢得了今年的世界系列赛的机会。 10. At the trial , Bob’s teacher, who was called as a character witness, said he was a quiet boy who had never been in trouble before. 在审讯中，鲍伯的老师，被称为证人，说他是个安静的男孩以前从未惹过麻烦。 Unit 2 11. We’ve just had a very fruitful meeting with the management and we’re now much more hopeful about the pay rise. 我们刚刚与管理层有了一个非常富有成效的会议，我们现在对加薪的希望更大了 12. The book I’m reading explains the evolution of plant and animal life on earth. 我读的这本书解释了地球上动植物的进化

计算机组成原理第二版课后习题答案

第1章计算机系统概论 1. 什么是计算机系统、计算机硬件和计算机软件？硬件和软件哪个更重要？ 解： 计算机系统：由计算机硬件系统和软件系统组成的综合体。 计算机硬件：指计算机中的电子线路和物理装置。 计算机软件：计算机运行所需的程序及相关资料。 硬件和软件在计算机系统中相互依存，缺一不可，因此同样重要。 2. 如何理解计算机的层次结构？ 答：计算机硬件、系统软件和应用软件构成了计算机系统的三个层次结构。 （1）硬件系统是最内层的，它是整个计算机系统的基础和核心。 （2）系统软件在硬件之外，为用户提供一个基本操作界面。 （3）应用软件在最外层，为用户提供解决具体问题的应用系统界面。 通常将硬件系统之外的其余层称为虚拟机。各层次之间关系密切，上层是下层的扩展，下层是上层的基础，各层次的划分不是绝对的。 3. 说明高级语言、汇编语言和机器语言的差别及其联系。 答：机器语言是计算机硬件能够直接识别的语言，汇编语言是机器语

言的符号表示，高级语言是面向算法的语言。高级语言编写的程序（源程序）处于最高层，必须翻译成汇编语言，再由汇编程序汇编成机器语言（目标程序）之后才能被执行。 4. 如何理解计算机组成和计算机体系结构？ 答：计算机体系结构是指那些能够被程序员所见到的计算机系统的属性，如指令系统、数据类型、寻址技术组成及I/O机理等。计算机组成是指如何实现计算机体系结构所体现的属性，包含对程序员透明的硬件细节，如组成计算机系统的各个功能部件的结构和功能，及相互连接方法等。 5. 冯?诺依曼计算机的特点是什么？ 解：冯?诺依曼计算机的特点是：P8 ●计算机由运算器、控制器、存储器、输入设备、输出设备五大 部件组成； ●指令和数据以同同等地位存放于存储器内，并可以按地址访 问； ●指令和数据均用二进制表示； ●指令由操作码、地址码两大部分组成，操作码用来表示操作的 性质，地址码用来表示操作数在存储器中的位置； ●指令在存储器中顺序存放，通常自动顺序取出执行； ●机器以运算器为中心（原始冯?诺依曼机）。

翻译理论的习题及答案

~ 关于翻译理论的习题 选择题 1、直译保存了原作____,因而能达到与原文近似的效果。 A内容 B思想 C风格 D手法 2、死译只注意保存原文____,对原文使用的词语，句子结构，比喻以及其他修辞手法，尽量原封不动地照搬过来。 A 形式 B风格 C 意义 D 内容 3、译文中若出现译语词不搭配的现象，就会产生_____。 A 翻译调 B翻译病 C 翻译症 D翻译腔 4、( _____与内容的关系。 5、克服翻译症的方法之一是弄清 A 形式 B风格 C意义 D表面 5、从实用翻译理论的角度来看，译文不但要保存原作的思想风格，而且必须符合译语习惯，即提高____。 A随意性 B传意性 C相似性 D可接受性 6、有的动物可通过动作，如蜜蜂的舞蹈，来传递某种信息，这属于_____。 A自然信息 B动物信息 C 非语言信息 D语言信息 7、交流思想通过语言进行，因而语言是交流思想的___ A物质 B工具 C媒介 D手段 8、。 ____,七分靠____。9、有人认为翻译外国小说等文学作品。三分靠 A外语，汉语 B汉语，外语 C外语，外语 D汉语，汉语

9、翻译症的主要特征是____。 A文从句顺 B流畅易懂 C声情并茂 D文笔拙劣 10、不可以的情况有___ A没有对等词 B内容和形式必须兼顾的情况 C词外含义 D A，B and C 1-5 DACAD 6-10 BCBAD } 简答题 1、结合具体事例你谈谈对“英语重形合，汉语重意合”这句话的理解。 形合指句子内部的链接或句子间的连接采用句法手段或词汇手段，意合指句子内部的链接或句子间的连接采用语义手段。印欧语言重形合，语句各成分的相互结合常用适当的链接词语或各种语言链接手段，以表示其结构关系。汉语重意合，句子各成分之间或句子之间的结合多依靠语义的贯通，少用连接语，所以句法结构形式短小精悍。 2、有人认为翻译的总体发展趋势是由归化逐步趋向与异化，你是否赞同这个观点 归化与异化作为翻译两种主要的翻译方法，一直是翻译界研究和争论的焦点之一。归化指以目的语文化为归宿，要求译者向目的语读者靠拢，采取目的语读者所习惯的表达方式，来传达原文的内容。异化指以源语文化为归宿，要求译者向作者靠拢采取目的语读者所习惯的表达方式来传达原文的内容。

全新版大学英语3综合教程课后习题翻译原题及答案

1.我们的计算机系统出了毛病，但我觉得问题不大 We have a problem with the computer system, but I think it’s fairly minor. 2.父亲去逝的时候我还小,不能独立生活。就在那时，家乡的父老接过了教育我的责任。My father died when I was too young to live on my own. The people of my hometown took over my upbringing at that point. 3.这些玩具必须得达到严格的安全要求后才可出售给儿童 The toys have to meet strict safety requirements before they can be sold to children. 4.作为新闻和舆论的载体，广播和电视补充了而不是替代了报纸。 Radio and television have supplemented rather than replaced the newspaper as carriers of news and opinion. 5.至于这本杂志，它刊载了世界各地许多报纸杂志上文章的摘要 When it comes to this magazine, it is/ carries a digest of articles from many newspapers and magazines around the world. 1.虽然受到全球金融危机后果的巨大影响，但是我们仍然相信我们能够面对挑战，克服危机。Though greatly affected by the consequences of the global financial crisis, we are still confident that we can face up to the challenge and overcome the crisis. 2.在持续不断的沙尘暴的威胁下，我们被迫离开我们喜爱的村庄，搬迁到新的地方。 Under threat of constant sand storms, we were compelled to leave our cherished village and move to the new settlement. 3.根据最近的网上调查，许多消费者说他们也许会有兴趣考虑购买电视广告中播放的产品。According to a recent online survey, a lot of consumers say they may be motivated to consider buying products shown in TV commercials. 4.看到卡车司机把受污染的废弃物倒在河边，老人马上向警方报告 Having spotted a truck driver dumping contaminated waste alongside the river, the old man reported to the police at once. 5.一些科学家坚信人们总有一天会喜欢转基因农作物的，因为它们能够提高产量，帮助发展 中国家战胜饥荒和疾病 Some scientists hold to the firm conviction that people will come to like genetically modified crops someday since they can increase yields and help combat hunger and disease in the developing world. 1.无论是在城市还是农村，因特网正在改变人们的生活方式。 The Internet is changing the way people live, whether they are in urban or rural areas. 2.和大公司相比，中小公司更容易受到金融危机的威胁。 Medium-sized and small companies are more vulnerable to the threat of the global economic crisis than large ones. 3.关于期末论文，教授要求我们先分析失业图表，然然后对过家的经济发展提供批评性的见解。 With regard to our term paper, the professor asked us to analyze the unemployment chart first, and then provide critical reflections on the nations economic development. 4.他从来也没有想到他们队会大比分赢得那场篮球赛。 It never occurred to him that their team would win the basketball match by a large margin.

计算理论课后题及答案2

第三章 上下文无关语言 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 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →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 →A1A1A1A A →0A|1A|ε b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A 0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε

翻译理论与技巧(A)精彩试题集及问题详解

翻译理论与技巧(A)试题集及答案 (红色为自己所出题) 一 Fill in the blanks. According to sociosemiotic theories, meaning consists of three aspects: _________, ___________ and ____________ . As far as communicative function is concerned, English sentences can be classified into four types: ____________ , ___________ , _____________ and ___________ . Professor Xu Yuanzhong ever proposed that literary translation should conform to the principle of “____________, __________ and ___________”. The basic procedures of translation are made up of three steps: __________, ___________ and ___________ . Peter Newmark divided the function of language into six kinds, among which the most important four functions are ____________, ___________ , __________ and ___________ . “Literal translation” is based on -language-oriented principle, while “liberal translation” is based on -language-oriented principle. Translators often abide by -oriented principle when they translate literary works When we see the sun, we often think of hope. It’s the meaning of the sun we in fact think of. Yan Fu’s standard for good translation is , and . According to Peter Newmark, the expression “How do you do?” performs ___________ function. We should analyze , and before we really put something into the target language. According to the structure, English sentences can be classified into sentences, ___________ sentences, sentences and sentences. The three principles for translation advocated by Alexander Fraser Tytler are: ① ②③ The sentence “The earth goes around the sun” performs the function of language. When we hear somebody speaks ungrammatically, we know that he is not well-educated. Here the language carries the meaning. According to the different signs that translation deals with, translation can be classified into , , . Translation can be regarded as a , a or a . According to different topics, translation can be classified into sssssss translation, translation and translation. 二 Translating the following sentences into Chinese. Their host carved, poured, served, cut bread, talked, laughed, proposed healths.

英语课后翻译答案

Unit1 1、任何年满18岁得人都有资格投票。(be eligible to, vote) Anyone over the age of 18 is eligible to vote、 2、每学期开学前，这些奖学金得申请表格就会由学校发给每一个学生。(apply for, scholarship) A form to apply for these scholarships is sent by the university to every student before the start of every semester、 3、遵照医生得建议，我决定戒烟。(on the advice of) On the advice of my doctor, I decided to give up smoking、 4、公园位于县城得正中央。(be located in) The park is located right in the center of town、 5、这所大学提供了我们所需得所有材料与设备。(facilities) The university provides all the materials and facilities we desire、 1、她们花了多年得时间寻找内心得平静，但就是收效甚微。(search for) They spent many years searching for peace of mind, but with little success、 2、这种新药得成功研制已经使许多疾病得治疗发生了根本性得变革。(revolutionize) The successful development of the new drug has revolutionized the treatment of many diseases、 3、由于这个国家得经济不景气，这家公司濒于破产。(on the edge of) The company is on the edge of bankruptcy due to the economic depression in the country、 4、大学毕业后她成为了一名护士。她认为护士这一职业可能很有发展前途。(rewarding) He became a nurse after college、He thought nursing could be a very rewarding career、 5、她像往常一样在文件上签了名。(just as) He signed his name on the paper just as he has always done it、 Unit2

新视野大学英语课后习题翻译答案

新视野大学英语课后习 题翻译答案 -CAL-FENGHAI.-(YICAI)-Company One1

新视野大学英语（第二版）读写教程2 1至7单元课后翻译答案总结 IA：她连水都不愿意喝一口，更别提留下来吃饭了。 She wouldn’t take a drink , much less would she stay for dinner. 他认为我在对他说谎，但实际上我讲的是实话。 He thought I was lying to him , whereas I was telling the truth. 这个星期你每天都迟到，对此你怎样解释 How do you account for the fact you have been late every day this week 他们利润增长的部分原因是采用了新的市场策略。 The increase in their profits is due to their new market strategy. 这样的措施很可能会带来工作效率得提高。 Such measures are likely to result in the improvement of work efficiency.

我们已经在这个项目上投入了大量时间和精力，所以我们 只能继续。 We have already poured a lot of time and energy into the project , so we have to carry on. IIA: 尽管她是家里的独生女，他父母也从不溺爱她。 Despite the fact that she is the only child in the family , her parents never baby her . 迈克没来参加昨晚的聚会，也没有给我打电话作任何解 释。 Mike didn’t come to the party last night , nor did he call me to give an explanation. 坐在他旁边的那个人确实发表过一些小说，但绝不是什么 大作家。 The man sitting next to him did publish some novels , but he is by no means a great writer. 他对足球不感兴趣，也从不关心谁输谁赢。 He is not interested in football and is indifferent to who wins or loses.

翻译理论与实践(笔译)期末复习及答案

浙江广播电视大学 英语专业(开放本科) 《翻译理论与实践》期末复习 题型： 一、选择题（每小题2分，共20分） 二、翻译句子。（每小题3分，共30分） 三、篇章翻译（每小题40分，共40分） 四、案例分析题（每小题10分，共10分） 一、选择题（每小题2分，共20分） 1.美国语言学家罗曼.雅各布森把翻译分成__________。 A. 语内翻译 B. 语际翻译 C. 符际翻译 D. 以上选项都正确 2. 下面哪个选项是错误的？_________。 A. dry goods：纺织品B．white goods：白色的货物 C．white wine：白葡萄酒D．toilet water：花露水 3. “This is a special offer and is not subject to our usual discounts” 请问下面哪个译文最合适？________。 A. 这是特殊报盘，不以我方通常折扣为条件。 B. 这是特惠报盘，我方通常折扣不适应于此盘。 C. 此系特惠报盘，不另加我方通常折扣。 D. 这是特殊报盘，不局限于我们通常折扣。 4．下面哪句话的描述是错误的？________。 A．美国著名翻译理论家奈达提出了“动态对等”原则。 B．“动态对等”原则是指，运用交际理论和信息论的原理，将焦点从传统的译文与原文两个文本的比较转移到两个过程的比较，使人们注意到影响信息接收的各种语言和文化因素。C．奈达曾将“动态对等”的提法改成了“功能对等”原则。 D．翻译求的是“形式对等”，而非”动态对等”。

5．_________提出了“美化之艺术，创优似竞赛”的翻译理念。 A．尤金.奈达B．泰特勒 C．许渊冲D．鲁迅 6. 下面哪个配对是错误的？_____。 A．赤脚医生：barefoot doctor B．纸老虎：paper tiger C．to show one’s cards：摊牌D．大海捞针：look for a needle in sea D B C D C D 7.哪句话的描述是正确的？______。 A. 严复提出的翻译是：重神似不重形似 B. 傅雷的翻译标准是：信、达、雅 C. 许渊冲的翻译标准是：美化之艺术，创优似竞赛 D. 泰特勒的翻译标准是：通顺 8. 下面哪个选项是错误的？_________。 A. dry State：实行禁酒的州B．white goods：白色的货物 C．dry white wine：涩白酒D．toilet water：花露水 9. 泰特勒(Tytler)提出的著名翻译原则是：_______。 A. 译文应完整地再现原文的思想内容。 B. 译文的风格、笔调应与原文的性质相同。 C. 译文应像原文一样流畅自然。 D. 以上选项都正确。 10．下面哪个选项是正确的？________。 A．bring down the house 翻译为：“推倒房子” B．pull up one's socks 翻译为：鼓起勇气 C．think a great deal of oneself 翻译为：“为自己想得很多” D．an apple of love 翻译为：“爱情之果” 11．A book, tight shut, is but a block of paper.下面哪个译文是最合适的？_____。A．一本书，紧紧合上，只是一叠纸。 B．一本书，如果紧紧合上不读，只是一叠纸。 C．一本书，如果紧紧合上不读，只是一叠废纸。 D．闲置之书只是一叠废纸。

新视野大学英语课后习题翻译答案

新视野大学英语（第二版）读写教程2 1至7单元课后翻译答案总结 IA：她连水都不愿意喝一口，更别提留下来吃饭了。 She wouldn’t take a drink , much less would she stay for dinner. 他认为我在对他说谎，但实际上我讲的是实话。 He thought I was lying to him , whereas I was telling the truth. 这个星期你每天都迟到，对此你怎样解释? How do you account for the fact you have been late every day this week？ 他们利润增长的部分原因是采用了新的市场策略。 The increase in their profits is due to their new market strategy. 这样的措施很可能会带来工作效率得提高。 Such measures are likely to result in the improvement of work efficiency. 我们已经在这个项目上投入了大量时间和精力，所以我们只能继续。 We have already poured a lot of time and energy into the project , so we have to carry on. IIA: 尽管她是家里的独生女，他父母也从不溺爱她。 Despite the fact that she is the only child in the family , her parents never baby her .

计算机组成原理课后习题答案(一到九章)

作业解答 第一章作业解答 1.1 基本的软件系统包括哪些内容？ 答：基本的软件系统包括系统软件与应用软件两大类。 系统软件是一组保证计算机系统高效、正确运行的基础软件，通常作为系统资源提供给用户使用。包括：操作系统、语言处理程序、数据库管理系统、分布式软件系统、网络软件系统、各种服务程序等。 1.2 计算机硬件系统由哪些基本部件组成？它们的主要功能是什么？ 答：计算机的硬件系统通常由输入设备、输出设备、运算器、存储器和控制器等五大部件组成。 输入设备的主要功能是将程序和数据以机器所能识别和接受的信息形式输入到计算机内。 输出设备的主要功能是将计算机处理的结果以人们所能接受的信息形式或其它系统所要求的信息形式输出。 存储器的主要功能是存储信息，用于存放程序和数据。 运算器的主要功能是对数据进行加工处理，完成算术运算和逻辑运算。 控制器的主要功能是按事先安排好的解题步骤，控制计算机各个部件有条不紊地自动工作。 1.3 冯·诺依曼计算机的基本思想是什么？什么叫存储程序方式？ 答：冯·诺依曼计算机的基本思想包含三个方面： 1) 计算机由输入设备、输出设备、运算器、存储器和控制器五大部件组成。 2) 采用二进制形式表示数据和指令。 3) 采用存储程序方式。 存储程序是指在用计算机解题之前，事先编制好程序，并连同所需的数据预先存入主存储器中。在解题过程（运行程序）中，由控制器按照事先编好并存入存储器中的程序自动地、连续地从存储器中依次取出指令并执行，直到获得所要求的结果为止。 1.4 早期计算机组织结构有什么特点？现代计算机结构为什么以存储器为中心？ 答：早期计算机组织结构的特点是：以运算器为中心的，其它部件都通过运算器完成信息的传递。 随着微电子技术的进步，人们将运算器和控制器两个主要功能部件合二为一，集成到一个芯片里构成了微处理器。同时随着半导体存储器代替磁芯存储器，存储容量成倍地扩大，加上需要计算机处理、加工的信息量与日俱增，以运算器为中心的结构已不能满足计算机发展的需求，甚至会影响计算机的性能。为了适应发展的需要，现代计算机组织结构逐步转变为以存储器为中心。 1.5 什么叫总线？总线的主要特点是什么？采用总线有哪些好处？ 答：总线是一组可为多个功能部件共享的公共信息传送线路。 总线的主要特点是共享总线的各个部件可同时接收总线上的信息，但必须分时使用总线发送信息，以保证总线上信息每时每刻都是唯一的、不至于冲突。 使用总线实现部件互连的好处： ①可以减少各个部件之间的连线数量，降低成本； ②便于系统构建、扩充系统性能、便于产品更新换代。 1.6 按其任务分，总线有哪几种类型？它们的主要作用是什么？ 答：按总线完成的任务，可把总线分为：CPU内部总线、部件内总线、系统总线、外总线。

翻译理论与实践试题及答案讲解

翻译理论与实践试题 一、选择题（在四个选项中选择一个正确答案）：20% 1. 中国古代佛经翻译家------提出了“既须求真，又须喻俗”的翻译思想。 A. 鸠摩罗什 B. 玄奘 C．安世高D。释道安 2. 严复说的“一名之立，旬月踟躇”是指---------------------。 A. 翻译一部书要化一个月时间作准备 B 翻译一个术语往往要考虑很久 C.只有化苦功才能翻译成一部名著 D.书名的翻译颇费思量 3..下列四句，----句的表述是不正确的。 A. 鲁迅提出过“宁信而不顺”的翻译观点。 B. 马建忠主张“善译”的翻译标准。 C. 钱钟书认为文学翻译的最高标准是“化”。 D. 傅雷认为文学翻译的最高境界是“形似”。 4.下列四位翻译家中，英译《红楼梦》的是------。 A. 林语堂 B. 杨宪益 C. 杨必 D. 鲁迅 5.英国语言学家M.A.K.Halliday提出的构成语境三要素中，fields of discourse指---------------------------。 A. 交际内容 B. 交际方式 C. 交际风格 D. 交际地点 6. 多用被动语态是----------的一个比较明显的语法特点。 A. 广告英语 B. 科技英语 C. 新闻英语 D. 法律英语 7. “意译”是指译文从意义出发，要求将原文的意义正确表达出来，不必拘泥于------的形式。 A.词句 B. 词句和比喻 C. 各种修辞手段 D. 词、句、以及各种修辞手段 8.. ------翻译了莎士比亚的全部戏剧作品。 A. 朱生豪 B. 卞之琳 C. 梁实秋 D. 林语堂 9. fast, firm, secure三个同义词中，firm的正规程度介于前后两者之间，由此可以判定，它最有可能源自------。 A. 法语 B. 拉丁语 C.盎格鲁-撒克逊语 D. 德语 10. 下列四种“语体”中，--------的语言最为正规。 A. 广告英语 B. 法律英语 C. 新闻英语 D. 科技英语 二、问答题：30% 1. 为什么严复要在他的翻译标准中加上一个“雅”字？你认为现在我们应该怎样理解 这个“雅”字？