Answer Happy

1. (10 pts) The language accepted by the the following 1. Labo) 2. Laba) 3. {a} u Loba) 4. {a} u Labda) 0-0-300 2. (10 pts) Let I {w e {a,b} whas the same number of a's and b's). Consider the fol- lowing algorithm that decides L. M = "In input 1. Scan across the tape until a a orb is found. 2. If none is found, accept. 3. If one is found nue scanning until a matching bor 4. If none is found, reject. 5. Otherwise, cross off that symbol and repeat." is found Using the Big-O notation, state the time complexity of each step of M, and the overall tir complexity of M. 1

recognizable or unrecognizable? Justify your answer. 6 (10 pts) Let LOOP - {ania is a TM that loops on all inputs) I. LOOP decidable. 7. (10 pts) We can show that the clique problem is NP-hard by proving that 1. CLIQUE S, SAT 2. CLIQUE S, 3SAT 3. CLIQUES, VERTEX-COVER 4. None of the above 8. (10 pts) Let 4. B. and C be languages. Prove or disprove: If A Sm B and A S.C. then A Sm BC. Justify your answer.