past_exam_01

COSC 1105/7 COMPUTING THEORY MOCK EXAM DATE: 1st June TIME ALLOWED: 3 hours TIME: 2:00pm NUMBER OF PAGES: 5 • The exam commences with fifteen (15) minutes of reading time. Read the questions carefully. • Writing is not permitted until the conclusion of reading time. • If you are unclear about a question, ask for clarification. • You may make reasonable assumptions; state these clearly with your answer. • You are expected to answer all parts of all questions. There are eight (8) questions, worth a total of 120 marks. Marks for each question are shown. Questions are not worth equal marks. • Questions may be answered in any order; hence you should start with the questions you consider easiest, and end with the ones you consider hardest. • This is a closed book examination. You must not refer to any written or printed materials during the examination aside from the exam paper itself. • You may take the exam paper with you after the session. • If you do not understand what is required to answer a particular question, ask for clarification during the reading time. When asked to “briefly explain” something, or to describe something “informally”, an answer of one or two English sentences is expected.When asked to “explain” or “justify” something, an answer of one or two English paragraphs is expected. • The following may be of use to you. Pumping Lemma Let L be a regular language. Then there is a k ≥ 1 such that for any w ∈ L where length( w ) ≥ k , we have w = xyz where | xy |≤ k , y 6 = λ and xy i z ∈ L for all i ≥ 0. 0

1. Complexity and Cryptography (7+3+3+4 = 17 marks) (a) Two programs had their execution times (in seconds) measured on the same data resulting in the table below. n Program 1 Program 2 (seconds) (seconds) 1 4 2 2 7 4 3 10 8 4 13 16 5 16 32 Based on this data: i. Classify each of Program 1 and Program 2 as either tractable or intractable. Briefly explain your answer. (2 marks) ii. Calculate the time required for Program 1 for n = 10. (1 mark) iii. Calculate the value of n for which Program 1 executes in the same time that Program 2 takes for n = 10. (2 marks) iv. Calculate the largest value of n for which Program 2 executes in under 10 seconds on a machine 100 times faster. (2 marks) (b) Briefly explain the difference between tractable, intractable and undecidable problems. (3 marks) (c) What feature of NP-complete problems makes them useful in cryptography? (3 marks) (d) Briefly explain how RSA can be used to digitally sign messages. (4 marks) 2. Chomsky Hierarchy (10+10 = 20 marks) (a) Classify the languages below as either • regular • context-free but not regular • recursively enumerable but not context-free i. { a i b 2 i | i ≥ 1 } (1 mark) ii. { a i b 2 i c i | i ≥ 1 } (1 mark) iii. { a i b j c k | i 6 = j or j 6 = k } (2 marks) iv. { a i b i c j d j | i, j ≥ 0 } (2 marks) v. { www | w ∈ a * b * } (2 marks) vi. { a i b k c i + j | i, j, k ≥ 0 } (2 marks) (b) Which of the following statements is true? Briefly explain your answer. i. Context-free grammars are more powerful than regular expressions. (2 marks) ii. Regular grammars are more powerful than DFAs. (2 marks) iii. Any variety of Turing machine is equivalent to a deterministic Turing machine with one semi-infinite tape. (2 marks) iv. A PDA with three stacks is more powerful than a PDA with two stacks. (2 marks) v. Context-sensitive grammars are more powerful than PDAs. (2 marks) 3. Grammars (3+5+4 = 12 marks) Consider the grammar G below. S → aS | Sb | A A → bAa | BC B → cB | c C → dC | e 1

5. Chomsky Hierarchy (5+2+2+4 = 13 marks) You may find the following information useful for this question. Pumping Lemma Let L be a language which is accepted by a DFA with k states. Let w ∈ L where | w | ≥ k . Then w = xyz where | xy | ≤ k , y 6 = e and xy i z ∈ L for all i ≥ 0. (a) Let L 1 = { a i cb 2 i | i ≥ 0 } . Prove that there is no DFA for L 1 . (5 marks) (b) Let L 2 = { a 2 i cb i | i ≥ 0 } . Give a context-free grammar for L 2 . (2 marks) (c) Give an example of a string w such that w ∈ L 1 and w ∈ L 2 . (2 marks) (d) Describe in set notation the language L 3 = L 1 ∩ L 2 . Is L 3 context-free? Briefly justify your answer. (4 marks) 6. Pushdown Automata (3+4+3 = 10 marks) Consider the pushdown automaton M below. (a) Trace the execution of M with inputs abcab , aacaa and bbbcaaa . (3 marks) (b) Describe the language of M in set notation and informally. (4 marks) (c) How does the language of M change if we add the transition δ ( q 1 , b, A ) = ( q 1 , e ) to M ? The revised machine is given below. Briefly explain your answer. (3 marks) 7. Turing machines (4+3+6+2 = 15 marks) Consider the Turing machine M below. 3

(a) Trace the computation of M with initial configuration q 0 B 1122. What is the outcome of the computation of M with the inputs q 0 B 101021 and q 0 B 001120? Briefly explain your answer. There is no need to give a full trace for these inputs. (4 marks) (b) Describe informally the result of a computation in M . (3 marks) (c) Give a Turing machine M which given a string w over (0 , 1 , 2) * behaves as follows: • If w does not contain any 2’s, then no changes are made to w . • Otherwise, if w contains an even number of 2’s, then M converts all 1’s in w into 2’s. • If w contains an odd number of 2’s, then M converts all 2’s in w into 1’s. For example, given the strings 100121, 10122 and 010101, your machine should terminate with outputs 100111, 20222 and 010101 respectively. You may use any notation for Turing machines and any variety of Turing machine that you wish. (6 marks) (d) How difficult would it be to change your machine so that if w does not contain any 2’s, then M converts all 0’s in w to 1’s and all 1’s in w to 0’s? Briefly explain your answer (but there is no need to give the changed machine). (2 marks) 8. Universal Turing machines (2+3+4+4 = 13 marks) Consider the definitions below. • A universal Turing machine U is a Turing machine that takes the encoding of a Turing machine M and an input string w and emulates the computation of M on w . More specifically, U takes as input code(M)code(w) , (where code() is a function which encodes Turing machines and inputs into the input language of U ) and for every configuration in the computation of M on w , there is a corresponding configuration in the computation of U on code(M)code(w) . • A universal Turing machine U is obedient for M on w if M terminates on w and U terminates on code(M)code(w) . • A universal Turing machine U is loyal for M on w if M does not terminate on w and U does not terminate on code(M)code(w) . • A universal Turing machine is transparent if for any Turing machine M and input w , U is either obedient for M on w or loyal for M on w . (a) Let M be a Turing machine and w an input on which M halts. Explain why running U on code ( M ) code ( w ) does not tell us anything about whether U is loyal for M on w or not. (2 marks) (b) Let M be a Turing machine and w an input for M . Is it possible for U to be not obedient for M on w and not loyal for M on w ? Briefly explain your answer. (3 marks) (c) Let U be a universal Turing machine that does not terminate for any input. Explain why U cannot be transparent. (4 marks) (d) Let U be a transparent universal Turing machine, and let w 1 and w 2 be inputs to U such that U terminates on input w 1 but U doesn’t terminate on w 2 . Explain why U must terminate on code ( U ) code ( w 1 ) and U must not terminate on code ( U ) code ( w 2 ). (4 marks) End of exam paper 4