CMPS 257 Final, Spring 2004

ent CMeRICAN UNIVERSE LIBRARY oF BEIRUT CMPS 257 Time: 2 Hrs Final Exam Spring 03-04 Family Name First Name Id. Num 1 2 Section (9:00 TR) —_((11:00 TR) PART/Problem Grade Your Grade I 20 II 30 Ill. 1 10 Ill. 2 10 Ill. 3 10 Il. 4 15 Il. 5 10 Ill. 6 15 III. 7 10 Ill. 8 20 EEE Dae A Total Instructions Write your names, Id number, and circle your section in the space provided above. THIS IS A CLOSED BOOK, CLOSED NOTES (OPEN MIND ?) Exam !! Your answers must be presented on the question sheet itself. Use the provided space for your answers. If the space is not enough, then most probably you are writing more than what is expected. In case you need more space, put an “explicit pointer” to where your ) For scratch work, you may use the back of the sheet, and the last blank page. DO NOT CUT OFF ANY PAGE !! There are 13 pages altogether. Try to solve as much as you can in the given time (120 minutes). Good Luck Page 1/13 eee am nena ea JeMEIUCAN ONTVERSIT | LIBRARY | OF BEIRUT ~ Part I. }(20 Points) True or False questions. Circle T or F [ Not Both ] You might want to comment briefly, if you are not sure about your answer. But in case your comment is not relevant, and you have the right answer, you might loose the points for that part If a language is regular, then there are infinitely many regular r/ expressions that represent it. The complement of a decidable language is necessarily decidable Context free languages are closed under complementation . Any subset of a decidable language is necessarily decidable . Decidable languages are closed under intersection. There is an uncountable number of languages that are not Turing-recognizable . Every string generated by a context free grammar has exactly one left most derivation.. Push down automata cannot be simulated by Turing machines A non-deterministic finite automaton might have an infinite computation on a string w. . For Turing machines, if the halting problem is decidable, then the acceptance problem will be decidable Page 2/13 Part II. (30 Points) Multiple choice problems, 10 of them The multiple-choice problems, are intended to have only one correct answer. If you discover otherwise, do indicate that in writing and circle all what you think is a correct answer. 1. Which of the following best expresses the pumping theorem for context free languages ? 8 A language L is context free if there is a pumping length p such that for any string weZ of length greater than or equal to p, w can be subdivided as w = uvxyz in such a way that either v or y is nonempty, |vxy| < p, and uv” xy" z is in L for every n > 0. b. Suppose L is a CFL. Then for some p > 0, the pumping length for L , any string wel of length greater than or equal to p, every subdivision of w = uvxyz , with either v or y is nonempty, then |vxy| < p, and uv" xy” z is in L for every n > 0. Suppose L is a CFL. Then for some p > 0, the pumping length for L , any string weL of length greater than or equal to p, there is a subdivision of w = uvxyz , such that either v or y is nonempty, |vxy| < p, and uv" xy” z is in L for every n 2 0. Suppose Z is a CFL. Then for every number p >0, and for any string we of length greater than or equal to p, there is a subdivision of w = uvxyz , such that either v or y is nonempty, |vxy| < p, and uv" xy" z is in L for every n = 0. 2. The language {w | w has an equal number of occurrences of 01 and 10 }is: a not regular, because any finite automaton has only a finite amount of memory, and so cannot keep count of the number of 01 and/or 10’s, for a string with arbitrary length equal to the set of strings that start and end with the same symbol and hence is regular . finite . hot context free 3. Let A = {<M>: Mis a Turing machine, and M satisfies a property P}. The complement of A is a. {<M>| Misa Turing machine, and M does not satisfy property P } b. {<M> | Mis a Turing machine, and M loops on some input } ¢. {<M> | Misa Turing machine, and M accepts all input } d’ {u| wis not a valid coding of a Turing machine} U{<M> | is a Turing machine, and M does “not satisfy property P } 4. The Church-Turing thesis A. Says that all problems can be solved by algorithms ‘b presents the Turing machine as a formal definition for the intuitive notion of an algorithm ¢. says that some problems cannot be solved by algorithms d. was proven to be wrong in the 1970’s 5. By a solvable problem (or decidable problem) is meant . The problem has a mathematical solution There is an algorithm to solve the problem ¢. There is an algorithm to solve the problem and the algorithm is efficient d. The problem is in NP. Page 3/13 » ILA is NP — cumplete , dic uicuibesship in dA van be verified quickly and decided quickly verified quickly and decided slowly verified slowly and decided quickly verified slowly and decided slowly . The extended Tm model for which the one-tape simulating Turing machine is significantly slower (exponential) running time is the . the k-tape Turing machine .. the non-deterministic Turing machine The two-way infinite tape Turing machine The enumerator 8. The language that expresses the emptiness problem for Turing machines Ey, is: a. {<M w>| Misa Turing machine that does not halt on w} b. {<M, w>| Misa Turing machine that rejects w} c. {<M> | Misa Turing machine that halts on ¢} ( {<M> | Misa Turing machine, and L(M) = 6 } 9. The universal Turing machine is a. the ultimate Turing machine, that simulates any variant (multi-tape, enumerators, etc...)of the Turing machine model b, a decider for Atm Qc) capable of simulating any Turing machine on any input d. a decider for ALBA . The acceptance problem for linear bounded automata, A: pa is decidable essentially because an LBA has a finite amount of memory, so it runs out of memory in finite time for a given LBA B and a string w, there is a finite number of possible configurations for the computation of B on w a linear bounded automaton B must halt on any w an LBA has the mechanism to guess whether it will halt on w or not Page 4/13 PART III. Problems. Problem 1.(10 Points) Give an example for each of the following (No proof is required) a. A language that is context free but not regular ai b. A language that is decidable but not context free aA LS cee c. A language that is Turing-recognizable but not decidable ol t YW d. A language that is not Turing-recognizable Ca re a e. A language that is infP ; Problem 2.(10 Points) Let © = {0,1}, and consider the language L = {w €=* | the i symbol in w is 0, whenever i iis odd } . aye’ ae a. Show that Z is regular by giving the state diagram of a DFA that ‘yo . recognizes L. v b. Give a simple regular expression for describing L. Page 5/13 Problem 3.(10 Points) Consider the language L = {0" 1"| msn<2m} a. Show that Z is context free by giving a PDA that recognizes L. b. Give a simple CFG for L. Page 6/13 Problem 4.(15 Points) Let 2 = {0,1}, and consider the language L = {uu |uex* } a. List in lexicographic order the first 8 strings in L . b. Show that Z is not regular by using the pumping lemma for regular languages. c. Consider the following incorrect “proof” that attempts to show that Z above is regular: LetA={u|luexX*}. 1. A is obviously regular. 2. Now, L=AA 3. But regular languages are closed under concatenation. 4. Therefore, L is regular. Which step in the “proof” is false, and why ? d. If 2 = {0}, would the language L = { uu | ueX* } be not regular ? Why ? Page 7 / 13 Problem 5 (10 Points) Consider the acceptance problem for Turing machines represented by the language: Arm = { <M, w>| Misa Turing machine that accepts string w} a. Show that Arty is Turing-recognizable. In showing that Arm is undecidable, we introduced a Turing machine D as follows: D=“On input <M>, where M is a Turing machine: 1. Run Hon input <™, < >> 2. IfH accepts, reject; if H reject, accept.” What is H supposed to be, and what is the missing second component in Step 1 of D? c. Then a contradiction is arrived at by running D on some input. What is the input, and what is the contradiction ? Page 8 / 13 Problem 6.(15 Points) Suppose that L is recognized by a DFA M with n states. Prove each of the following: a. Lis nonempty if and only if M accepts a string of length less than 1. (Hint: Take a string in Z of minimal length, and show that its length must be less than n.) b. Lis infinite if and only if M accepts some string w where n < |w| < 2n; i.e. the length of w is between n and 2n. Page 9/13 c. Using (b) of the previous problem or otherwise, show that INFINITE pa is decidable, where INFINITEpas = { <F> | F is a finite automaton (not necessarily deterministic, and L(F) is infinite } Page 10/13