自动机理论、语言和计算导论课后习题答案(中文版)

1、Solutions for Section 2.2Exercise 2.2.1(a)States corresp ond to the eight comb in ati ons of switch positi ons, and also must in dicate whether the previous roll came out at D, i.e., whether the previous in put was accepted. Let 0 represent a position to the left (as in the diagram) and 1 a position

2、 to the right. Each state can be represe nted by a seque nee of three 0's or 1's, represe nti ng the directions of the three switches, in order from left to right. We follow these three bits by either a in dicat ing it is an accepti ng state or r, in dicat ing rejecti on. Of the 16 possible

3、states, it turns out that only 13 are accessible from the initial state, OOOr. Here is the tran siti on table:杠杆可能出现8种情况，影响着最终状态。并且也要说明，前面一个大理石球是 否从D滚出，也就是说，前一个输入是否被接受。令0代表向左方的状态(如图表)，1代表向右方。这三个杠杆的每一个状态都可以用三个数(0或1)组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态OOOr可达的。下面它的有穷自 动机的转移表。AB-

4、>OOOr1OOrO11r*OOOa1OOrO11r*OO1a1O1rOOOaO1Or11OrOO1a*O1Oa11OrOO1aO11r111rO1Oa1OOrO1Or111r*1OOaO1Or111r1O1rO11r1OOa*1O1aO11r1OOa11OrOOOa1O1a*11OaOOOa1O1a111rOO1a11OaExercise 2.2.2The statement to be proved ishat(q,xy)= 咅hat( -hat(q,x),y), and we proceed by in duct ion on the len gth of y.证明：通过对|y|进

5、行归纳，来证明、？(q , xy)=、？C?(q , x) , y)，具体过程如下：Basis: If y = , ihen the statement ishat(q,x) = -hat( -hat(q,x), . Teh)s statement follows from the basis in the definition ofhat. 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 b

6、e proved is p = -(hat(p, , w)ich is easy to recognize as the basis in the definition of $hat.基础：y =0，则y= £0那么需证/(q,x)= §(&(q ,x),，&记p=$(q,x),命题变为 p=、?(P , £,)由？的定义知这显然成立。In duct ion: Assume the stateme nt for stri ngs shorter tha n y, and break y = za, where a is the last symb

7、ol of y. The steps convertinghat( -hat(q,x),y) tohat(q,xy) are summarized in the following table:归纳：假设命题对于比y短的串成立，且y = za,其中a是y的结尾符号、?(？(q,x),y)到、?(q,xy)的变换总结在下表中：Expression 表达式Reason原因W(q,x),y)Start开始发(发(q,x),za)y=za by assumption由假设 y=zaS(*(q,x),z),a)Definition of hat, treating 咅hat(q,x) as a stat

8、e曾的疋义，把(q,x)看作是一个状态(q,xz),a)In ductive hypothesis归纟内假设发(q,xza)Definition ofhat貳的定义发(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.状态A, B, C分别表示以1 ,0和00结尾的串的状态。01A->ABBCA*CCAExercise 2.2.6(a)The trick is to

9、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 en tire nu mber see n - just its rema in der whe n divided by 5. That is, if we have any nu mber of the form 5a+b, where

10、 b is the rema in der, betwee n 0 and 4, then 2(5a+b) = 10a+2b. Si nee 10a is surely divisible by 5, the rema in der of 10a+2b is the same as the rema in der of 2b whe n divided by 5. Since b, is 0, 1,2, 3, or 4, we can tabulate the an swers easily. The same idea holds if we want to con sider what h

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

12、utomat on. State qi means that the in put see n so far has rema in der i whe n divided by 5.其中状态qi代表输入串被5除的余数i的状态0 1->*q0q0 q1q1q2q3q2q4q0q3q1q2q4q3q4There is a small matter, however, that this automat on accepts stri ngs with lead ing 0's. Since the problem calls for accepting only those str

13、ings that begin with 1, we need an additi onal state s, the start state, and an additi on al ''dead state'' d. If, i n state s, we see a 1 first, we act like q0; i.e., we go to state q1. However, if the first in put is 0, we should n ever accept, so we go to state d, which we n ever

14、leave. The complete automato n is:但是上述自动机仍接受以0开头的字符串。因为题目要求只接受以1开头的串， 可增加一个初始状态s和“死亡状态” d。在状态初始状态s,若看到1,则转到 状态q1;若看到0，则直接转到状态d,识别终止。所求自动机如下：0 11->sd 1q1*q0q。q1q1q2q3q2q4q0q3q1q2q4q3q4dddExercise 2.2.9Part (a) is an easy in ducti on on the len gth of w, starti ng at le ngth 1.Basis: |w| = 1. Thenh

15、at(qo,w) = -hat(qf,w), because w is a single symbol, and(-hat agrees with Son single symbols.In duct ion: Let w = za, so the in ductive hypothesis applies to z. Thenhat(qo,w)= Shat(qo,za) =-hat(qp,z),a) =-ha(qf,z),a) by the in ductive hypothesis=(-hat(qf,za) = -hat(qf,w).证明：a)通过对w长度的归纳证明。基础:若|w| = 1

16、,则w是一个符号，此时需证?(qo,w) = ?(qf,w),而对于单个符号扩展转移函数?与转移函数 曲勺作用是一样的，得证。归纳:令w = za,假设对于z命题?(qo,z) = ?(qf,z)成立。那么?(qo,w) = ?(qo,za)=S(q0,z),a) =?S(qf,z),a)由归纳假设=? (qf,za) = ? (qf,w).For part (b), we know that Shat(q0,x) = qf. Since x & , we know by part (a) that Shat(qf,x) = qf. It is the n a simple in du

17、ct ion on k to show that -hat(q0,x ) = qf. SBasis: For k=1 the stateme nt is give n.In duct ion: Assume the stateme nt for k1; i.e., -hat(qo,xSUP>k-1) = qf. Usingkk-1Exercise 2.2.2, -hat(q0,x ) = -lhat( -hat(qo,x ),x) = -hat(qf,x) by the inductive hypothesis = cf by (a).b) x是属于L(A)的非空串，也即串x被接收，因此

18、、？(qo,x) = qf，则由a)知、?(qf,x) =、?(qo,x)= qf。现在通过对k的归纳来证明、?(qo,xk) = qf。基础：k=1时，需证?(qo,x) = qf，由已知可得。归纳：假设对于k-1命题成立，也就是说，、？(qo,xk-1) = qf 。由练习2.2.2, ?(qo,xk)=?( ?(qo,xk-1),x) =?(qf,x)由归纳假设=qf 由(a)。Exercise 2.2.10The automat on tells whether the nu mber of 1's see n is eve n (state A) or odd (state

19、B), accept ing in the latter case. It is an easy in duct ion on |w| to show that dh(A,w) = A if and only if w has an eve n nu mber of 1's.Basis: |w| = 0. Then w, the empty stri ng surely has an eve n nu mber of 1's, n amely zero 1's, and ? (A,w) = A.In duct ion: Assume the stateme nt for

20、 stri ngs shorter tha n w. Then w = za, where a is either 0 or 1.Case 1: a = 0. If w has an eve n nu mber of 1's, so does z. By the in ductive hypothesis,? (A,z) = A. The transitions of the DFA tell us ? (A,w) = A. If w has an odd nu mber of 1's, the n so does z. By the in ductive hypothesis

21、,-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 eve n nu mber of 1's.Case 2: a = 1. If w has an eve n nu mber of 1's, the n z has an odd nu mber of 1's. By the inductive hypothesis, -hat(A逆)=B. The transiti

22、ons of the DFA tell us -hat(A,w) = S A. If w has an odd nu mber of 1's, the n z has an eve n nu mber of 1's. By the in ductive hypothesis, -hat(A,z) = A, and the transitions of the DFA tell us -hat(A,w) = B. S Thus, in this case as well, -hat(A,w) = A if and only if w has an even number of 1

23、'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.因此这种情况

24、下、？(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.3Exercise 2.3.1Here are the sets of NFA states represe nted by each of the DFA states A th

25、rough 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.01->ABABDCCeADFC*EFG*FFG*GEH*HEHExercise 2.3.4(a)The idea is to use a state qi, for i = 0,1,.,9 to re

26、prese nt the idea that we have see n an in put 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 hav ing bee n made. The tran siti on table:记状态qi为已经看到i并猜测i就是结尾将要重复的数字，i

27、 = 0,1,.,9。初始状 态为qs,终止状态为qf。我们可以一直停留在状态 qs,表示尚未猜测。转移表 如下：01.9->qsqs,qOqs,q1qs,q9L q0qfq0.q0q1q1 |qfq1|. |q9q9q9qf*qf.Solutio ns for Secti on 2.4Exercise 2.4.1(a)We'll use q0 as the start state. q1, q2, and q3 will recognize abc; q4, q5, and q6 will recog nize abd, and q7 through q10 will reco

28、g nize aacd. The tran siti on table is:记q0为初始状态。q1, q2和q3识别abc; q4, q5和q6识别abd, q7到q10识 别aacd.转移表如下：abcd->q0q0,q1,q4,q7q0q0q0q1q2q2q3*q3q4|q5q5q6*q6q7q8q8q9q9 |q10 1*q10口Exercise 2.4.2(a)The subset con struct ion gives us the follow ing states, each represe nting the subset of the NFA states indi

29、cated: A = qO; 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 comb ined into one accepti ng state, or we can use these three state to sig nal the recog niti on of abc, abd, and aacd, respectively.由子集构造法可得以下DFA的状态，其中每一个状态都是N

30、FA状态的子集：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和aacdabcd->ABAAABCDAACCDEADBAFGEBAAH*FBAAA*GBAAA*HBAAASolutions for Section 2.5Exercise 2.5.1For part (a): the closure of p is just p; fo

31、r 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), begi n by no tici ng that a always leaves the state un cha nged. 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 fro

32、m 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

33、's as well. When we try to insert a's in these strings, yet志文工作室8keeping 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 stri ngs con sisti ng of one c and up to 2 a's are accepted; other stri ngs are rejected.b

34、)由于输入a状态总是保持不变，因此只需考虑输入 b和c的情况。可以看出， 从状态p第一次到r且只经过b，c和&转移的路径为bb, b &和c ;到r之后， 读入b仍可回到r，读入c回到p，则可通过继续读入串bb, bc和c回到r。£ closure因此，每一个由b和c组成的长度小于等于3的串可以被接受，除了串b不能接 受。向这些串中插入a，并保持长度小于等于3，就会得到所有由a，b，c组成 的，至多含有一个a的可被接受的串。由一个c和两个a组成的任意串也是可以 被接受的。其它的串均被拒绝。There are three DFAstates accessible fro

35、m the in itial state, which is theor p. Let A = p, B = p,q, and C = p,q,r. Then the tran siti on table is:由初始状态，即p的&闭包或者p，有3个状态可以达到。令A = p, B = p,q, C = p,q,r。转移表如下：abc->AABCBBCC*CCCCSolutio ns for Section 3.1Exercise 3.1.1(a)The simplest approach is to consider those strings in which the fir

36、st 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 st

37、rings that have no two adjace nt 1's. Here is one such expressio(10+0)*( &1)To see why this expressi on works, the first part con sists of all stri ngs 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 b

38、y 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 adjace nt 1's followed by a suffix with no adjace nt 0's. The former is the

39、expressi on we developed, and the latter is the same expression, with 0 and 1 interchanged. Thus, a solution to this problem is (10+0)*( s+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 in stead.

40、题目要求的串可由两部分组成，也就是，前缀没有相邻的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 expressi on is ano ther way to write、'no adjace nt 1's.'' You

41、 should compare it with the different-looking expression we developed in the solution to Exercise 3.1.2(a).The argume nt 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 thebeg inning allows aninitial 1, which

42、 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.5The Ianguage of the regular expression£ . Note that 

43、3; * denotes the Ianguage of stringcon sist ing of any nu mber of empty stri ngs, con cate nated, but that is just the set containing the empty stri ng.正则表达式 & £表示由任意多个空串组成的串，也是只包含空串的集合。Solutions for Section 3.2Exercise 3.2.1Part (a): The following are all R0 expressions; we list only the s

44、ubscripts. R11 =1;£ +R12 = 0; R13 = phi; R21 = 1; R22 =& ; R23;=R31 = phi; R32 = 1; R33 =0. +a) 下面就是所有R0的表达式；我们只写出下标：R11 = d; R12 = 0; R13 =：(phi); R21 = 1; R22 =£ ; R23;=R31 =心(phi); R32 = 1; R33 = Q. +Part (b): Here all expressi on n ames are R; we aga in list only the subscripts. R1

45、1 = 1*; R12 = 1*0; R13 = phi; R21 = 11*; R22 =11*0; R23 = 0; R31 = phi; R32 = 1;R33 =妙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 elim in ate state q2 we get:如果消除状态q2,有:Applyi

46、ng 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 LExercise 3.2.6(b)The set of suffixes of strin

47、gs in L. (以儿 中串(作为)后缀/下标的集合。Exercise 3.2.8Let R(k) ijm be the nu mber of paths from state i to state j of len gth m that go through no state nu mbered higher tha n k. We can compute these nu mbers, for all states i and j, and for m no greater tha n n, by in ducti on on k.令R(k)ijm为从状态i到状态j,长度为m,且没有经过

48、编号大于k的路径的个数。 对于所有状态I和j，以及m (mWn),通过对k归纳来计算这个个数。Basis: R°ij1 is the nu mber of arcs (or more precisely, arc labels) from state i to state j. R°iio = 1, and all other Rijm's are 0.基础：k=0, R0ij1是由状态i到状态j的箭弧(更准确的说，是箭弧标号)的个数。 R°ii0 = 1,其他的 R°ijm's 都为 0。In duct ion: R叫m is the

49、sum of Rk-1)jm and the sum over all lists (p1,p2,.,pr) of positive integers that sum to m, of Rk-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)是所有和为

50、m的正整数序列，r大于等于2。The an swer is the sum of Rk)1jn, where k is the nu mber of states, 1 is the start state, and j is any accepti ng state.答案就是R(k)1jn的总和，其中k是状态个数，1为开始状态，j是任意接受状态。Solutio ns 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

51、 a. That is, a,b = b,a. Since order is irreleva nt in sets, both Ian guages are the same: the Ianguage 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 stri

52、 ngs of a's, in clud ing the empty string. The left side is (a*)*, that is, all strings consisting of the con cate nati on of stri ngs of a's. But that is just the set of stri ngs of a's, and is therefore equal to the right side.将R替换为a。右边变为a*,代表a组成的所有串，包含空串。左边是（a*）*, 代表由a组成的串构成的串，也就是由a构成

53、的串。当然相等。Exercise 3.4.2(a)Not the same. Replace R by a and S by b. The left side becomes all stri ngs 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 Ianguage of the left side but not the right

54、.不等。将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 stri ngs composed of zero or more occurre nces of stri ngs of the form a.ab, that is, one or more a's en ded by one

55、b. However, every stri ng in the Ian guage of the left side has to end in ab. Thus, for instanee, & is in the Ianguage on the right, but not on the left.不等。举反例，将R替换为a ,S替换为b。右边表示由0个或多个形如a.ab 组成的串，也就是，一个或多个 a后面紧跟一个结尾的b。但是，左边的串必须 以ab结尾。因此，&属于右边的语言，但不属于左边。Solutio ns for Secti on 4.1Exercise 4.1

56、.1(c)Let n be the pump in g-lemma con sta nt (note this n is un related to the n that is a local variable in the definition of the Ianguage L). Pick w = 0n10n. Then when we write w = xy z, we know that |xy| <= n, and therefore y con sists 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 n 0'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,后面跟着一