I have a theory of computation test on DEC 12th at 2pm EST.
Last name (please print) First name (please print) Student Number western university department of computer science CS3331 - Foundations of Computer Science – Fall 2015 – Final Exam Instructor: Dr. Lucian Ilie Friday, Dec. 11, 2015, 7:00pm - 10:00pm P&AB106 (Absi - Meht), P&AB148 (Meye - Zhu) This exam consists of 6 questions worth a total of 100 marks. No other materials are allowed, such as cheat-sheets (or any other sheets), books, or electronic devices. All answers are to be written in this booklet. For each question, if use the back of the page or the scrap work sheets at the end to write your answers, please indicate this clearly on the page that contains the question. The exam is 120 minutes long and comprises 30% of your final mark. (1) 10pt (2) 10pt (3) 30pt (4) 10pt (5) 30pt (6) 10pt Grade CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 2 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 3 1. (10pt) Construct a deterministic Turing machine M that decides the language L = {w ∈ {a, b}∗ | w contains at least three a’s} . M starts with the initial configuration (s,�w) and halts with the configuration (q,�w), in the appropriate state q ∈ {y, n}. Describe M using the macro language (e.g.: aR�bL#) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 4 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 5 2. (10pt) The set SD is closed under intersection. Is the following a correct proof of this fact? Explain your answer. Assume L1, L2 ∈ SD, semidecided by two Turing machines M1 and M2, respectively. We can build a machine M to decide L1 ∩ L2 as follows: 1. on input w 2. run M1 on w 3. if M1 accepts, then 4. run M2 on w 5. if M2 accepts, then accept CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 6 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 7 3. (30pt) Can you give an example of a language L such that: (a) L ∈ D and ¬L ∈ SD − D? (b) L,¬L ∈ SD − D? (c) L ∈ SD, ¬L 6∈ SD? (d) L,¬L 6∈ SD? Prove your answers. (¬L is the complement of L.) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 8 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 9 4. (10pt) Assume a language L and a Turing machine M that lexicographically enumerates L. Construct a Turing machine M ′ that decides ¬LR (the complement of the reversal of L). (Only clear English description is required.) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 10 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 11 5. (30pt) For each of the following languages, prove whether it is in D, SD − D, or ¬SD. Explain first intuitively why you think it is in D, SD−D, or ¬SD, then prove your assertion rigurously. (a) L1 = {< m="">| L(M) is finite}. (b) L2 = {< m="">| L(M) 6= ∅}. (c) L3 = {< m1,m2="">| L(M1)− L(M2) is infinite}. (d) L4 = {< m,w="">|M accepts w and rejects wR}. CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 12 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 13 6. (10pt) (a) Does the following instance of PCP have any solutions? Prove your answer. a bab bbb bb aab ab b a (b) If you can determine, as you did at (a), whether a PCP instance has solutions or not, how is it possible that the Post Correspondence Problem is undecidable? (c) Can you give an example of an instance of PCP that has only one solution? Prove your answer. CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 14 CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 15 (scrap work) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 16 (scrap work) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 17 (scrap work) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 18 (scrap work) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 19 (scrap work) CS3331 – Final Exam – Friday, Dec. 11, 2015, 7:00pm - 10:00pm, P&AB106/148 20 (scrap work)