CMPS 257 Final, Fall 2004

facie aN UNTIWERSIT | LIPRARY CMPS 257 ee ee Time: 2 Hrs Final Exam Fall 04-05 Family Name First Name Id. Num Major PART/Problem Your Grade I 10 I 30 Tl. 1 10 Ill. 2 15 IIL. 3 10 Ill. 4 15 Ill. 5 15 IIl. 6 25 Ill. 7 10 TL. 8 10 Ill. 9 10 Total 160 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 shect 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. Part I. ](10 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 1. Ifa language is regular, then there are only a finite number of , I T F DFA’s that recognize it. 1 < : / +0 fe ti, 2. Any subset of a Turing recognizable language is necessarily T 5 Turing recognizable Se a a 3. The complement of a decidable language is decidable T-| F 4. There is an uncountable number of languages that are not T a Turing-recognizable 5. Push down automata can be simulated by Turing machines wy F Part I. (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 ? a. 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 yis nonempty, |vxy| < p, and uv" xy" z is in L for every n > 0. b. Suppose Z is a CFL. Then for some p > 0, the pumping length for L , any string we of length greater than or equal to p, every subdivision of w = uvxyz , with v or y nonempty, then |yxy| < p, and uv" xy" zis in L for every n 2 0. c. Suppose Z is a CFL. Then for some p > 0, the pumping length for L , any string weZ of length greater than or equal to p, there is a subdivision of w = uvxyz , such that v or y is nonempty, |vxy| < p, and uv" xy" zis in L for every n > 0. d. 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 v or y is nonempty, |vxy| < p, and uv" xy"z is in LZ for every n = 0. 2. The language {w | w has an equal number of occurrences of 0’s and 1’s }is: not regular equal to {0"1"| n> 0} . finite mt iS C f not context free aoe} Page 2/14 - The complement of Eyy = {<M>|M is a Turing machine, and M has an empty language} is {<M> | Mis a Turing machine, and L(M) is not empty } {<M> | M is a Turing machine, and M loops on some input } {<M> | Mis a Turing machine, and M accepts all input } {u | wis not a valid coding of a Turing machine} U{<M> | is a Turing machine, and L(M) is not empty} . The Church-Turing thesis says that all problems can be solved by algorithms presents the Turing machine as a formal definition for the intuitive notion of an algorithm was proved by Turing in the 1930’s was proved to be wrong in the 1970’s aoe p Meow . By an unsolvable problem (or undecidable problem) is meant The problem has a mathematical solution There is no algorithm to solve the problem There is an algorithm to solve the problem but the algorithm is not efficient The problem has no mathematical solution pole y . The halting problem shows that Every Turing machine must halt There cannot be an algorithm for discovering logical errors in programs Turing decidable languages are also Turing recognizable A Turing machine might loop on its input \ RoE ~~ . In showing that a nondeterministic Turing machine can be simulated by a regular Tm, the traversal of the tree of computations Must be done using breadth search fage (39 Must be done using depth first search Depth first search or breadth first search may both be used will not end since there will definitely be an infinite path in the tree Fin #- c. d. foo} . The language that expresses the equivalence problem for Turing machines EQyy is: {<M, w>| Mis a Turing machine that does not halt on w} {<M, N>| Mand N are Turing machines, and L(M) = L(N) } {<M, N>| Mand N are DFA’s, and L(M) = L(N) } {<M, N>| Mand N are Turing machines, and L(M) = L(N) = 6} . The universal Turing machine is the ultimate Turing machine, that simulates any variant (multi-tape, enumerators, etc...)of the Turing machine model . adecider for Ary capable of simulating any Turing machine on any input . adecider for Ery . The acceptance problem for context free grammars, Acrg was shown to be decidable essentially because every grammar has an equivalent unambiguous grammar . the length of a derivation of a string w in a context free grammar in Chomsky normal form is of length bounded by 2|w| -1. . there is an equivalent PDA for any CFG . itis reducible to the acceptance problem for DFA’s (Apra) PART III. 9 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 007 pot ONC 7) b. A language that is decidable but not contest oct oe ( us o 4} ” z “ c. A language that is Turing-recognizable but not decidable HA ltpy d. A language that is not Turing-recognizable Te e. A language that is not context free, but its complement is context free pee Poy ve Problem 2.(15 Points) Let 2 = {0,1}, and consider 4 = {w €2* | the first and last symbol in w are the same} a. List the first 6 elements of A in lexicographic order. anole, wae HUE AD NN » o> Zu, oO, Los li, teste) Rog soo (ict an & f b. Show that 4 is re gular by giving the state diagram of a DFA that recognizes A. Ae Le ty @ aed © a> C- ° aie ~ t t 4 w) yt o~ r 0 ron O 0 - c. Give a simple regular expression for describin VAN) Sy D me (WN =o, (1 CWO) > © (ileye) © as . ww YD, > gan Sof a) d. Show that {w | w has an equal number of occurrences of 01 and 10 } is regular. ¢ A a fon rhe , (oF (2 0) od by DFA EL ~ > -» Oo Problem 3.(10 Points) ~ . . Consider the language B= {0"1"|m<n<mt+1} “+ © Vi etl, ect, cel), ove I)! a. List the first 6 elements of B in lexicographic order. Le Pee) Gol, B11 b. Show that B is context free by giving a PDA that Tecognizes B.- ~ a ee c. Give a simple CFG for B. S—p SI / Page 5/14 Problem 4 (15 Points) Consider the acceptance problem for Turing machines represented by the language: Am = {<M,w>|Misa Turing machine that accepts string w} a. Show that Arm is Turing-recognizable. ( pt ne i , be » doer poe y ma b. 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 H on input <M, < {\ >> 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? tloyte pee “ eos . . ak 4 . 7 Kolko, Were ecdive x Ho We se opese c. Then a contradiction is arrived at by running D on some input. What is the input, and what is the contradiction? Ky i puk fo DO Page 6/14 Problem 5. (15 Points) Consider the language B = {0"1"| n> 0 }. Suppose that M is a Turing machine that decides B. a. Is<M,001>in Ary ? Why? ve b. Is <M, 0011>in Atm 4? Why? 7e.¢ c. Is <M> in Em? Why? noe 4 p Ne d. If we run the universal Turing machine U on input <M, 001> will it accept, reject, or what? Why ? e. If we run the universal Turing machine U on input <M> will it accept, reject, or what? Why ? HO ve seve big pee Vv “* ok Page 7/14 Problem 6. (25 Points) . Consider the following state diagram of a Tm M whose language is supposed to be C = {ww*| we {0,1}* } LOR ‘oO EO) UR Sur 4,1 0,1 >oL $ >#,L ‘ Y LOR FOR Wr ff -o (2 1 #,R 7 | FOR Com We have used the convention that missing arrows are arrows that would have pointed to reject - There are some ‘bugs’ in the transition rules as given. Correct them in the following table: Arrow Label should be From q4 to G6 03#,R a. 1 From qs to G6 3 From gg to q7 Page 8/14 b. Give a high level description of M.as corrected M =“On input w: 1. c. Ifthe arrows from gq to Y¢ and gs to qe are left as given the language of the Tm would be {wu® | we {0,1}* and w is_ Yow 42 “\ To } d. Is the given Tm M after correction, a decider ? Why ? Ks , he cewok A Goce? de ihe : e. Given your answer in (d), is the language C = {ww* | we {0,1}* }decidable ? Justify your answer. es . CU only wets be ais (Art WW Acc Ada Ne Came e oe ep. Page 9/14 f. Modify to the given Tm so that it becomes a decider for P = {w=w" | we {0,1}* } Le. set of all palindromes over {0,1}. Indicate your modifications on the diagram below. Give a brief explanation. LOR > Gh Page 10/14