past_exam_02

1. Complexity and Cryptography (7+6+3+4 = 20 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 1 3 2 2 5 5 3 7 10 4 9 17 5 11 26 6 13 37 7 15 50 8 17 65 9 19 82 10 21 101 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 = 20. (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 20 seconds on a machine 1000 times faster. (2 marks) (b) Let A and B be problems such that A can be reduced to B in polynomial time. What can you conclude from this if i. B ∈ P ? (1 mark) ii. A is NP-complete? (1 mark) iii. A is undecidable? (2 marks) iv. B is undecidable? (2 marks) (c) Briefly explain the difference between approximation, heuristic and probabilistic algorithms. (3 marks) (d) What is the key distribution problem? How is this overcome by public-key cryptosystems? (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 2 i b i | i ≥ 1 } (1 mark) ii. { a i b 2 i c 3 i | i ≥ 0 } (1 mark) iii. { a i b j c k | i, j, k ≥ 1 } (2 marks) iv. { a i b j c k | i ≥ k } (2 marks) v. { a i b j c k | i negationslash = k } ∪ { a i b j c k | j negationslash = k } (2 marks) vi. { a i b i + j c k | i, j, k ≥ 0 } (2 marks) (b) Which of the following statements is true? Briefly explain your answer. i. Non-deterministic Turing machines are more powerful than deterministic ones. (2 marks) ii. Non-deterministic PDAs are more powerful than deterministic ones. (2 marks) 1

iii. Regular expressions are more powerful than DFAs. (2 marks) iv. Context-sensitive grammars are more powerful than PDAs. (2 marks) v. Any finite language is regular. (2 marks) 3. Grammars (3+5+4 = 12 marks) Consider the grammar G below. S → aSb | A A → aA | B B → cBc | C C → aC | λ (a) Which of the strings aaabb , aacccacccbb and acacbb are derivable from G ? Briefly explain your answer (but there is no need to give full derivations). (3 marks) (b) Describe informally and in set notation the language of G . (5 marks) (c) Describe how the language of G changes if we change S to T and add the rule S → T | T S to G , making the grammar now S → T | T S T → aT b | A A → aA | B B → cBc | C C → aC | λ Compare this change to the one in which the rule A → aaA | λ is added to G (but the above changes are not made), making the grammar now S → aSb | A A → aA | B A → aaA | λ B → cBc | C C → aC | λ There is no need to write out the set notation for the new languages. (4 marks) 4. Grammars (8+3+3 = 14 marks) Consider the informal specification of a language below. • All Menu Planner programs commence with user(id) where id is an identifier, and conclude with stand , which may be optionally followed by either talk , or thanks , but not both. • Apart from the above constructs a Menu Planner program consists of an entree section , a main section , a dessert section , a cheese section and a coffee section , in that order. Only the main section is compulsory; all of the others are optional. • An entree section commences with nibbles , ends with gobbles and contains zero or more variable declarations . • A variable declaration is an identifier list followed by either salad, soup or savoury fol- lowed by ’;’. • An identifier list is either a single identifier or a number of identifiers separated by ’,’. • An identifier is a sequence of alphanumeric characters, including lower- and upper-case, com- mencing with a lower-case alphabetic character. • A main section commences with wash and optionally concludes with serviette and contains at least one main course . • A main course is one of – the keywords pasta chicken trout lentils rice – while boolean expression repeat main course stop – take away main course bag(identifier) • A boolean expression is either 2

Write the corresponding rule for MenuPlanner. You may assume that rules are already defined for Entree, Main, Dessert, Cheese, and Coffee and that none of these rules are of the form A → λ (i.e. there is no rule Entree → λ etc). (3 marks) 5. NFAs (3+3+2+6 = 14 marks) Consider the NFA below. q3 q0 0,1,2 q1 1 0,1,2 q2 1 1 0,1,2 (a) Which of the strings 000111, 1222122211 and 022221 are accepted by M ? (3 marks) (b) Describe informally the language L ( M ) of M . (3 marks) (c) How does the language of M change if the transition δ ( q 3 , λ, q 0 ) is added to M ? Briefly explain your answer. (2 marks) (d) Draw the state diagram for an NFA which accepts strings in { 0 , 1 , 2 } * in which either every third character is 2 or the string does not contain 00. For example, the strings 112002122, 002 and 222 should be accepted, but the string 00000 should not. (6 marks) 6. Chomsky Hierarchy) (5+2+2+4 = 13 marks) (a) Let L 1 = { ( aa ) i b i | i ≥ 0 } . Prove that there is no DFA for L 1 . (5 marks) (b) Let L 2 = { a i b j | i > j, j ≥ 0 } . Give a context-free grammar for L 2 . (2 marks) (c) Give an example of a string w such that w ∈ L 2 but w negationslash∈ L 1 . (2 marks) (d) Let L 3 = L 2 − L 1 (ie L 3 is all the strings in L 2 which are not in L 1 ). Is L 3 context-free? Briefly explain your answer. (4 marks) 7. Pushdown Automata (3+4+3 = 10 marks) Consider the pushdown automaton M below. q2 a-A,-A q0 a+A,b+B q1 c c b-B (a) Trace the execution of M with inputs aabcbcaa , aabcbca and abcbcaaa . (3 marks) (b) Describe the language of M in set notation and informally. (4 marks) (c) How does the language of M change if the transition from q 1 to q 2 is altered to be δ ( q 1 , e, e ) = ( q 2 , e ) and we add the transition δ ( q 2 , e, e ) = ( q 1 , e ) to M ? (where e denotes the empty string). The revised machine is given below. q2 a-A,-A q1 e q0 a+A,b+B c e b-B 4

Briefly explain your answer (but there is no need to give set notation for this language). (3 marks) 8. Turing machines (4+3+6+2+2 = 17 marks) Consider the Turing machine M below. q0 q1 BBR aaR,bbR,ccR q2 BBL q3 acL,caL q4 bbL acL,bbL,caL q5 BBR BBR acL,bbL,caL aaR,bBR,caR (a) Trace the computation of M with initial configuration q 0 Babbac . What is the outcome of the computation of M with the inputs q 0 Babbb and q 0 Bbbbba ? Briefly explain your answer (but 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 which given a string w over 0(0 ∪ 1) * will terminate with the binary representation of the result of adding 1 to w . For example, given the strings 0100 and 0011, your machine should terminate with outputs 0101 and 0100 respectively. You may use any notation for Turing machines and any variety of Turing machine that you wish. Note that you may also use other characters in the tape alphabet if you wish. (6 marks) (d) How difficult would it be to extend your machine to strings over (0 ∪ 1) * rather than just 0(0 ∪ 1) * ? Briefly explain your answer (but there is no need to give the extended machine). (2 marks) (e) How difficult would it be to extend your machine to add 2 to the string rather than 1? Briefly explain your answer (but there is no need to give the extended machine). (2 marks) End of exam paper 5