COPYRIGHT 1999 by Brooks/Cole Publishing Company division of intemational Thomson Publishing Inc. ‘The ITP logo is a registered trademark used herein under license. For more information, contact: BROOKS/COLE PUBLISHING COMPANY 511 Forest Lodge Road Pacific Grove, CA 93950 USA Intemational Thomson Publishing Europe Berkshire House 168-173 High Holbom London WC1V 7AA England ‘Thomas Nelson Australia 102 Dodds Street South Melboume, 3205 Victoria, Australia Nelson Canada 1120 Birchmount Road ‘Scarborough, Ontario Canada Mik 564 Intemational Thomson Editores Seneca 53 Col, Polanco 11560 México, D. F., México Intemational Thomson Publishing GmbH Konigswinterer Strasse 418 53227 Bonn Germany Intemational Thomson Publishing Asia 60 Albert Street #15-01 Albert Complex ‘Singapore 189969 Intemational Thomson Publishing Japan Palaceside Building, SF 1-1-1 Hitotsubashi Chiyoda-ku, Tokyo 100-0003 Japan All rights reserved. Instructors of classes using Introduction to the Theory of Computation by Sipser as a textbook may reproduce material from this publication for classroom use. Otherwise, the text of this publication may not be reproduced, stored in’a retrieval system, or transcribed, in any form or by any means—electronic, mechanical, photocopying, recording, or otherwise—without the prior written permission of the publisher, Brooks/Cole Publishing Company, Pacific Grove, Califomia 83950. Printed in the United States of America. ISBN 0-534-37462-XChapter 0 solutions Chapter 1 solutions Chapter 2 solutions Chapter 3 solutions Chapter 4 solutions Chapter 5 solutions Chapter 6 solutions Chapter 7 solutions Table of ContentsPreface This instructor’s manual is designed to accompany the textbook, Introduction to the Theory of Computation, by Michael Sipser, PWS Publishers, 1997. It con- tains solutions to almost all of the exercises and problems appearing in Chapters 1-5 and 7 along with a handful of solutions to problems in other chapters. Most of the omitted solutions in the early chapters require figures, and producing these required more work that we were able to put into this manual at this point. The next edition will be more complete. ‘This manual is available only to instructors and only in hardcopy form. Requests for copies should be directed to: 606-282-4629, fax 606-647-5020. ‘Thanks to Jonathan Feldman for sending in corrections to a draft of this menual. An errata site for this instructor's manual maintained at http: //wew-math.mit.edu/"sipser/itocsm-errs1.1.btm] . ‘The email address for correspondence regarding the textbook and the instructor's manual is sipserbook@math .mit.edu .Instructor’s Manual 1 Chapter 0 0.12 Here is a sketch of the solution. Make two piles, A and B, of nodes; initially empty. Then, starting with the entire graph, add each remaining node to A if its degree is greater than 1/2 of all remaining nodes and to B otherwise, then discard all nodes to which it isn’t (is) connected if it was added to A (B). Continue until nothing is left. Chapter 1 1 19 a b. ce a e f. & a. The start state of M; is 1. ‘The set of accept states of M; is {a2}. The start state of Mz is qi. ‘The set of accept states of Mz is {1,44}. On input aabb M; goes through the state sequence g1, 42,93; %1) 41 M, does not accept aabb. Mz does accept e. My = ({a1, 92,93}, {a,b}, 61,915 {a2})- ‘The transition function 1 is =r ala a @ |g 9 ela a Ma = ({41, 92193, 9a}s {2,0}, 52s a1, {an,94})- The transition function 62 is ab ala ao 2) % BR H alas m4 Let N = (Q,3,6,90,F) be any NFA. We build an NFA N! with only a single accept state that accepts the same language as N. Informally, N' looks exactly like N except it has e-transitions from states correspond- ing to accept states of N to a new special accept state, qaccept- Finally, the state daccepthas no transitions coming out of it. More formally, N! = (QU {deccept}; ©, 5's Go, {daccept}). Where for any q € Q and a € 7 =f a2) fax gP 800)= { HO 3 facet) itaceandgeF and 6’ (daccepts@) = 0 fora € Ex.Theory of Computation 1.10 113 115 a. Let M' be the DFA M with the accept and non-accept states swapped. We will show that M’ recognizes the complement of B, where B is the language recognized by M. Suppose M' accepts x. If we run M’ on z we end in an accept state of M’. Because M and M' have swapped accept/non-accept states, if we run M on z, we would end in a non-accept state. Therefore, z @ B. Similarly, if z is not accepted by M’, then it would be accepted by M. So M’ accepts exactly those strings not accepted by M. Therefore, M’ recognizes the complement of B. Since B could be any arbitrary regular language and our construction shows how to build an automaton to recognize its complement, it follows that the complement of any regular language is also regular. ‘Therefore, the class of regular languages is closed under complement. . Consider the NFA in exercise 1.12(a). The string a is accepted by this au- tomaton. If we swap the accept and reject states, the string a is still accepted. This shows that swapping the accept and non-accept states of an NFA doesn’t necessarily yield a new NFA recognizing the complement of the original one. The class of languages recognized by NFAs is, however, closed under comple- ment. This follows from the fact that the class of languages recognized by NNFAs is precisely the class of languages recognized by DFAs which we know is closed under complement from part (a). Let B = {0,1}. a. 1D°0 b. D"1E*1 ELE" c. E70101E" d. DE0r* e. (0U1E)(E2)* £ (0U(10)*)"1* g. (€UE)(eUE)(eUS)(eUD\(e UE) h. D*Od*U 111d" U1Ve 4. (1B)"(1Ue) J. 0*(100 U010 U001)0" k. eU0 1. (1"01701" m0 na. IE" Uors0*10" a, ab,e;ba,aba b. ab,ababje, sabbb , aba,babje,abababInstructor’s Manual 3 1.16 Lat 1.18 g- dyabje,bb h, ba,bbajb,€ In both parts we first add a new start state and a new accept state. Several solutions are possible, depending on the order states are removed. ‘a. Here we rerhove state 1 then state 2 and we obtain atb(aUba*b)* Here we remove states 1, 2, then 3 and we obtain €U ((aUd)arb((bU a(aUb))a"b)*(eUa)) a. Ay = {0"1"2"| n > 0}. Assume that A; is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string 0°172?. Because ¢ is a member of A; and s has length more than p, the pumping Jemma guarantees that s can be split into three pieces, s = 2yz, where for any i> 0 the string zy‘z is in A). 4) The string y consists only of Os, only of 1s or only of 2s. In these cases the string zyyz will not have equal number of Os, 1s and 2s, leading to a contradiction. ii) The string y consists of more than one kind of symbol. In this case zyy2 will have the 0s, 1s or 2s out of order. Hence it is not a member of Ai, which is a contradiction. ‘Therefore, A; is not regular. b. Ap = {wu| w € {a,b}*}. Assume that A, is regular. Let p be the pumping length given by the pumping lemma, Choose s to be the string a?ba?b. The pumping lemma guarantees that s can be split into three pieces, s = zy2, where for any i > 0 the string ay‘z is in Az. i) The string y consists of a’s only. In both cases that y is left or right of the middle b, zyyz would not be in the form of ww. fi) The string y is ab. The condition |zy| < p would be violated. iii) The string y contains the center b and y # eb. Therefore, zyyz would not be in the form of ww. Since all cases cause contradictions, Aa is not regular. c. As = {a?"| n > 0}. Assume that As is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string a”. The pumping Jemma guarantees that s can be split into three pieces, s = xyz, where for any i > 0 the string 2y'z is in A. ‘The shortest string in Ag which is longer than a”” is at = 2?” Thus the length of s’ is double the length of s. The only way that zyyz could be in ‘As is by letting y be a2”. However, that would violate the pumping lemma condition that |zy| < p. Therefore, Ag is not regular. ‘The error is that s = 0°? can be pumped. Let s = ayz, where z= 0, y =0 247, The conditions are satisfied because119 b ce a e £ Be 1.20 121 a ‘Theory of Computation = 000-4? is in o*1*, 5) for any ¢ > 0, ay ii) |y|=1>0, and ley =2 0} is regular. Let p be the pumping length given by the pumping lemma. The string s = 0P10? € L, and |s| > p- ‘Thus the pumping lemma implies that s can be divided as 2yz with = 0°,y = 08, z = 0°10", where b > 1 and a+b+c =p. However, the string a 10? ¢ L, since a+¢ < p. That contradicts the pumping If L, the complement of C = {0"1”| n > 0} is regular, then C itself is regular, using the result of Exercise 1.10a, However, we have shown in Example 1.38 that C is non-regular. So L cannot be regular. ‘Assume L = {0"1"| m # n} is regular. Let p be the pumping length given by the pumping lemma, Set m =p and n= p+pl. The string s = 0717"?! € L, and |s| > p. Thus the pumping lemma implies that s can be divided as yz with z = 0°,y =0°,z = 0°1?*?!, where b > Land a+b+c =p. However, the string #! = xy¥t1z = oeteitbteyptel = optelyrty! gL, That contradicts ‘the pumping lemma. Alternative solution: The nonregular language {0"1"| n > 0} = ON0°1". Hence C cannot be regular because the regular languages are closed under intersection. Assume C = {ul w € {0,1}* is a palindrome} is regular. Let p be the pumping length given by the pumping lemma, ‘The string s = 0°10? € C and |s| > p. Follow the argument as in part (a). Hence C isn’t regular, so neither is its complement, For any regular language A, let M; be the DFA recognizing it. We need to find a DFA that recognizes A®, Since any NFA can be converted to an equivalent DFA, it suffices to find an NFA Mz that recognizes A®. We keep all the states in M; and reverse the direction of all the arrows in My. We set the accept state of Mz to be the start state in Mi. Also, we introduce a new state go as the start state for Mz which goes to every accept state in My by an e-transition. For every string s accepted by M, the path that s follows in My starts at the start state and stops at one of the accept states, say, dead. If we input 3® to Ma, it starts at qo and forks into different paths starting at each of the accept states in M,. The computation can reach the accept state in Mz by following the same path as its reversed counterpart in M, but in the opposite direction. Similarly, for every string w accepted by Ma, there exists a path P starting ‘at qo going through qeng as its next step and stopping at the unique acceptat 138 oft es state, Camverting tha NFA My back tp iia counterpart My and reversing the fuptt tring, wo can yet from the start atzte 10 Gea bo A, by following the rama path in the opponite direction. ‘noo nignifioant bit unt! « differmns Is foie. Wa implement this Idee with 2 DFA baring mtates go, gu, amd o;, State op tnticated thm remult Sa not yet determinad. tates ¢1 Moki 2 Indicate the ing row ia known to ba larger, ar smaller, respectively. We start with gy. If the top hit In the tapct string iy bbiggec, 1b gem to gi, the ool accept iain, and stays thera til the acl of the Inget atcing. Hf the top bit ta the input sizing ts smaller, Ht goad to oy and stapa there 10 the end af the Input wiving. Qtherwine, it etays in state a, Asrume Ienguage 5 ia regahar. Use the ramping emma to 1 get a length p ‘the conditlons of ths pumping Jemma. Set « tran Obvicemly, o € £ td [xf > p. Thus, the pomping lomras inoptien that the For ach n 2 1, we build » OFA with the w states g++ yfa-a to count ‘the umber of cozmecutive a's modulo n read ao far. For cach cmmcter a ‘thet bs input, the counter fnotimenia by 1 aad jumpe to the next state in 3. ‘B accepés the string if end only if the machine stops ot ga. ‘That menns tha laagth of the string romeiate of all o’s ond ita length 'y 3 mokiple of 9, Moce dermally, the wet of tates of Mls GQ {ousci..-- deaf. The wtate oy jm the mart state nnd the ooly aovept atate. Define the trenatiion faction on: Sfgiyn) = oy where j md +1 mod n. By wimmlatlog binary division, we create 4 DFA with n state that serag- noises Ca. Af hes o ptaten which keep track of tho 1 posible rematudern of ‘thy diviglan proses, The start state Is the only scoept stata and correspamis: to remainder 0. ‘The input wizing in fod into Af starting trom the moet signiicamt bit. For each input bit, Af doubles the ramainder that ite curmnt phate ricocis, od,Instructor's Manual 7 1.82 1.83 1.34 1.38 Ifan input string ends at the accept state (corresponding to remainder 0), the binary number has no remainder on division by m and is therefore a member of Cn. ‘The formal definition of M is ({qo.---1dn—1}:{0,1}, 6,40, {a0})- For each 4G €Q and bE {0,1}, define 5(q;,b) = gj where j = (21 +6) mod n. Let M = (Q,5, 5,90) F) be an NFA recognizing A, where A is some regular language. We construct M’ = (Q',E: 5,9), F”) recognizing NOPREFIX(A) as follows: i) Q=Q . _ fia) REF w) Parr! adac dee #,0)= {4 _ iii) a = 90 iv) F=P Let M = (Q,2,6,q0, F) be an NFA recognizing A, where A is some regular language. We construct M’ = (Q’,2,6,q5, F’) recognizing NOEXTEND(A) as follows: i) =Q ii) #=6 iii) a = 90 iv) F’ = {q| there is no path from q to an accept state}. Assume to the contrary that some FST T outputs w™ on input w. Consider the input strings 00 and 01. On input 00, 7 must output 00, and on input 01, T must output 10. That is impossible, because in both cases the first input bit is a 0, but in one case the first output bit is a 0 and in the other case the first output is a 1, and the first output bit depends only on the first input bit. Hence no such FST can exist. ‘To show that = is an equivalence relation we show it is reflexive, symmetric, and transitive. It is reflexive because no string can distinguish z from itself and hence =z z for every . It is symmetric because 2 is distinguishable from y whenever y is distinguishable from z. It is transitive because ifw =r and z=; y, then for each z, wz € Lif zz € L and xz € Liff yz € L, hence wz € Liff yz € L, and so w =z y. ‘We prove this assertion by contradiction. Let M be a k-state DFA that recognizes L. Suppose for a contradiction that L has index greater than k. ‘That means some set X with more than k elements is pairwise distinguishable by L. Because M has k states, the pigeonhole principle implies that X contains two distinct strings z and y where 6(9o,2) = 4(qo,y)- Here 6(g0,2) is the state that M is in after starting in the start state qo and reading1.86 1.37 Theory of Computation input string z. Then, for any string z € D*, (go, zz) = 6(qo,yz). Therefore either both zz and yz are in Z or neither are in L. But then z and y aren’t distinguishable by L, contradicting our assumption that X is pairwise distinguishable by L. . Let X = {01,... , 94} be pairwise distinguishable by L. We construct DFA M = (Q,5,6,q,F) with k states recognizing L. Let Q = {41,... ,ga}, and define 5(gi,) to be qj where 8; =r, sa (the relation =, is defined in problem 1.34), Note that »; =z a for some 8; € X otherwise XUs,a would have k+1 elements and would be pairwise distinguishable by L and that contradicts our assumption that L has index k. Let F = {q| 8; € L}. Let the start state, qo, be the g; such that 5; =1 €. M is constructed so that, for any state 4, {3| 6(40, 8) = a} = {| 8 =z 9}. Hence M recognizes L. Suppose L is regular and let k be the number of states in a DFA recognizing E. Then from part (a) L has index at most k. Conversely, if L has index k, then by part (b) it is recognized by a DFA with k states, and thus is regular. To show that the index of L is the size of the smallest DFA accepting it, suppose that L's index is ezactly k. Then, by part (b), there is a k-state DFA accepting L. That is the smallest such DFA since if it were any smaller, then we could show by part (a) that the index of J is less than k. Assume to the contrary that ADD is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string 1?=0?+1?, which is a member of ADD. Because » has length greater than p, the pumping Jemma guarantees that s can be split into three pieces, s = zyz, satisfying the conditions of the lemma. By the third condition in the pumping lemma have that |zy| 1. Then zy*z is the string 17+*=0?+1?, which is not a member of ADD, violating the pumping lemma. Hence ADD isn’t regular. Note: The version of the problem that appears in the first printing is in- correct. The correct version (which appears in the second and subsequent printings) is: Show that the language F = {a‘bic*] i,j,k > 0 and ifi = 1 then j = k} satisfies the three conditions of the pumping lemma even though it is not regular. Explain why this fact does not contradict the pumping lemma. Language F satisfies the conditions of the pumping lemma using pumping length 2. If s € F is of length 2 or more we show that it can be pumped by considering four cases, depending on the number of e’s that # contains. 4) If s is of the form b*c*, let z =e, y be the first symbol of s, and let z be the rest of ». ii) If s is of the form ab*c*, let z =e, y be the first symbol of s, and let z be the rest of s. iii) If 6 is of the form aab*c*, let x =e, y be the first two symbols of s, and let z be the rest of #.Instructor’s Manual 9 1.38 1.89 e e iv) If s is of the form aaab'c", let 2 z be the rest of s. ¢, y be the first symbol of s, and let In each case, the strings zy'z are members of F for every i > 0. Hence F satisfies the conditions of the pumping lemma. However, F is clearly not regular, because the nonregular language {ab"c”| n > O} is the same as Friabre*, and the regular languages are closed under intersection. The pumping lemma is not violated because it states only that regular languages satisfy the three conditions, and it doesn’t state that nonregular languages fail to satisfy the three conditions. ‘The objective of this problem is for the student to pay close attention to the exact formulation of the pumping lemma. ‘The minimum pumping length is 4. The string s = 000 € 0001* cannot be pumped, and any string in 0001* of length 4 or more contains a 1 and hence can be pumped by dividing it so that 2 = 0, y = 1, and 2 is the rest, ‘The minimum pumping length is 1. ‘The string ¢ cannot be pumped because of condition 2 in the pumping lemma and hence 0 is not a pumping length. ‘Any string in 0°2” of length 1 or more contains a 0 or a 1 and hence can be pumped by dividing it so that 2 = €, y= 0 or 1, and z is the rest, so 1 is a pumping length. ‘The minimum pumping length is 1. The pumping length cannot be 0, as in part (b). Any string in (01)* of length 1 or more contains 01 and hence can be pumped by dividing it so that 2 = ¢, y = 01, and z is the rest. ‘The minimum pumping length is 3, The string 01 cannot be pumped, 50 2 is not a pumping length. All strings in the language of length 3 or more can be pumped, (note that there aren’t any such string, so the statement is true vacuously) so 3 is a pumping length. ‘The minimum pumping length is 1. String ¢ cannot be pumped because of condition 2 in the pumping lemma and hence 0 is not a pumping length. The language has no strings of length 1 or more so 1 is a pumping length. (the conditions hold vacuously). Let Ay = B*0*-10". A DFA with k states can recognize A, In addition to the start state, it has one state for each number of Os it has read since the last 1. After k— 1 0s the machine enters a accept state whose transitions are self-loops. In any DFA with fewer than k states, two of the k strings 1, 10, ... , 108"? must cause the machine to enter the same state, by the pigeon hole principle. But then, if we add to both of these strings enough 0s to cause the longer of these two strings to have exactly k — 1 Os, the two new strings will still cause the machine to enter the same state, but one of these strings is in Ay and the other is not. Hence, the machine must fail to produce the correct accept/reject response on one of these strings.w Theary of Compatation 140 1a = {2" | 2 0}. ‘the wet Ba(A) couminta of all sizings of tha form 10 which fa obrvimusly regular. We show by combradicHon that 3 m 2y(A) lan’ wegular. Suppom that Ht a, Then thece axieta 5 pumping Jeogth » suck that ‘Sor aay etting » © F with |s| > p, we can brenk ¢ vp into sizing: =, 9, ond medlatying tha comditiooa of abe lmmme. Compldec the atcing a € Hf that a base 8 repremntation af 2 whers wa chooso } lazge enough ta forve # ta Inve Length at Veaut p, Than am zyx mtlefying the conditions of the Jemona. Ih particaler, sre Bye By aul zs € 8. Now, defias tha length of 2 E* 3) es = 03" + (Call thls quantity ge} H) ops me cd" + yo +3. (Call thie quantiiy 91) SH) ayy me cite + yon +S" +x. (Call this quantity g:) We sow derive x exntraifiction algibrnically. Using equations (1), (i), and ye bere Ne nn ott yes = a ee * We know from the puiopring Immmy that 93, 052, =7yx € A wn it dbllows thas go = 24 and g: = 2%, Sor acme Jo, ty 2 0, Becacse sm zye and 3 i the ‘bam 3 represontation of #, wn hare q, = 2. Moceavar, by Construct NFA N = (Q/,5,4',qp,F’) recognizing the first halves of the strings in A as follows: i) W=QxQ. ii) For q,r € Q define &'((g,r),a) = {(u,v)| u € 5(q,a) and r € 4(v,b) for some b € E}. G0! = (Gos Gaccept)+ iv) F’ = {(q,9) 9 Q}- Let A= {o°#1*}. Thus, Ay_y 1 {0°1"} = {0"1"| n> 0}. Regular sets are closed under intersection, and {0"1"| n > 0} is not regular, so Ay_ is not regular. Let E, = {z € {0,1}*| the (n — 1)st symbol from the right in a is 1} for n> 2. Constructing an n-state NFA for En is easy. Let M be a DFA recognizing E,. We claim that M has at least 2"~? states. Let S be the set of all strings of length n — 1. For each y in $ let q, be the state that M is in after starting at the start state and the reading y. If y #2, then gy # qe, otherwise M fails to recognize the E,, for the following reason. Say that y and z differ on the ith bit. Then one of the strings yO"? and 20-1 js in E, and the other one isn’t. But M has the same behavior on both, so M fails to recognize E,.. Hence, M has at least as many states a S has strings, and 50 M has at least 2"-1 states. 2 Here are the derivations (but not the parse trees). » E> TP a . E> BAT => THT > F*T > F+F > atF = ata E = Es? = EsTsT > T+T+T > F+T+T > F+F+T > F+P+F > atP+F => atatF = atata |. D> T > F > (E) > (T) > (F) > ((B)) > ((T)) > (FY) > (a) First, we show that both A and B are context-free. It's not hard to see that the following grammar recognizes A: S— RT Rake Tvlele12 2.8 Theory of Computation The following grammar recognizes B: S>TR T+ alble R+cRle So, both A and B are context-free languages. Now, observe that ANB = {a"b"c"| n > 0}. We know from Example 2.20 that this language is not, context-free. We have found two context free languages whose intersection is not context-free. Therefore context-free languages are not closed under intersection. bb, First, the context-free languages are closed under the union operation. Let Gy = (Vi,B, Ri, 51) and Gz = (Va, 2, Ra, S2) be two arbitrary context free grammars. We construct a grammar G that recognizes their union, Formally, G = (V,3,R, S) where: )V=SYUN ii) R= R,UR,U{S + Sy, $+ $2} (Here we assume that R, and Ry are disjoint, otherwise we change the variable names to ensure disjointness) Next, we show that the CFGs are not closed under complementation. Assume, for a contradiction, that the CFGs are closed under complementation. Then, if G; and G are context free grammars, it would follow that L(Gi) and 1{G,) are context free. We previously showed that context-free languages are closed under union and so £(Gi) U Z(G) is context free. That, by our assumption, implies that (G1) UL(Gj) is context free. But by DeMorgan’s laws, L(Gi) UL(Gi) = £(Gs) N L(G). However, if G1 and Gz are chosen as in part (a), L(G1) UL(Gi) isn’t context free. This contradiction shows that, the context-free languages are not closed under complementation. a, The variables of G are: R,X,$,7. The terminals of G are: a,b. The start variable is R. b. Three strings in G are: ab,ba, and aab. ¢. Three strings not in G are: a,b, and e. . False. e. True. f. False. 1. False. m. L(G) consists of all strings over a and b that are not palindromes.Instructor’s Manual 13 24 2.5 e f S— RiRiRiR R-+OR|1R|€ . $+ 0RO| 1Rt |e R-+OR|1R|€ $+0|1| 005 | 018 | 108 | 118 $-+0| 0$0| 0S1| 180] 151 S+ BiB B- BB}OB1|1B0|1 |e This CFG works because B generates all strings that have at least as many 4s as Os, and so S forces an extra 1. $4080 | 181/o|1/€ S38 This set is regular, so the PDA doesn’t even need to use its stack. The PDA scans the string and uses its finite control to maintain a counter which counts up to 3. It keeps track of the number of 1's it has seen using this counter. ‘The PDA accepts the moment it sees three ones. This set is also regular. The PDA scans the string and keep track of the first and last symbol in its finite control. If they are the same, it accepts, otherwise it rejects. Again, this set is regular. The PDA scans the string and keep track of the length (modulo 2) using its finite control. If the length is 1 (modulo 2) it accepts, otherwise it rejects. ‘The PDA scans across the string and push the symbols onto the stack. At some point it nondeterministically guesses where the middle is. It looks at the middle symbol. If that symbol is a 1, it rejects. Otherwise, it scans the rest of the string, and for each character scanned, it pops one element off of its stack. If the stack is empty before it reaches the end of the input, it rejects. If the stack is empty when it finishes reading the input (ie. it correctly guessed the middle) then it accepts. ‘The PDA scans across the input. If it sees a 1 and its top stack symbol is a 0, it pops the stack. Similarly, if it scans a 0 and its top stack symbol is a 1, it pops the stack. In all other cases, it pushes the input symbol onto the stack. After it scans the input, if there is a 1 on top of the stack, it accepts. Otherwise it rejects. ‘The PDA begins by scanning across the string and pushing each symbol onto its stack. At some point it nondeterministically guesses when it has reached the middle. It also nondeterministically guesses if string has odd length or ‘even length. Ifit guessed even, then it pushes the current symbol it’s reading ‘onto the stack (recall that the PDA has guessed that this symbol is the middle symbol). If it guesses that string has odd length, it goes to the next input symbol without changing the stack. Now, it scans the rest of the string, and it compares each symbol it scans to the symbol on the top of the stack. If they are the same, it pops the stack, and continues scanning. If they are different, it rejects. If the stack is empty before it finishes reading all the14 2.6 2.7 ce Theory of Computation input, it rejects. If the stack becomes empty just after it reaches the end of the input then it accepts. In all other cases, it rejects. ‘The PDA simply rejects immediately. $+ SaSaSbS | SaSbSas | SbSaSa5 |e $+ XbXaB|T|U T-+aTo|To|b U-+aUb| aja Xalb S3TX T+ 0To | 171 | #X X 0X |1X fe S—+UPV P-aPa|vPo|Tle T+ #MT | # U> Mau |e VoaMV |e M-+aM|bM |e ‘Note that we need to allow for the case when i = j, that is, some 2; isa palindrome. Also, ¢ is in the language since it’s a palindrome. ‘The PDA uses its stack to keep a count of the number of a’s minus twice the number of b’s. It enters an accepting state whenever this count is 0. In more detail, it operates as follows. It reads the next input symbol. If it is an a and the top of the stack is a b, it pops the b. If it is an a and the top of is either an a or empty, it pushes the a. If the next input symbol is a b, then repeat the following sentence twice. If the top if the stack is an a, pop the stack, otherwise push the b. ‘The PDA scans actoss the string. It pushes the a's it reads onto the stack ‘until it encounters a b. Then, for each b it reads, it pops one a off the stack. If the machine encounters an a after ab, it accepts (by entering an accept state and moving its head to the end of the input). If the stack becomes empty before the end of the input is reached, of if the end of the input is reached without the stack becoming empty, the machine accepts. Otherwise it rejects. ‘The PDA scans across the input string and pushes every symbol it reads until it reads a #. If # is never encountered, reject. Then, it skips over part of the input, nondeterministically deciding when to stop skipping. Then, it compares the input symbols it next read with the symbols it pops off the stack. At any disagreement, or if the input finishes while the stack is nonempty, this branch of the computation rejects. If the stack becomes empty, the machine accepts. The PDA uses its nondeterminism to guess the values of ¢ and j and uses its stack to compare a; with 2%. In more detail, first it nondeterministically branches to the procedures in the next two paragraphs.Instructor’s Manual 15 2.8 ‘The machine begins by nondeterministically skipping over a part (possibly empty) of the input until it arrives at a symbol which is either at the be- ginning of the input string or is immediately to the right of a #. Then, ‘the machine continues to read input symbols, while pushing them onto the stack, During this reading and popping phase, two cases arise. In one case, if an input # is read, the machine nondeterministically skips to another # in the input nd continues reading inputs symbols, now comparing them with symbols popped off the stack. If all agree and the stack becomes empty at the same time as either the end of the input of # symbol is reached, accept. However, if a disagreement occurs, or the stack becomes empty before either theend of the input of # symbol is reached, or either the end of the input of # symbol is reached without the stack becoming empty, reject on this branch of the nondeterminism. In the other case, during the reading and popping phase, the machine may nondeterministically chose to enter the reading and popping phase, as just described. Then it continues to operate as in that case. Here is one derivation: (SENTENCE) = (NOUN-PHRASE)(VERB-PHRASE) => (CMPLX-NOUN) (VERB-PHRASE) => (cMPLX-NOUN){CMPLX-VERB) (PREP-PHRASE) => (ARTICLE) (NOUN){CMPLX-VERB){PREP-PHRASE) => The boy (VERB)(NOUN-PHRASE)(PREP-PHRASE) => The boy (VERB)(NOUN-PHRASE) (PREP) (CMPLX-NOUN) => ‘The boy touches (NOUN-PHRASE) (PREP) (CMPLX-NOUN) => ‘The boy touches (CMPLX-NOUN)(PREP)(CMPLX-NOUN) => The boy touches {ARTICLE){NOUN) (PREP) (CMPLX-NOUN) => The boy touches the girl with (CMPLX-NOUN) = The boy touches the girl with (aRTICLE)(NoUN) => The boy touches the girl with the flover Here is another derivation: (SENTENCE) > (NOUN-PHRASE) (VERB-PHRASE) => (CMPLX-NOUN) (VERB-PHRASE) => (ARTICLE) (NOUN) (VERB-PHRASE) => The boy (VERB-PHRASE) => The boy (CMPLX-VERB) => ‘The boy (VERB)(NOUN-PHRASE) => The boy touches (NOUN-PHRASE) => The boy touches (CMPLX-NOUN)(PREP-PHRASE) => The boy touches {ART)(NOUN) (PREP-PHRASE) => The boy touches the girl (PREP-PHRASE) => ‘The boy touches the girl (PREP)(CMPLX-NOUN) => The boy touches the girl with (CMPLX-NOUN) =>16 2.10 2.41 Theory of Computation The boy touches the girl vith (ARTICLE)(NOUN) = The boy touches the girl with the flower Each of these derivations corresponds to a different English meaning. In the first derivation, the sentence means that the boy used the flower in order to touch the girl. In the second derivation, the girl happens to be holding the flower when the boy touches her. A CFG G that generates A is given as follows: G=(V,3,R,5). V is {S, Eas, Ere, C, A} and © is {a,b,c}. The rules are S + Bal | Abbe EBay > aFasb | € Eve > bE tet | € Crccle Andale Initially substituting Za4C' for S generates any string with an equal number of as and bs followed by any number of cs. Initially substituting E,, for S generates any string with an equal number of bs and cs prepended by any number of as. ‘The grammar is ambiguous. Consider the string ¢. On the one hand, it can be derived by choosing E,,C with each of Eg, and C yielding €, On the other hand, € can be derived by choosing AEs. with each of A and Ete yielding ¢. In general, any string a‘b/c* with i = j = k can be derived ambiguously in this grammar. Informal description of a PDA that recognizes A in Exercise 2.9: Nondeterministically branch to either step 2 or step 6. Read and push a's. Read b’s, while popping a” If b's finish when stack is empty, skip c's on input and accept. Skip a’s on input. Read and push b’s. Read c's, while popping b' If c's finish when stack is empty, accept. exes e eee Informal description of a PDA that recognizes the CFG in Exercise 2.1: 1. Place the marker symbol $ and the start variable E on the stack. 2. Repeat the following steps forever.Instructor's Manual 17 3. If the top of stack is the variable Z, pop it and nondetermin- istically push either E+T or T into the stack. 4. If the top of stack is the variable T, pop it and nondetermin- istically push either T°xF or F into the stack. If the top of stack is the variable F, pop it and nondetermin- istically push either (E) or a into the stack. 6. Ifthe top of stack is a terminal symbol, read the next symbol from the input and compare it to the terminal in the stack. If they match, repeat. If they do not match, reject on this branch of the nondeterminism. If the top of stack is the symbol 8, enter the accept state. Doing so accepts the input if it has all been read. ‘The formal definition of the equivalent PDA is (Q,5,T, 6,41, F), where Here Q = {a}; D = {+,x,G), a}; and P= {E,T,F} UL; F = {g2}. The transition function 6 : Q x De x Te —+ P(Q x Ie) is given as follows. {(q2,)} {(q, B4T), (a1,T)} {(q, TxF), (a. F)} {(q, EB), (g1,8)} {(a,€)} 6(q,2,y) 2.12 Informal description of a PDA that recognizes the CFG in Exercise 2.3: 1. Place the marker symbol $ and the start variable R on the stack. 2. Repeat the following steps forever. 8. If the top of stack is the variable R, pop it and nondetermin- istically push either XRX or S into the stack. 4. If the top of stack is the variable S, pop it and nondetermin- istically push either aT or bT'a into the stack. 5. Ifthe top of stack is the variable T, pop it and nondetermin- istically push either XTX, X or e into the stack. 6. If the top of stack is the variable X, pop it and nondeter- ministically push either a or b into the stack. 7. If the top of stack is a terminal symbol, read the next symbol from the input and compare it to the terminal symbol in the stack. If they match, repeat. If they do not match, reject on this branch of the nondeterminism. 8. If the top of stack is the symbol $, enter the accept state. Doing so accepts the input if it has all been read. ‘The formal definition of the equivalent PDA is (Q,,T,4,q1, F), where Q = {qq}; © = {a,b}; P = {R,S,7,X} UE; and F = {qo}. The transition18 2.13 2.14 215 Theory of Computation function 6: Q x E_ x I; —+ P(Q x Iz) is given as follows. {(ane)} ita s {(qu, XRX), (an, 9)} ita R Slaz,y) = 4 {(91ATP), (01 07a)} ifq=a,2=6y=S DEMS) {qr XTX), (GX) (ave)} fe Tr {(a1,8), (a158)} fa es {@se)} ifq=a,2=y a. L(G) is the set of strings of Os and #s that either contain exactly 2 #s and any number of Os, or contain exactly 1 # and the number of Os to the right of the # is twice the number of 0s to the left. b. Assume L(G) is regular. Let A = L(G) Mo"#0*. If L(G) is regular, 0 is A. Let p be the pumping length for A given by the pumping lemma for regular languages. Consider the string w = 0°#0?°, Because |u| > p and w € A, the pumping lemma that w = zyz such that |zy| < p, y # € and zy'z € L(G) Vi > 0. We investigate all possible ways of cutting w and prove that such a cut cannot exist. i) x contains the character #. In this case, y is to the right of #. Pumping it down makes the number of 0s on the right less than twice of the number of 0s on the left. ii) y contains the character #. Pumping y down makes the resulting string contain no #s. iii) z contains the character #. In this case, y is to the left of #. Pumping y down makes the number of 0s on the right more than twice of the number of 0s on the left. In each case the resulting string doesn’t belong to A. Hence A fails the pumping lemma, so it cannot be regular, and neither can L(G). The equivalent CFG in Chomsky normal form is given as follows Sy + AB| CC | BA| BD | BB|e A+ AB|CC| BA| BD | BB B+0C co D+ AB Let L(G;) and L(Gz) be CFGs where G; and Gz are defined as follows. (Here we assume that that the sets of variables are disjoint.) let Gy = (Vi,%, Ri, $1) and Ga = (V2, B, Ra, S2). We construct a new CFG Gy where L(Gy) = (G1) UL(G2). Let $' be new variable that is neither in V; nor in V3. Let Gu = (VWUVAU{S'}, E, Ri UR2U{ro}, 5"), where ro is S! +S; | S2.Instructor’s Manual 19 2.16 2417 2.18 We construct CFG G, that generates L(G) 0L(Ga) as in Gy by changing ro in Gy into S’ + 5,52 To construct CFG G, that generates the language L(G1)*, let 5” be a new variable not in Vj and make it the starting variable. Let ro be S’ + S'S, | € bea new rule in G-. Let A be a regular language generated by regular expression R. If R is one of the atomic regular expressions 6, for b € X, construct the equivalent CFG ({S}, {0}, {S + 8}, $). If R is the atomic regular expression €, construct the equivalent CFG ({S}, {b}, {S$ + e}, S). If Ris the atomic regular expressions 0, construct the equivalent CFG ({S}, {b},{5 + 5}, 5). If Ris a regular expression composed of smaller regular expressions combined with a regular operation, use the result of Problem 2.15 to construct an equivalent CFG out of the CFLs that are equivalent to the smaller expressions. Let C be a context-free language and R be a regular language. Let P be the PDA that recognizes C, and D be the DFA that recognizes R. If Q is the set of states of P and Q! is the set of states of D, we construct a PDA P’ that recognizes CM R with the set of states P x Q. P’ will do what P does and also keep track of the states of D. It accepts a string w if and only if it stops at astate q € Fp x Fp, where Fp is the set of accept states of P and Fp is the set of accept states of D. Since O'R is recognized by P’, it is context free. Let be the regular language a*b*c*. If A were Aa CFL then AN.R would bea CFL by part (a). However, AN R = {a"b"c"| n > 0} and Example 2.20 proves AN R is not context-free. Thus A is not a CFL. Let A = {0"1"0"1"| n > 0}. Let p be the pumping length given by the pumping lemma. We show that s = 0°1?0?1? cannot be pumped. Let 5 = wvay2. Ifeither v or y contain more than one type of alphabet symbol, uv?zy?z does not contain the symbols in the correct order. Hence it cannot be a member of A. If both v and y contain (at most) one type of alphabet symbol, uv2y?z contains runs of 0's and 1's of unequal length. Hence it cannot be a member of A. Because s cannot be pumped without violating the pumping lemma conditions, A is not context free. Let B = {o"#0*"#0%"| n > 0}. Let p be the pumping length given by the pumping lemma. Let s = 0°#07P#0°?, We show that s = uvzyz cannot be pumped. Neither v nor y can contain #, otherwise zv?wy?z contains more than two #s. ‘Therefore, if we divide s into three segments by #’s: 0?, 0??, and 0°?, at least ‘one of the segments is not contained within either v or y. Hence, 2u?wy?z is not in B because the 1: 2: 3 length ratio of the segments is not maintained.20 2.19 2.20 Theory of Computation c. Let C = {wiz| w is a substring of z, where w,x € {a,b}*}. Let p be the pumping length given by the pumping lemma. Let s = a?bP#aPb?. We show that the string s = uvzyz cannot be pumped. Neither » nor y can contain #, otherwise uv°xy°z does not contain # and therefore is not in C. If both v and y are nonempty and occur on the left- hand side of the #, the string uv*zy?z cannot be in C’ because it is longer on the left-hand side of the #. Similarly, if both strings occur on the right-hand side of the #, the string uo®zyz cannot be in C, because it is again longer on. the left-hand side of the #. If only one of v and y is nonempty (both cannot be nonempty), treat them as if both occurred on the same side of the # as above. ‘The only remaining case is where both v and y are nonempty and straddle the #. But then v consists of b’s and y consists of a’s because of the third pumping lemma condition |vzy| < p. Hence, uv®2y?z contains more b’s on the left-hand side of the #, so it cannot be a member of C. Let D = {a:#2,#-+-#z4| k > 2, each 2; € {a,b}*,and for some ij, my=2;}. Let p be the pumping length given by the pumping lemma. Let s = aPbP#aPbP. ‘We show that s = uvzyz cannot be pumped. Use the same reasoning as in part (c). Note: The version of the problem that appears in the first printing is in- correct. The correct version (which appears in the second and subsequent printings) is: Show that the language F = {a‘b/c*| i,j,k > 0 and if then j = k} satisfies the three conditions of the pumping lemma even though it is not regular. Explain why this fact does not contradict the pumping lemma. Every rule of a Chomsky normal form grammar is of the form ABC Ava (except possibly for the rule $ + e, where S is the start variable. This rule isn’t used in the derivation of w because n > 1.) Consider a derivation of w. Each application of a rule of the form A> BC increases the length of the string by 1. So we have n — 1 steps here. Besides that, we need exactly n applications of terminal rules (A —+ a) to convert the variables into terminals. Therefore, exactly 2n — 1 steps are required. Note: The version of the problem that appears in the first printing is in- correct. The correct version (which appears in the second and subsequent printings) replaces the phrase “more than b steps” with the phrase “at least 2° steps”. Let G be a CFG in Chomsky normal form that contains b variables. Assume G generates a string w using a derivation with at least 2° steps. Let n be the length of w. By the results of Problem 2.20, n > 21 > 2-1,