past_exam_02-solutions

pdf

School

Royal Melbourne Institute of Technology *

*We aren’t endorsed by this school

Course

1107

Subject

Computer Science

Date

Oct 30, 2023

Type

pdf

Pages

Uploaded by ChefLionPerson918

COSC 1105/7 COMPUTING THEORY EXAM SOLUTIONS 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) Answer: Program 1 has complexity 2 n + 1 and hence is tractable. Program 2 has complexity n 2 + 1 and hence is tractable. ii. Calculate the time required for Program 1 for n = 20. (1 mark) Answer: 2 × 20 + 1 = 41 seconds. iii. Calculate the value of n for which Program 1 executes in the same time that Program 2 takes for n = 10. (2 marks) Answer: We want 2 n + 1 = 101, ie that n = 50. iv. Calculate the largest value of n for which Program 2 executes in under 20 seconds on a machine 1000 times faster. (2 marks) Answer: We want n 2 + 1 < 20 , 000, ie n < 141 . 5. Hence the largest value is 141. Unsimplified form is fine. (b) Let A and B be problems such that A can be reduced to B in polynomial time. What can you conclude from this for each of the cases below. Briefly explain your answer. i. B ∈P Answer: A ∈P (1 mark) ii. A is NP-complete Answer: B is NP-complete (1 mark) iii. A is undecidable Answer: B is undecidable (2 marks) iv. B is undecidable Answer: Nothing (2 marks) (c) Briefly explain the difference between approximation, heuristic and probabilistic algorithms. (3 marks) Answer: Approximation algorithms find a solution to a simpler problem than the original one. Probabilistic algorithms find a solution to the original problem which is only probably correct. Heuristic algorithms generally find an efficient solution to the original problem, but their performance cannot be guaranteed. (d) What is the key distribution problem? How is this overcome by public-key cryptosystems? (4 marks) Answer: Any secret key cryptosystem requires a secure means to distribute the key, which must be kept secret. Hence there is a bootstrapping problem. A public-key system separates the encryption key from the decryption one, and hence the encryption key can be made public. 2. Chomsky Hierarchy (10+10 = 20 marks) 1

(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 } Answer: context-free but not regular (1 mark) ii. { a i b 2 i c 3 i | i ≥ 0 } Answer: recursively enumerable but not context-free (1 mark) iii. { a i b j c k | i, j, k ≥ 1 } Answer: regular (2 marks) iv. { a i b j c k | i ≥ k } Answer: context-free but not regular (2 marks) v. { a i b j c k | i negationslash = k }∪{ a i b j c k | j negationslash = k } Answer: context-free but not regular (2 marks) vi. { a i b i + j c k | 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. Non-deterministic Turing machines are more powerful than deterministic ones. (2 marks) Answer: False. A non-deterministic Turing machine can always be converted into an equivalent deterministic one. ii. Non-deterministic PDAs are more powerful than deterministic ones. (2 marks) Answer: True. It is not always possible to convert a non-deterministic PDA into an equivalent deterministic one. iii. Regular expressions are more powerful than DFAs. (2 marks) Answer: False. Regular expressions are equivalent in power to NFAs, and for any NFA there is an equivalent DFA. iv. Context-sensitive grammars are more powerful than PDAs. (2 marks) Answer: True. Context-sensitive grammars are equivalent to LBAs, which are more powerful than PDAs. v. Any finite language is regular. (2 marks) Answer: True. There is an NFA for any string, and we can combine a finite number of these into a single NFA. 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) Answer: S ⇒ * aaAbb ⇒ aaaAbb ⇒ * aaabb derivable. S ⇒ * aaBbb ⇒ * aacccCcccbb ⇒ aacccacccbb derivable. S ⇒ aSb ⇒ aaSbb not derivable. (b) Describe informally and in set notation the language of G . (5 marks) Answer: { a i a j c k a l c k b i | i, j, k, l ≥ 0 } (c) Describe how the language of G changes if we change S to T and add the rule S → T | TS to G , making the grammar now S → T | TS T → aTb | A A → aA | B B → cBc | C C → aC | λ 2

Compare this change to the one in which the rule A ← aaA | λ is added to G (but the above changes are not made). There is no need to write out the set notation for the new languages. (4 marks) Answer: For the first change, we get the same kinds of strings, but repeatedly. In other words, if w 1 and w 2 are in the original language, then the string w 1 w 2 is in the new one. For the second change, the language is the same as the original one, as anything we can derive from A with the previous grammar can also be derived with this new one. From the original grammar we can get A ⇒ aA ⇒ aaA and A ⇒ B ⇒ C ⇒ λ . 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 – an identifier – of the form identifier comparison operator numerical expression – of the form boolean expression binary operator boolean expression – of the form unary operator boolean expression • A numerical expression is either – an identifier – a natural number – of the form numerical expression numerical operator numerical expression • A comparison operator is one of =, = > and < =. • A numerical operator is one of +, -, *, /. • A binary operator is one of <> , >< and = > =. • A unary operator is one of @ and %. • A dessert section begins with yummies , ends with full and contains one or two of the following keywords (repeats allowed): ice cream mousse pancakes fruit salad chocolate frogs jelly 3

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

• A cheese section commences with mouse , optionally ends with esuom and contains exactly three of the following keywords (repeats allowed): cheddar edam camembert brie swiss gorgonzola parmesan ricotta blue optionally followed by a single statement of the form repeat dessert section and cheese section until boolean expression • A coffee section begins with drinks , ends with satisfaction and contains exactly one of the following keywords: cappuccino latte short black devonshire tea Assume that rules have already been given for VariableDeclaration, Identifier, BooleanExpression, and all of the tokens and reserved words mentioned above (e.g. pasta, mousse, cappuccino, ... ). (a) Complete the following grammar for Menu Planner programs (i.e. write the grammar rules for Main, Dessert and Cheese). You do not need to worry about whitespace. MenuPlanner → user(Identifier) Entree Main Dessert Cheese Coffee stand MenuEnd MenuEnd → talk | thanks | λ Entree → nibbles VariableDeclaration gobbles | λ Main → ... Dessert → ... Cheese → ... Coffee → drinks CoffeeType satisfaction CoffeeType → cappuccino | latte | short black | devonshire tea (8 marks) Answer: Main → wash MainMeal MainEnd MainMeal → MainCourse | MainCourse MainMeal MainEnd → serviette | λ MainCourse → pasta | chicken | trout | lentils | rice | while BooleanExpression repeat MainCourse stop | take away MainCourse bad(Identifier) Dessert → yummies DessertType full | yummies DessertType DessertType full DessertType → ice cream | mousse | pancakes | fruit salad | chocolate frogs | jelly Cheese → mouse CheeseType CheeseType CheeseType CheeseOption CheeseEnd CheeseEnd → esuom | λ CheeseType → cheddar | edam | camembert | brie | swiss | gorgonzola | parmesan | ricotta | blue CheeseOption → repeat Dessert and Cheese until BooleanExpression | λ (b) Consider the following change to the second bullet point in the above specification of Menu Planner programs: “Apart from the above constructs a Menu Planner program consists of an entree section and a main section , followed by any two of a dessert section , a cheese section and a coffee section , in any order. The main section must not be empty; any of the others may be empty.” 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) Answer: MenuPlanner → user(Identifier) Entree Main Choice Choice stand MenuEnd Choice → Dessert | Cheese | Coffee | λ (c) Consider the following change to the second bullet point in the above specification of Menu Planner programs: 4

“Apart from the above constructs a Menu Planner program consists of either a main section followed by one or more coffee sections , or a dessert section followed by a cheese section followed by one or more coffee sections . None of these may be empty.” 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) Answer: MenuPlanner → user(Identifier) MenuMain stand MenuEnd MenuMain → Main Coffees | Dessert Cheese Coffees Coffees → Coffee | Coffee Coffees 5. NFAs (3+3+2+6 = 14 marks) Consider the NFA below. q3 q0 012 q1 1 012 q2 1 1 012 (a) Which of the strings 000111, 1222122211 and 022221 are accepted by M ? (3 marks) Answer: 000111 and 1222122211 accepted. 022221 is rejected. (b) Describe informally the language L ( M ) of M . (3 marks) Answer: Strings over { 0 , 1 , 2 } which contain at least three 1’s and finish with a 1. (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) Answer: It doesn’t change at all, as the strings still have to contain at least three 1’s, and still have to finish with 1. (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) Answer: q1 q2 012 q4 12 q5 0 12 q6 0 q0 e e q3 012 2 012 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) 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 negationslash = λ , | xy |≤ k and xy i z ∈ L 1 ∀ i ≥ 0. Let w = ( aa ) k b k . 5

As | w | > k , the Pumping Lemma applies and so we have xyz = ( aa ) k b 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 = ( aa ) k a m b k , and so xy 2 z negationslash∈ L 1 , which is a contradiction. (b) Let L 2 = { a i b j | i > j, j ≥ 0 } . Give a context-free grammar for L 2 . (2 marks) Answer: S → aSb | aS | a (c) Give an example of a string w such that w ∈ L 2 but w negationslash∈ L 1 . (2 marks) Answer: aaab ∈ L 2 but aaab negationslash∈ L 1 . (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) Answer: A string w ∈ L 2 − L 1 is of the form a i b j where i > j as w ∈ L 2 . As w negationslash∈ L 1 , we must have that i negationslash = 2 j . Hence we have either 2 j > i > j or i ≥ 2 j + 1. There is certainly a context-free grammar for the latter case. Hence if we can find one for the former case, then L 2 − L 1 is also context-free. 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) Answer: ( q 0 , aabcbcaa, e ) ⊢ ( q 0 , abcbcaa, A ) ⊢ ( q 0 , bcbcaa, AA ) ⊢ ( q 0 , cbcaa, BAA ) ⊢ ( q 1 , bcaa, BAA ) ⊢ ( q 1 , caa, AA ) ⊢ ( q 2 , aa, AA ) ⊢ ( q 2 , a, A ) ⊢ ( q 2 , e, e ) Accepted. ( q 0 , aabcbca, e ) ⊢ ( q 0 , abcbca, A ) ⊢ ( q 0 , bcbca, AA ) ⊢ ( q 0 , cbca, BAA ) ⊢ ( q 1 , bca, BAA ) ⊢ ( q 1 , ca, AA ) ⊢ ( q 2 , a, AA ) ⊢ ( q 2 , e, A ) ⊢ ( q 2 , e, e ) Accepted. ( q 0 , abcbcaaa, e ) ⊢ ( q 0 , bcbcaaa, A ) ⊢ ( q 0 , cbcaaa, BA ) ⊢ ( q 1 , bcaaa, BA ) ⊢ ( q 1 , caaa, A ) ⊢ ( q 2 , aaa, A ) ⊢ ( q 2 , aa, e ) Rejected. 6

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

(b) Describe the language of M in set notation and informally. (4 marks) Answer: { a i b j cb j ca k | i ≥ k, i, j, k ≥ 0 } . This is the set of strings beginning with a number of a ’s followed by a number of b ’s followed by a single c then the same number of b ’s as before then another single c and finally no more a ’s than in the first part of the string. (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 Briefly explain your answer (but there is no need to give set notation for this language). (3 marks) Answer: Strings in L ( M ) are now of the form w 1 cw 2 where w 1 , w 2 ∈{ a, b } * , n a ( w 2 ) ≤ n a ( w 1 ) and n b ( w 2 ) = n a ( w 1 ). In other words, there must be the same number of b ’s on either side of the c , but no more on the right than there are on the left. To see this, note that there is now no order constraint on how the stack may be emptied, and so any string over { a, b } * will fill up the stack. However, we empty the stack in the reverse order to the input. Without the − A transition, this would mean that w 2 = w R 1 . With this extra transition, we can arbitrarily omit a ’s from w 2 . Hence w 2 can be best specified as w R 1 with an arbitrary number of a ’s deleted. 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) Answer: q 0 Babbac ⊢ Bq 1 abbac ⊢ Baq 1 bbac ⊢ Babq 1 bac ⊢ 7

Babbq 1 ac ⊢ Babbaq 1 c ⊢ Babbacq 1 B ⊢ Babbaq 2 c ⊢ Babbq 3 aa ⊢ Babq 3 bca ⊢ Baq 3 bbca ⊢ Bq 3 abbca ⊢ q 3 Bcbbca ⊢ Bq 5 cbbca ⊢ Baq 5 bbca ⊢ BaBq 5 bca ⊢ BaBBq 5 ca ⊢ BaBBaq 5 a ⊢ BaBBaaq 5 B ⊢ For abbb , the machine will move to the end and then move backwards through the string, converting the a to c and then go into an infinite loop, repeatedly exchanging a ’s and c ’s. For bbbba , the machine will convert all the b ’s to blanks and then terminate (after converting the a to c and then back to a again). (b) Describe informally the result of a computation in M . (3 marks) Answer: If the string ends in a or c , it will convert all the c ’s to a ’s and all the b ’s to blanks and then terminate. If the string ends in b , it will loop forever. (c) Give a Turing machine which given a string w over 0(0 ∪ 1) * (i.e. binary strings which commence with 0) 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) Answer: q0 q1 BBR 00R,11R q2 BBL q3 01L q4 10L 10L q5 01L (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) Answer: This would require potentially shifting the entire tape one place to the right. For example, given the input 1111, the result of the addition is 10000, which is one digit longer. (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) Answer: This is quite simple. Rather than commence from the final digit, we move one place to the left, and proceed as above. To see this consider adding 2 (which in binary is 10) to the strings 0101 and 0100, for which we get 0111 and 0110 respectively. End of exam paper 8