CMPS 257 Final, Spring 2005

CMPS 257 Time: 2 Hrs Final Exam Spring 04-05 Family Name First Name Id. Num Section 1 2 (9:30 TR) _(11:00 TR) PART/Problem Grade Your Grade aoe 15 ° 10 15 10 15 20 25 25 15 ©} C0|~I} AD] on] Bp Oo} bo] re : Total 150 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 answer is written or continued (e.g. draw an arrow, or say back of page or both !!!...) For scratch work, you may use the back of the sheet, and the last blank page. DO NOT CUT OFF ANY PAGE !! There are 14 pages altogether. Try to solve as much as you can in the given time. GOOD LUCK ™ tibet \ ; Nan . / Page 1/14 Problem 1.(15 Points) Consider the following diagram, which is supposed to express the relationship among classes of languages, that we have learned about this semester. Each of these classes is associated with a computation model of computing. In addition, containment is proper, i.e. there are languages that are in the outer class of languages and not in the inner class. Ls= =* Complete the following table. Class AssociatedComputing Model Language in L£; but not in Lis oe “ alla Oy af ‘hon ie Page 2/14 Problem 2 (10 Points) a. What are the practical implications (on compiler construction) of the fact that the acceptance problem for context free grammars, Acgg is decidable. b. What are the practical implications (on possibility of having a super compiler for discovering logical errors in programs) of the fact that Halting problem, HALTry is undecidable ? Page 3/14 Problem 3.(15 Points) Let = = {0,1}, and consider the language B = { w € =* | w has exactly three 0's } a. Give the state diagram of a DFA M that recognizes B, using as small a number of states as possible. b. Based on your answer in (a) above, what is the pumping length for B ? Why ? c. Give as simple a regular expression as possible representing the language B. Page 4/14 Problem 4.(10 Points) For any DFA M=(K, X, 6, s, F) define the following sequence { Q; } of subsets of K recursively: Qo=F Own = {qe Q]| there is x, s.t. 8 (, x) € QO; } i= 0,1,2,.... i.e. ge Q; if from g an accept state might be reached inj steps. a. Can the sequence of sets Q; be all distinct ? Why ? yl Page 5/14 Problem 5.(15 Points) For any language A, let A; be the set of all first halves of strings in A; that is A; = {u| for some v, |u| = |v| and wv € A } E.g. A= {010, 10, 101, 0011, 1010} then Ay = {1, 00, 10} (Contributions from 10, 0011, and 1010; odd length strings of A do not contribute to Aj. a. (Difficult) Show that if A is regular, then A; is also regular. (Hint: Make use ‘ ) of the sets Q; as introduced in the previous problem.) b. What is A; if A is the set of palindromes; i.e. = fwe=w* | we{0,13}*} ? Why? c. Is the converse of (a) true? (i.e. If A; is regular, then A is also regular.) Why ? Page 6/14 Problem 6.(20 Points) Let G=(V, x, R, S) be a CFG. A variable Ae V is said to be useful if there is at least one weL(G) such that: S>..2xAy>. >w where x, y € (VUZ)*. In words a variable is useful if it occurs in at least one derivation. A variable that is not useful is called useless. A production rule is useless if it involves any useless variable. Thus, a variable is useless because either there is no way of getting a terminal string from it or because there is no way it may be reached in a derivation starting at S (or both). ee fo ah UA ys Consider the Grammar fw : an Sad | aBB im LURAY A) A->aad | Ns / B-» bB | bbC AUF Be: “ CoB ieee a. Are there useless variables in the grammar as given ? What are they and why ? (a tO b. Based on your answer in the previous part, give an equivalent grammar to the given one, with no useless variables. c. What is the language generated by the given grammar. Page 7/14 d. Suggest a general algorithm for removing useless variables and their associated production rules, to convert a given grammar to an equivalent grammar without useless variables. Page 8/14 Problem 7 (25 Points) Consider the following implementation level description of a Turing machine M, M, =" On input string w: 1. Scan the tape and mark the first 0 which has not been marked. If no unmarked 0 is found, go to stage 4. Otherwise move the head back to the front of the tape. 2. Scan the tape and mark the first 1 which has not been marked. If no unmarked 1 is found, reject 3. Move the head back to the front of the tape and go to stage 1. 4. Move the head back to the front of the tape. Scan the tape to see if any unmarked 1s remain. If none are found then accept; else reject" a. Argue that M, is a decider b. What is the language, A; decided by M,? Give a brief explanation c. Based on (b), what is the smallest k for which 4;¢ TIME(n‘). Why ? t Page 9/14 d. Give a state diagram that represents the machine M,. e. Suppose we were to decide 4; using a two-tape Turing machine. How can you improve on the complexity obtained in (c) ? Page 10/14