5034657600自動(dòng)機(jī)理論語(yǔ)言和計(jì)算導(dǎo)論課后習(xí)題答案(中文版)

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

2、 right. each state can be represented by a sequence of three 0s or 1s, 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 o

3、nly 13 are accessible from the initial state, 000r. here is the transition table: 杠桿可能出現(xiàn)8種情況，影響著最終狀態(tài)。并且也要說(shuō)明，前面一個(gè)大理石球是否從d滾出，也就是說(shuō)，前一個(gè)輸入是否被接受。令 0 代表向左方的狀態(tài)（如圖表）， 1 代表向右方。這三個(gè)杠桿的每一個(gè)狀態(tài)都可以用三個(gè)數(shù)（0或1）組成的序列表示。這個(gè)序列后面跟著字母a或者r。a代表接受狀態(tài)，r代表拒絕狀態(tài)。16種可能的狀態(tài)中，只有13種是從初始狀態(tài)000r可達(dá)的。下面它的有窮自動(dòng)機(jī)的轉(zhuǎn)移表。 a b-000r 100r 011r*000a 100r

4、 011r*001a 101r 000a010r 110r 001a*010a 110r 001a011r 111r 010a100r 010r 111r*100a 010r 111r101r 011r 100a*101a 011r 100a110r 000a 101a*110a 000a 101a111r 001a 110aexercise 2.2.2the statement to be proved is -hat(q,xy) = -hat(-hat(q,x),y), and we proceed by induction on the length of y. 證明：通過(guò)對(duì)|y|進(jìn)行歸

5、納，來(lái)證明(q , xy)=(q , x) , y) ，具體過(guò)程如下： 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

6、is p = -hat(p,), which is easy to recognize as the basis in the definition of -hat. 基礎(chǔ): =0，則y=。那么需證(q,x)=(q ,x),)，記p=(q,x),命題變?yōu)?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

7、 -hat(q,xy) are summarized in the following table: 歸納: 假設(shè)命題對(duì)于比 y短的串成立, 且y = za, 其中 a 是y的結(jié)尾符號(hào)。(q,x),y) 到(q,xy) 的變換總結(jié)在下表中: expression 表達(dá)式reason 原因(q,x),y) start 開始(q,x),za) y=za by assumption 由假設(shè)y=za(q,x),z),a) definition of -hat, treating -hat(q,x) as a state 的定義, 把(q,x) 看作是一個(gè)狀態(tài)(q,xz),a) inductive hy

8、pothesis 歸納假設(shè)(q,xza) definition of -hat 的定義(q,xy) y=zaexercise 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. 狀態(tài) a, b，c分別表示以,和00結(jié)尾的串的狀態(tài)。0 1-a b ab c a*c c aexercise 2.2.6(a)the trick is to realize that reading another bit eithe

9、r 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 dont 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)

10、 = 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. 對(duì)于一個(gè)二進(jìn)制整數(shù)，如果讀入

11、一個(gè)比特，其值等于原數(shù)乘以；否則等于原數(shù)乘以再加以1。而任意一個(gè)數(shù)均可寫成形如5a+b，其中a任意，0= b *q0 q0 q1q1 q2 q3q2 q4 q0q3 q1 q2q4 q3 q4there is a small matter, however, that this automaton accepts strings with leading 0s. since the problem calls for accepting only those strings that begin with 1, we need an additional state s, the start

12、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: 但是上述自動(dòng)機(jī)仍接受以開頭的字符串。因?yàn)轭}目要求只接受以開頭的串，可增加一個(gè)初始狀態(tài)s和“死亡狀態(tài)”d。在狀態(tài)初始狀

13、態(tài)s, 若看到，則轉(zhuǎn)到狀態(tài)q1；若看到, 則直接轉(zhuǎn)到狀態(tài)d，識(shí)別終止。所求自動(dòng)機(jī)如下: 0 1-s d q1*q0 q0 q1q1 q2 q3q2 q4 q0q3 q1 q2q4 q3 q4d d dexercise 2.2.9part (a) is an easy induction on the length of w, starting at length 1. basis: |w| = 1. then -hat(q0,w) = -hat(qf,w), because w is a single symbol, and -hat agrees with on single symbols

14、. induction: let w = za, so the inductive hypothesis applies to z. then -hat(q0,w) = -hat(q0,za) = (-hat(q0,z),a) = (-hat(qf,z),a) by the inductive hypothesis = -hat(qf,za) = -hat(qf,w). 證明：a) 通過(guò)對(duì)w長(zhǎng)度的歸納證明。 基礎(chǔ): 若|w| = 1，則w 是一個(gè)符號(hào)，此時(shí)需證(q0,w) = (qf,w), 而對(duì)于單個(gè)符號(hào)擴(kuò)展轉(zhuǎn)移函數(shù)與轉(zhuǎn)移函數(shù)的作用是一樣的，得證。 歸納: 令w = za, 假設(shè)對(duì)于z命題(

15、q0,z) = (qf,z)成立。那么(q0,w) = (q0,za) = (q0,z),a) = ( (qf,z),a) 由歸納假設(shè) = (qf,za) = (qf,w). for part (b), we know that -hat(q0,x) = qf. since x, we know by part (a) that -hat(qf,x) = qf. it is then a simple induction on k to show that -hat(q0,xk) = qf. basis: for k=1 the statement is given. induction: a

16、ssume the statement for k-1; i.e., -hat(q0,xsupk-1) = qf. using exercise 2.2.2, -hat(q0,xk) = -hat(-hat(q0,xk-1),x) = -hat(qf,x) by the inductive hypothesis = qf by (a). b) x是屬于l(a)的非空串，也即串x被接收，因此(q0,x) = qf ，則由 a)知(qf,x) =(q0,x)= qf ?，F(xiàn)在通過(guò)對(duì)k 的歸納來(lái)證明(q0,xk) = qf 。基礎(chǔ): k=1 時(shí)，需證(q0,x) = qf ，由已知可得。歸納：假設(shè)對(duì)于

17、k-1命題成立，也就是說(shuō)，(q0,xk-1) = qf 。由練習(xí) 2.2.2, (q0,xk) =(q0,xk-1),x) = (qf,x) 由歸納假設(shè) = qf 由(a)。 exercise 2.2.10the automaton tells whether the number of 1s 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 e

18、ven number of 1s. basis: |w| = 0. then w, the empty string surely has an even number of 1s, namely zero 1s, 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 1s, so does z. by the inductive hypo

19、thesis, (a,z) = a. the transitions of the dfa tell us (a,w) = a. if w has an odd number of 1s, 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 1s. case 2: a = 1.

20、 if w has an even number of 1s, then z has an odd number of 1s. 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 1s, then z has an even number of 1s. by the inductive hypothesis, -hat(a,z) = a, and the transitions of the dfa tell

21、 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 1s. 這個(gè)自動(dòng)機(jī)表示，狀態(tài)a表示偶數(shù)個(gè)1，狀態(tài)b表示奇數(shù)個(gè)1，不管串有偶數(shù)個(gè)還是奇數(shù)個(gè)1，都會(huì)被接受。當(dāng)且僅當(dāng)串w中有偶數(shù)個(gè)1時(shí)， (a,w) = a.。用歸納法證明如下基礎(chǔ): |w| = 0?？沾?dāng)然有偶數(shù)個(gè) 1 ，即0個(gè) 1，且 (a,w) = a. 歸納：假設(shè)對(duì)于比w 短的串命題成立。令 w = za, 其中 a 為 0 或1。 情形1： a = 0. 如果w有偶數(shù)個(gè) 1, 則z有偶數(shù)個(gè)1

22、。由歸納假設(shè)， (a,z) = a。由轉(zhuǎn)移表的dfa知(a,w) = a.如果w有奇數(shù)個(gè)1, 則z有奇數(shù)個(gè)1. 由歸納假設(shè)， (a,z) = b, 由轉(zhuǎn)移表的 dfa 知 (a,w) = b. 因此這種情況下(a,w) = a 當(dāng)且僅當(dāng) w 有偶數(shù)個(gè) 1。 情形2： a = 1. 如果w有偶數(shù)個(gè) 1, 則z有奇數(shù)個(gè)1。由歸納假設(shè)， (a,z) = b. 由轉(zhuǎn)移表的dfa知 (a,w) = a. 如果w有奇數(shù)個(gè) 1, 則z有偶數(shù)個(gè)1。由歸納假設(shè), (a,z) = a, 由轉(zhuǎn)移表的dfa知 (a,w) = b. 因此這種情況下(a,w) = a 當(dāng)且僅當(dāng) w 有偶數(shù)個(gè) 1. 綜合上述情形，命題得證

23、。solutions for section 2.3exercise 2.3.1here 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. 下表就是利用子集構(gòu)造法將nfa轉(zhuǎn)化成的dfa。其中構(gòu)造的子集有：a = p; b = p,q; c = p,r; d = p,q,r; e = p,q,s; f = p,q,r,s; g = p

24、,r,s; h = p,s. 0 1-a b ab d cc e ad f c*e f g*f f g*g e h*h e hexercise 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.

25、 we stay in state qs all the time; it represents no guess having been made. the transition table: 記狀態(tài)qi為已經(jīng)看到i并猜測(cè)i就是結(jié)尾將要重復(fù)的數(shù)字，i = 0,1,.,9 。初始狀態(tài)為qs，終止?fàn)顟B(tài)為qf。我們可以一直停留在狀態(tài)qs，表示尚未猜測(cè)。轉(zhuǎn)移表如下： 0 1 . 9-qs qs,q0 qs,q1 . qs,q9q0 qf q0 . q0q1 q1 qf . q1. . . . .q9 q9 q9 . qf*qf . solutions for section 2.4exercise

26、2.4.1(a)well 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為初始狀態(tài)。q1, q2和q3識(shí)別 abc; q4, q5和q6 識(shí)別abd, q7 到q10 識(shí)別aacd. 轉(zhuǎn)移表如下： a b c d-q0 q0,q1,q4,q7 q0 q0 q0q1 q2 q2 q3 *q3 q4 q5 q5 q6*

27、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 int

28、o one accepting state, or we can use these three state to signal the recognition of abc, abd, and aacd, respectively. 由子集構(gòu)造法可得以下dfa的狀態(tài)，其中每一個(gè)狀態(tài)都是nfa狀態(tài)的子集： 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 可以整合到一個(gè)接受狀態(tài)中，或者我們可以用這三個(gè)狀態(tài)來(lái)分別標(biāo)記已

29、識(shí)別abc, abd 和aacd。a b c d-a b a a ab c d a ac c d e ad b a f ge b a a h*f b a a a*g b a a a*h b a a asolutions for section 2.5exercise 2.5.1for part (a): the closure of p is just p; for q it is p,q, and for r it is p,q,r. (a): 根據(jù)狀態(tài)的閉包的的性質(zhì)。求得，p的閉包：p； q的閉包：p,q； r的閉包：p,q,r。 for (b), begin by noticing th

30、at a always leaves the state unchanged. thus, we can think of the effect of strings of bs and cs 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, e

31、very string of length 3 or less, consisting of bs and cs only, is accepted, with the exception of the string b. however, we have to allow as as well. when we try to insert as in these strings, yet keeping the length to 3 or less, we find that every string of as bs, and cs with at most one a is accep

32、ted. also, the strings consisting of one c and up to 2 as are accepted; other strings are rejected. b) 由于輸入a狀態(tài)總是保持不變，因此只需考慮輸入b和c的情況。可以看出，從狀態(tài)p第一次到r且只經(jīng)過(guò)b，c和轉(zhuǎn)移的路徑為bb, bc和 c ；到r之后，讀入b仍可回到r，讀入c回到p ，則可通過(guò)繼續(xù)讀入串bb, bc和 c回到r。因此，每一個(gè)由b和c組成的長(zhǎng)度小于等于3的串可以被接受，除了串b不能接受。向這些串中插入a，并保持長(zhǎng)度小于等于3，就會(huì)得到所有由a，b，c組成的，至多含有一個(gè)a的可被接受

33、的串。由一個(gè)c和兩個(gè)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: 由初始狀態(tài)，即p的閉包或者p，有3個(gè)狀態(tài)可以達(dá)到。令a = p, b = p,q, c = p,q,r。轉(zhuǎn)移表如下： a b c-a a b cb b c c*c c c csolutions for sec

34、tion 3.1exercise 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)* 首先考慮第一個(gè)a在第一個(gè)b的前面，然后再考慮相反的情況。表達(dá)式為： c*a(a+c)*b(a+b+c)* + c*b(b+c)*a(a+b+c)* exe

35、rcise 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 1s. 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 o

36、nly 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). 首先寫出沒(méi)有兩個(gè)1相鄰的串的集合，如下：(10+0)*(+1) 。表達(dá)式的第一部分表示每個(gè)1之后都緊跟一個(gè)0的這樣的串組成。為了表示結(jié)尾可能是1的情況，則可在串尾處加上 (+1)。 now, we can rethink the question as asking for strings that have a prefix with no adjacent 1

37、s followed by a suffix with no adjacent 0s. 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 facto

38、r can be obtained from the (01+1)* factor instead. 題目要求的串可由兩部分組成，也就是，前綴沒(méi)有相鄰的1，后綴沒(méi)有相鄰的0。前半部分也就是已經(jīng)給出的(10+0)*(+1)，根據(jù)對(duì)稱性后半部分可將上式的1和0交換得到。所求即為(10+0)*(+1)(01+1)*(+0)。注意中間的+1 項(xiàng)沒(méi)有作用，因?yàn)?可以由后面的(01+1)* 項(xiàng)得到。因此最后得到的正則表達(dá)式為(10+0)*(01+1)*(+0)exercise 3.1.4(a)this expression is another way to write no adjacent 1s. y

39、ou 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 0s after the final 1, and (+1) at the beginning allows an initial 1, which

40、must be either the only symbol of the string or followed by a 0. 你可以與練習(xí)3.1.2(a)中我們給出的不同樣子的表達(dá)式作比較。為什么起作用的原因是類似的。這個(gè)表達(dá)式是 “沒(méi)有相鄰的1”的另一種描述方式。(00*1)* 表示每個(gè) 1 的前面都至少有一個(gè)0做前綴。最后的0* 允許在最后一個(gè)1后面有0。開頭的(+1) 允許初始為1，要么串就只有這一個(gè)符號(hào)，要么后面跟著的就是0。 exercise 3.1.5the language of the regular expression . note that * denotes the

41、 language of strings consisting of any number of empty strings, concatenated, but that is just the set containing the empty string. 正則表達(dá)式 。*表示由任意多個(gè)空串組成的串，也是只包含空串的集合。 solutions for section 3.2exercise 3.2.1part (a): the following are all r0 expressions; we list only the subscripts. r11 = +1; r12 = 0;

42、 r13 = phi; r21 = 1; r22 = ; r23 = 0; r31 = phi; r32 = 1; r33 = +0. a) 下面就是所有 r0 的表達(dá)式；我們只寫出下標(biāo)： 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

43、 = 11*; r22 = +11*0; r23 = 0; r31 = phi; r32 = 1; r33 = +0. b) 下面就是所有 r(1) 的表達(dá)式；我們只寫出下標(biāo)：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轉(zhuǎn)移圖: if we eliminate state q2 we get: 如果消除狀態(tài)q2，有: applying the formula in the

44、 text, the expression for the ways to get from q1 to q3 is: 1 + 01 + 00(0+10)*11*00(0+10)* 由課本中的公式，q1到q3的正則表達(dá)式：1 + 01 + 00(0+10)*11*00(0+10)* exercise 3.2.4(a)利用定理3。7每個(gè)用正則表達(dá)式來(lái)定義的語(yǔ)言也可用窮自動(dòng)機(jī)來(lái)定義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中串(作

45、為)后綴/下標(biāo)的集合。exercise 3.2.8let 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 為從狀態(tài)i到狀態(tài)j，長(zhǎng)度為m，且沒(méi)有經(jīng)過(guò)編號(hào)大于k的路徑的個(gè)數(shù)。對(duì)于所有狀態(tài)i和j，以及

46、m（mn），通過(guò)對(duì)k歸納來(lái)計(jì)算這個(gè)個(gè)數(shù)。 basis: r0ij1 is the number of arcs (or more precisely, arc labels) from state i to state j. r0ii0 = 1, and all other r0ijms are 0. 基礎(chǔ): k=0，r0ij1 是由狀態(tài)i到狀態(tài)j的箭?。ǜ鼫?zhǔn)確的說(shuō)，是箭弧標(biāo)號(hào)）的個(gè)數(shù)。 r0ii0 = 1,其他的r0ijms 都為0。induction: r(k)ijm is the sum of r(k-1)ijm and the sum over all lists (p1,p2,.,p

47、r) 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的正整數(shù)序列，r大于等于2。 the answer is the sum of r(k)1jn,

48、where k is the number of states, 1 is the start state, and j is any accepting state. 答案就是r(k)1jn的總和，其中k是狀態(tài)個(gè)數(shù)，1為開始狀態(tài)，j是任意接受狀態(tài)。 solutions for section 3.4exercise 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

49、 in sets, both languages are the same: the language consisting of the strings a and b. 將r 替換為a ，s 替換為b。 等式變?yōu)閍 + b = b + a. 也就是 a,b = b,a. 因?yàn)榧现性氐捻樞蚴菬o(wú)關(guān)緊要的，所以，等式兩邊是一樣的：由串a(chǎn)和b構(gòu)成的語(yǔ)言。 exercise 3.4.1(f)replace r by a. the right side becomes a*, that is, all strings of as, including the empty string. the l

50、eft side is (a*)*, that is, all strings consisting of the concatenation of strings of as. but that is just the set of strings of as, and is therefore equal to the right side. 將r 替換為a 。右邊變?yōu)閍*, 代表a組成的所有串，包含空串。左邊是(a*)*, 代表由a組成的串構(gòu)成的串，也就是由a構(gòu)成的串。當(dāng)然相等。 exercise 3.4.2(a)not the same. replace r by a and s by

51、 b. the left side becomes all strings of as and bs (mixed), while the right side consists only of strings of as (alone) and strings of bs (alone). a string like ab is in the language of the left side but not the right. 不等。將r 替換為a ，s 替換為b。 左邊表示所有由a和b（可混合）構(gòu)成的串。而右邊表示只有a構(gòu)成的串和只有b構(gòu)成的串。像ab這樣的串就只屬于左邊的語(yǔ)言，而不屬于右邊。 exercise 3.