past_exam_01-solutions

Computing Theory Exam Solutions 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. Answer: Program 1 has complexity 3 n + 1, which is polynomial, and hence tractable. Program 2 has complexity 2 n which is exponential and hence intractable. (2 marks) ii. Calculate the time required for Program 1 for n = 10. Answer: 3 × 10 + 1 = 31 seconds. (1 mark) iii. Calculate the value of n for which Program 1 executes in the same time that Program 2 takes for n = 10. Answer: 2 10 = 3 n + 1 ≡ 3 n = 1023 ≡ n = 341 seconds. (2 marks) iv. Calculate the largest value of n for which Program 2 executes in under 10 seconds on a machine 100 times faster. Answer: 2 n < 1000 ⇒ n < 10, ie n ≤ 9. Hence 9 is the largest such value. (2 marks) (b) Briefly explain the difference between tractable, intractable and undecidable problems. Answer: A tractable problem is one that can be solved in polynomial time. An intractable problem is one that can only be solved in exponential time or worse. An undecidable problem is one for which there is no algorithm. (3 marks) (c) What feature of NP-complete problems makes them useful in cryptography? Answer: A solution to an NP-complete problem can be checked in polynomial time, but a solution can (almost certainly) only be found in exponential time. This means that it is tractable to check a solution, but not to generate a solution. This can be used allow efficient checking of a password or other key, whilst ensuring that it is intractable to “crack” the system. (3 marks) (d) Briefly explain how RSA can be used to digitally sign messages. Answer: For Alice sending a message to Bob, Alice first encodes the message M with her secret decryption key D A , and then encrypts it with Bob’s public encryption key E B , and sends E B ( D A ( M )) to Bob. Bob then decrypts the mesage with his secret key and then applies Alice’s public key. This Bob ends up with E A ( D B ( E B ( D A ( M )))). (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 } Answer: context-free but not regular (1 mark) ii. { a i b 2 i c i | i ≥ 1 } Answer: recursively enumerable but not context-free (1 mark) iii. { a i b j c k | i 6 = j or j 6 = k } Answer: context-free but not regular (2 marks) 1

iv. { a i b i c j d j | i, j ≥ 0 } Answer: context-free but not regular (2 marks) v. { www | w ∈ a * b * } Answer: recursively enumerable but not context-free (2 marks) vi. { a i b k c i + j | i, j, k ≥ 0 } Answer: context-free but not regular (2 marks) (b) Which of the following statements is true? Briefly explain your answer. i. Context-free grammars are more powerful than regular expressions. Answer: True. Regular expressions are equivalent to regular grammars, which are a subset of context-free grammars. (2 marks) ii. Regular grammars are more powerful than DFAs. Answer: False. Regulgar grammars are equivalent to NFAs which are equivalent to DFAs. (2 marks) iii. Any variety of Turing machine is equivalent to a deterministic Turing machine with one semi-infinite tape. Answer: True. All varieties of Turing machines are 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. Answer: False. Both are equivalent to Turing machines. (2 marks) v. Context-sensitive grammars are more powerful than PDAs. Answer: True. PDAs are equivalent to context-free grammars which are a subset of context-sensitive grammars. (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 (a) Which of the strings abcdab , ccc and abbcdab are derivable from G ? Briefly explain your answer (but there is no need to give full derivations). Answer: S ⇒ aS ⇒ aSb ⇒ aAb ⇒ abAab ⇒ abBCab ⇒ abcCab ⇒ abcdCab ⇒ abcdab S ⇒ A ⇒ BC ⇒ cBC ⇒ ccBC ⇒ cccC ⇒ ccc S ⇒ aS ⇒ aSb ⇒ abAab ⇒ ?? so abbcdab is not derivable. (3 marks) (b) Describe informally and in set notation the language of G . Answer: L ( G ) = { a i b k c l d m a k b j | i, j, k, m ≥ 0 , l ≥ 1 } . This is the set of strings of the form any number of a ’s followed by any number of b ’s then any number of c ’s then any number of d ’s then the same number of a ’s as before and then any number of b ’s. (5 marks) (c) Describe how the language of G changes if we delete the rules S → aS and S → Sb and add the rule S → aSb , making the grammar now S → aSb | A A → bAa | BC B → cB | c C → dC | e Compare this change to the one in which we delete the rule A → BC and add the rule A → CBC , making the grammar now S → aSb | A A → bAa | CBC B → cB | c C → dC | e There is no need to write out the set notation for the new languages. Answer: For the first change, we have the language below. L ( G ) = { a i b k c l d m a k b i | i, k, m ≥ 0 , l ≥ 1 } . This is the same as the first case except that we now have i = j . 2

A domain is either an identifier or a sequence of identifiers separated by a ‘.’. For example, rmit , wwww.rmit.edu.au and www1l.d22.dzz1 are domains, but .32r3r3r3 , rmit.ZXSS.1 and rmit.edu.au.2. are not. An email address is either of the following two forms: • identifier @ domain • identifier % domain @ domain Draw the state diagram for an NFA which recognises valid email addresses. For example, fred@rmit.edu.au, b1@b2.bananas.com123 and joe%wherever@bubbles3.ch1.d4 should be ac- cepted, but fred and fred@ebay@com.au should not. You can use abbrevations such as a - z and 0 - 9 on transitions. Answer: (6 marks) 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 . Answer: Assume that L 1 is regular. Hence there is a DFA M which accepts L 1 . Let the number of states in M be k . Then by the Pumping Lemma for any w ∈ L 1 for which | w | ≥ k there exist x, y, z such that w = xyz , y 6 = e , | xy | ≤ k and xy i z ∈ L 1 ∀ i ≥ 0. Let w = a k cb 2 k . As | w | > k , the Pumping Lemma applies and so we have xyz = a k cb 2 k . As | xy | ≤ k , y must contain only a ’s and so y = a m for some 1 ≤ m ≤ k . Now consider xy 2 z = a k + m cb 2 k , and so xy 2 z 6∈ L 1 , which is a contradiction. (5 marks) (b) Let L 2 = { a 2 i cb i | i ≥ 0 } . Give a context-free grammar for L 2 . Answer: S → aaSb | c (2 marks) (c) Give an example of a string w such that w ∈ L 1 and w ∈ L 2 . Answer: c (2 marks) (d) Describe in set notation the language L 3 = L 1 ∩ L 2 . Is L 3 context-free? Briefly justify your answer. Answer: As L 3 = { c } , this is context-free (a grammars for it would be just S → c ). (4 marks) 6. Pushdown Automata (3+4+3 = 10 marks) Consider the pushdown automaton M below. 4

(a) Trace the execution of M with inputs abcab , aacaa and bbbcaaa . (3 marks) Answer: ( q 0 , abcab, e ) ‘ ( q 0 , bcab, A ) ‘ ( q 0 , cab, BA ) ‘ ( q 1 , ab, BA ) ‘ ( q 1 , b, A ) ‘ ( q 1 , e, e ) ‘ ( q 2 , e, e ) ( q 0 , aacaa, e ) ‘ ( q 0 , acaa, A ) ‘ ( q 0 , caa, AA ) ‘ ( q 1 , aa, AA ) ‘ ( q 2 , aa, AA ) ‘ ??? ( q 0 , bbbcaaa, e ) ‘ ( q 0 , bbcaaa, B ) ‘ ( q 0 , bcaaa, BB ) ‘ ( q 0 , caaa, BBB ) , ‘ ( q 1 , aaa, BBB ) ‘ ( q 1 , aa, BB ) ‘ ( q 1 , a, B ) ‘ ( q 1 , e, e ) ‘ ( q 2 , e, e ) (b) Describe the language of M in set notation and informally. Answer: L ( M ) = { a i b j ca j b i | i, j ≥ 0 } . This is the set of strings containing any number of a’s followed by any number of b’s followed by 1 c followed by the same number of a’s as b’s followed by the same number of b’s as a’s. (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. Answer: This makes the language larger. Previously, there was a sequence of a’s then a sequence of b’s and then the c. Now the a’s and b’s can come in any order, providing that there is a “matching” a for each b. We can also have a sequence of b’s before the first a, provided that there is a matching sequence of b’s at the end. This makes the language now { b i wc w R b i | i ≥ 0 } where w R is the reverse of w and w is w with the a’s changed to b’s and the b’s changed to a’s. For example, abbaabcabbaab is in the new language. (3 marks) 7. Turing machines (4+3+6+2 = 15 marks) Consider the Turing machine M below. (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. Answer: q 0 B 1122 ‘ Bq 1 1122 ‘ B 1 q 1 122 ‘ B 11 q 1 22 ‘ B 112 q 1 2 ‘ B 1122 q 1 B ‘ B 112 q 2 2 ‘ B 11 q 3 21 ‘ B 1 q 3 111 ‘ Bq 3 1211 ‘ q 3 B 2211 ‘ Bq 1 2211 ‘ B 2 q 1 211 ‘ B 22 q 1 11 ‘ B 221 q 1 1 ‘ B 2211 q 1 B ‘ B 221 q 2 1 ‘ B 22 q 4 10 ‘ B 2 q 4 200 ‘ Bq 4 2200 ‘ q 4 B 2200 q 0 B 101021 ‘ Bq 1 1010121 ‘ * B 1010121 q 1 B ‘ B 10102 q 2 1 ‘ B 1010 q 4 20 ‘ * q 4 B 000020 q 0 B 001120 ‘ Bq 1 001120 ‘ * B 001120 q 1 B ‘ B 00112 q 2 0 (4 marks) 5

(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. Answer: U is loyal for M on w if M does not terminate on w and U codes not terminate on code ( M ) code ( w ). As in this case M terminates on w , we cannot state that U is loyal for M on w . (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. Answer: No. There are four cases: i. M terminates on w and U terminates on code ( M ) code ( w ). ii. M terminates on w and U does not terminate on code ( M ) code ( w ). iii. M does not terminate on w and U terminates on code ( M ) code ( w ). iv. M does not terminate on w and U does not terminate on code ( M ) code ( w ). In case 1, U is obedient for M on w , and in case 4, U is loyal for M on w . Hence for this to hold, we must have either case 2 or case 3. In case 2, U is not obedient, but we can’t say that it is not loyal. In case 3, U is not loyal, but we can’t say that it is not obedient. Clearly we cannot have both case 2 and case 3 at the same time, and hence it is not possible for U to be both not loyal and not obedient for M on w . (3 marks) (c) Let U be a universal Turing machine that does not terminate for any input. Explain why U cannot be transparent. Answer: For U to be transparent, it is necessary for U to terminate on code ( M ) code ( w ) when M terminates on w . However, it U does not terminante for any input, it clearly cannot do this. (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 ). Answer: U on code ( U ) code ( w 1 ) must emulate U on w 1 , as U is a universal machine. As U halts on w 1 and U is transparent, we must then have that U halts on code ( U ) code ( w 1 ). U on code ( U ) code ( w 2 ) must emulate U on w 2 , as U is a universal machine. As U does not halt on w 2 and U is transparent, we must then have that U does not halt on code ( U ) code ( w 2 ). (4 marks) End of exam paper 7