CMPS 257 Final, Spring 2003

American University of Beirut CMPS 257 Theory of Computation Spring 2002-2003 Final Exam Date: June 7", 2003. 8:00 — 10:00am. Instructor: Jihad Boulos Name: Section: ...........cceeceeees This is an open-book, open-note exam. Your exam should have 1] pages, and there are 10 questions totaling 100 points. You may use your notes (i.e., class handouts) and the main course textbook. You are NOT allowed to use any external notes. Your answers should be concise, and when possible should be a list of important points rather than prose. Solve as much problems as you can. I advise you to spend time on understanding the problem and budget your time for solving each problem, or else you will be wasting a lot of time on one problem and will run out of time for other problems. Wordy and/or irrelevant answers will reduce your score for that problem. Your answers should be the summary of work done on scratch paper that you do not hand in. If Icould not read your writing, I will just give a ZERO without bothering myself trying to understand what you are writing. The space allocated for answers should be sufficient for your answers. If not, use the back of papers. MERICAX UNTVERSIT?) LIBRARY OF RBFIRUT Circle for each statement (TRUE) for true, (FALSE) for false, or (UNKNOWN) for unknown to researchers. Exercise 1 (7.5 points): 1. Recursively Enumerable (RE) languages are closed under union and under intersection. TRUE FALSE UNKNOWN . Deterministic and non-deterministic finite automata accept exactly the same class of languages. TRUE FALSE UNKNOWN Regular languages are closed under union, complementation, and intersection. TRUE FALSE UNKNOWN Context-free languages are closed under union and under intersection. TRUE FALSE UNKNOWN . The problem of determining if a string over {a, b} is described by a given regular expression over that alphabet is decidable. TRUE FALSE UNKNOWN . The problem of determining if a string over {a, b} is generated by a given context-free grammar over that alphabet is decidable. TRUE FALSE UNKNOWN {ww lw in {0, 1}*} is not regular but it is context-free. TRUE FALSE UNKNOWN Ifa language A is a subset of a language B, and A is non-recursive, then B is also non-recursive. TRUE FALSE UNKNOWN . Every regular language can be recognized by a deterministic pushdown automaton. TRUE FALSE UNKNOWN ERICAN UNTVERSIT LIBRARY OF BEIRUT . Anon-deterministic TM accepts its input if every possible computation on the input leads to an accepting state. TRUE FALSE UNKNOWN . Every finite set is regular. TRUE FALSE UNKNOWN . Every context-free grammar can be made unambiguous. TRUE FALSE UNKNOWN . The computational path of a TM on an input w either halts accepting, halts rejecting, or enters a never halting loop of repeating configurations. TRUE FALSE UNKNOWN . Let A and B be two sets. If there exists a surjection f: A > B and an injection g:A — B between A and B, then there exists a bijection h: A > B. TRUE FALSE UNKNOWN . For all finite sets A, the complement of A is a context-free language. TRUE FALSE UNKNOWN Exercise 2 (5 points): This question explores the relations among the various classes of Janguages. a. Indicate ALL the regular languages below (by circling the item number to its left). i All strings over {0, 1} that have equally many 0’s and 1’s. ii. All strings over {0, 1} that have an even number of 0’s and an even number of 1’s. All strings over {0, 1} that start with a 0 and do nor contain fifty 1’s in arow. b. Indicate ALL the languages below that ARE context-free but ARE NOT regular (by circling the item to its left.) {a"b"c" In 20} {a"b"c# ln, m, k= 0} [awenn oS UNIVERSIT LIBNARY QF BEIRUT iid. {a"b"|0SnSmS2n} Indicate ALL the languages below that ARE recursive but NOT context-free (by circling the item to its left.) i. {ww lwin {a,b il. {wew |win {a,b iii. {a""b"c" In > 0} R. : : . }*}, where w" is the string w written in reverse. }* } . Indicate ALL the languages below that ARE recursively enumerable (RE) but NOT recursive (by circling the item to its left.) i. {(M, w)!TM M accepts input w} ii. {M1TM M is such that L(M) # OD} iii. {(M,, Mz)! TMs M; and M2 are such that L(M,) = L(M2)} Indicate ALL the languages below that ARE NOT recursively enumerable (RE) (by circling the item to its left.) i. {(M, w)!TM M halts on input w} ii {M1TM M is such that L(M) # } {(M), Mz) |TMs M; and M2 are such that L(M)) A L(M2) = ®} Exercise 3 (6 points): apm ot Construct a grammar G over {a, b, c} such that L(G) = {a”b"c' |O<n+mSi}. ANSWER: MERICAS UNTVENSIT LIBRARY OF BEIRUT Exercise 4 (16 points): a. Give a pushdown automaton that accepts the following language: L={wa"é {a,b}* 1 lwl=n} ANSWER: b. Give a regular expression for the language L of al] strings w € {0, 1}* such that string w begins or ends with 00 or 11. For example, 00101 and 011 are in L, but 010 is not in L. ANSWER: c. Transform the following regular expression into an equivalent NFA using the procedure studied in class. (You may omit some of the redundant € transitions, but your automaton should have a structure that closely resembles the regular expression.) ((a U ba)(ab)*ba)* ANSWER: ERICAN CNTVERSIT LIBKAR Y be BIRT ————— d. Give a context free grammar for the language of L: L={ a'ble* |i,j,k> 0 and either i#j or i = 2k (or both)] ANSWER: Exercise 5 (6 points): Is it possible to m-reduce Ary to EQcrg? (2 points) Explain your answer bellow: (4 points) ANSWER: AMERIC VS UNIVERSIT LIBRARY OF BEIRUT Exercise 6 (10 points): State whether the language L C (a, b,c, d}*, defined by L={a™b'c"d"\n,me N} is context-free or not and prove your statement. ANSWER: MERICAS CNIVERSIT LIBRARY OF BEIRUT Exercise 7 (12 points): Let INFry = {(M) | M is a Turing machine and L(M) is infinite}. Suppose that you want to show that Ary <,, INFpy using a reduction f that maps (M, w) to (M)). a. Fil] in the blanks in the following two statements in a way that states what you have to do to make the reduction works. (In both cases you will be writing down something about the behavior of the Turing machine M,.) e If M accepts w, then b. Give the definition of the desired Turing machine M,, given M and w. ANSWER: c. What conclusion about JNF7y follows from the fact that Ary S,, INFry ? (You can get credit for this part without doing the previous two parts.) ANSWER: MEKICAN UNIVERSIT’ LIBKARY OF BEIRUT Exercise 8 (10 points): For each of the following languages L, circle [Dj if L is decidable, circle Rj if Lis recognizable but undecidable, circle IN| if L is not recognizable. L, = {(M)|L() is finite} L2 = {(M)|L(M) € (P- NP)} L3= {(M)|L(M) is recognized by at least one TM} L4= {(M)|L(M) is recognized by at least one polynomial-time NT™ } Ls a language recognizable by at least one polynomial-time NTM. MERICAS ENTVERSIT LIBKARY OF BEIRUT Exercise 9 (12 points): Your last CMPS-257 problem: Let L = {(M)1M prints 257 on some input}. Prove that: a. Lis recognizable (i.e., give a (very simple) TM that would recognize it). b. Lis not decidable. ANSWER: