past_exam_05-solutions only

RMIT School of Computer Science and Information Technology 2005 COSC1105/1107 COMPUTING THEORY EXAM DATE: 14th June TIME ALLOWED: 2 hours TIME: 2.00pm - 4.00pm NUMBER OF PAGES: 4 TOTAL NUMBER OF MARKS: 100 • 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. • 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. The pumping lemma asserts that there is a p such that for all w ∈ L with | w |≥ p then w = xyz , | xy |≤ p , | y | > 0 and xy i z ∈ L for all i ≥ 0.

1. Complexity and Cryptography (4+3+4 = 11 marks) (a) Briefly explain the terms tractable , intractable and undecidable , then briefly explain which of those classes the Travelling Salesrep problem belongs to. Answer: tractable: a problem which has a solution in polynomial time Answer: intractable: a problem where all solutions are exponential or worse Answer: undecidable: a problem for which there is no algorithm Answer: Travelling salesrep is intractable because there is an algorithm but it doesn’t run in polynomial time (b) Are all intractable problems in the class NP? Briefly explain why or why not. Answer: No. For NP problems, each candidate ’solution’ can be checked in polynomial time. Not all intractable problems have this property (c) Which of the following properties are possessed by RSA? (Answer true or false ) i. Messages can be signed by the sender ii. Releasing the encryption key would compromise RSA security iii. Encryption and decryption can be performed in any order iv. RSA relies on prime number generation being intractable Answer: true, false, true, false 2. Chomsky Hierarchy (6+3+8 = 17 marks) (a) Classify the languages below as either • regular • context-free but not regular • recursively enumerable but not context-free i. { a i b j c i | i ≥ j } Answer: recursively enumerable but not context-free ii. { a i b j c j d i | i, j ≥ 1 } Answer: context-free but not regular iii. { ab 2 i | i ≥ 1 } Answer: regular iv. { w ∈ { a, b } * | w contains twice as many a s as b s } Answer: context-free but not regular (b) Which of the following statements is true? Briefly explain your answer. i. Unrestricted grammars are more powerful than deterministic Turing machines. Answer: False. They are equivalent ii. Context-free grammars are less powerful than pushdown automata. Answer: False. They are equivalent iii. Regular expressions are more powerful than context-free grammars. Answer: False, reg- ular expressions are less powerful than CFG (c) Prove there is no FSA for { a i b j | i < j } Answer: If there was a FSA, then the language would be regular. The pumping lemma says for w ∈ L there is a p where w = xyz , | xy |≤ p , | y | > 0 and xy i z ∈ L for all i ≥ 0. Consider s = a p b p +1 . The pumping lemma says s can be broken into xyz with | y | > 0. This means y y consists of only a s. Pumping y will result in too many a s. 1

4. NFAs (3+4+7+6 = 20 marks) (a) Consider the NFA M below: a > a b q2 q3 q1 a b q4 b e i. Which of the strings abbabbab , abaaba and baaa are accepted by M ? Answer: abbabbab accepted, abaaba rejected, baaa accepted ii. Give a regular expression for the language L ( M ) of M . Answer: ab * a ( bb * a ) * ba * U ( bb * a ) ba * iii. Give a DFA for the language of M . Answer: state a b 13 2 24 2 3 2 3 F 24 24 34 2 34 4 24 4 4 F F F F a b a b a 13 24 34 4 F 3 2 a a b > a,b a b b b (b) Draw the state diagram for an NFA over the alphabet { a, b } which recognises strings: • starting with ab and ending with ba , or • alternating a s and b s For example abaababa , abab and baba are in the language, but abb and baab are not. 3

> b a e b a a,b b a e e e e a b 5. Pushdown automata (5+6+5 = 16 marks) Consider the pushdown automaton M below. The initial state is q 0 . Q = { q 0 , q 1 , q 2 , q 3 } δ ( q 0 , a, λ ) = { ( q 0 , A ) } δ ( q 2 , b, λ ) = { ( q 2 , B ) } Σ = { a, b, c } δ ( q 0 , b, A ) = { ( q 1 , λ ) } δ ( q 2 , c, B ) = { ( q 3 , λ ) } Γ = { A, B } δ ( q 1 , b, A ) = { ( q 1 , λ ) } δ ( q 3 , c, B ) = ( q 3 , λ ) F = { q 3 } δ ( q 1 , b, λ ) = { ( q 2 , B ) } (a) Trace the execution of M with inputs aabbbbbccc . Answer: ( q 0 , aabbbbbccc, λ ) ‘ ( q 0 , abbbbbccc, A ) ‘ ( q 0 , bbbbbccc, AA ) ‘ ( q 1 , bbbbccc, A ) ‘ ( q 1 , bbbccc, λ ) ‘ ( q 2 , bbccc, B ) ‘ ( q 2 , bccc, BB ) ‘ ( q 2 , ccc, BBB ) ‘ ( q 3 , cc, BB ) ‘ ( q 3 , c, B ) ‘ ( q 3 , λ, λ ) (b) Describe M in set notation. Answer: { a i b i + j c j | i, j ≥ 1 } (c) Give a context-free grammar for the language of M . Answer: S → AB A → aAb | ab B → bBc | bc 6. Turing Machines (5+5 = 10 marks) Consider the Turing machine M below. δ B 0 1 q 0 q 1 , B, R q 1 halt q 2 , 1 , R q 1 , 0 , R q 2 q 3 , B, L q 2 , 1 , R q 2 , 1 , R q 3 halt q 2 , 0 , R q 3 , 1 , L 4