Computer Theory Final Assignment
Computing Theory COSC 1107/1105 Final Exercise Assessment Type Individual assignment. Submit online via Canvas → Assignments → End of semester exercise. Marks awarded for meeting requirements as closely as possible. Clarifications/updates may be made via announcements/relevant discussion forums. Due Date Thursday 3rd November 2022, 9.00am Marks 110 worth 50% of your final assessment 1 Overview This assessment requires you to demonstrate your knowledge of the key concepts in the course. Please note that this is an individual assessment; you are expected not to communicate with any other person in any way about this exercise for the entire duration of it. Any breach of this requirement may result in disciplinary action. 2 Assessment details 1. Consider the grammar derivations below. S ⇒ aSb ⇒ aaSbb ⇒ aaSbbb ⇒ aa0Abbb ⇒ aa00A1bbb ⇒ aa00cBd1bbb ⇒ aa00c23d1bbb S ⇒ 0A ⇒ 00A1 ⇒ 00B1 ⇒ 00cBd1 ⇒ 00c2C3d1 ⇒ 00c2dD3d1 ⇒ 00c2dd3d1 S ⇒ aSb ⇒ a0Ab ⇒ a0cBdb ⇒ a0c2Cdb ⇒ a0c22C3db ⇒ a0c22dD3db ⇒ a0c22de3db (a) From the above derivations, construct rules that must exist in any context-free grammar G for which these derivations are correct. (2 marks) (b) Assuming that these are all the rules in G, give L(G) in set notation. (3 marks) (c) Is G in Chomsky normal form? Briefly explain your answer. (2 marks) (d) What happens to L(G) if the rule B → dBc is added to G? Explain your answer. (3 marks) (e) Construct a context-free grammar for the language L2 below. (4 marks) L2 = {xi 0 w1 1 w2 2 yj | i ̸= 2j, i, j ≥ 0, |w1| = |w2|, w1 ∈ {a, b}∗, w2 ∈ {c, d}∗} (f) Can the language of a context-sensitive grammar be context-free? Explain your answer. (2 marks) (2+3+2+3+4+2 = 16 marks) 2. The following discussion was discovered in some ancient archives. There are at least 3 incorrect statements in the paragraph below. Identify all incorrect statements and justify each of your answers. (Each statement is numbered for easy identification.) 1. Decision problems are a class of problems for which the possible outcomes are only either ’yes’ or ’no’. 2. Examples of decision problems including primality testing, the Hamiltonian circuit problem, the Halting problem for Turing machines and the 3-colouring problem. 3. No matter what the decision problem may be, it is always possible to find an algorithm that solves it. 4. There some decision problems which although they can be solved in principle, in practice can be very difficult to solve. 5. These problems are often referred to as NP-complete problems, and include the Travelling Salesperson problem, 3-SAT, factorisation and vertex cover. 6. These problems are certainly intractable, i.e. all algorithms for these problems are known to have exponential running times. 7. This means that they can be solved for small instances, but the rate of growth of their complexity is so fast that they cannot be solved in practice for any reasonable size. 8. For example, the best known algorithm for the Travelling Salesperson problem can take up to 2n12 + 3n3 operations for a graph of size n. 9. This means it is in the class O(n12) and is thus intractable. 10. Fortunately it is possible to use approximation and heuristic algorithms to find some kind of solutions to these problems, either by removing the guarantee that an optimal solution will be found, or by removing the constraint that the running time will be polynomial or less (or removing both). 11. There are also some similar problems, such as the Hamiltonian circuit problem, which are known to be simpler to solve than the Travelling Salesperson problem and are tractable. 12. The name NP-complete problems comes from the property that such problems can be solved in at most polynomial-time on a nondeterministic Turing machine. 13. It is not known whether all NP-complete problems can be solved in at most polynomial-time on a deterministic Turing machine. 14. In order to disprove this, it would be sufficient to show that that one NP-complete problem cannot be solved in at most polynomial-time on a deterministic Turing machine. Note: A single sentence counts as one statement. (12 marks) 3. (a) Prove that the Empty Language problem is undecidable by reducing the Acceptance problem to it. Make sure that all of the details of the reduction are clearly specified. You may use a diagram to assist with this if you wish. (4 marks) (b) Prove that the Halting Problem is undecidable by reducing the Reachability Problem to the Halting Problem. Make sure that all of the details of the reduction are clearly specified. You may use a diagram to assist with this if you wish. Note: The classic way to prove the Reachability Problem is undecidable is to reduce the Halting Problem to it; this is asking for a reduction in the ’opposite’ direction. (6 marks) (c) The sun is expected to sputter out and die in about 8 billion years. Thomas and his friend Smaug are obsessed with the Platypus game, and are determined to play as large a tour- nament as possible in the time while the sun is still shining. Thomas prefers the 2-player 2 version, for which a tournament of n teams will take n(n + 1)/2 matches. Smaug prefers the 4-player version, for which a tournament of n teams will take n(n+ 1)(n+ 2)(n+ 3)/24 matches. Assuming that a 2-player match takes 0.002 seconds, and a 4-player match takes 0.015 seconds, calculate the size of the tournament that each can play in the time remaining before the sun dies. Explain your answer and include all relevant calculations. (4 marks) (d) Smaug is very disappointed with this result, and suggests that they compromise by focusing on the 3-player version, which are tournament of n teams will take n(n+1)(n+2)/6 matches. Thomas, who is about a million times smaller than Smaug, readily agrees. By enslaving an army of dwarves (who are excellent programmers), Smaug is able to reduce the time needed to play a 3-player game to 10−5 seconds. Calculate the size of the tournament that they can play in the time remaining before the sun dies. Explain your answer and include all relevant calculations. (2 marks) (4+6+4+2 = 16 marks) 4. (a) Construct a Turing machine M1 that accepts the reverse of your student number. The machine should only accept this one string; it should reject any string of length 6 or less, and any string of length 8 or more. The only string of length 7 which it should accept is the reverse of your student number. For example, if your student number is 7894321, M1 should accept only the string 1234987. (2 marks) (b) Which of the following machines could also be used to recognise the same language as L(M1)? Briefly justify each of your answers. (2 marks) A non-determinisitc PDA A deterministic PDA A non-deterministic finite state automaton (NFA) A deterministic finite state automaton (DFA) A linear-bounded automaton (c) Consider the following machine M2, where q2 is the first state of your machine M1 above (so the states q0 and q1 below are added to your M1, with machine constructed this way starting in q0). Explain why M2 on input xxxxxxx will always eventually terminate with success, no matter what your student number is. (4 marks) 3 (d) Given an input of xn (i.e. n consecutive x’s), calculate the maximum time it will take M2 to terminate, assuming that it can process 1 transition from the above machine in 4× 10−4 seconds. Show your working and explain your reasoning. Show your answers for n = 8, 12, 16 and 20 in the table below. Use the most appropriate units of time in each case. (4 marks) n Transitions Time 8 12 16 20 (2+2+4+4 = 12 marks) 5. Recall the game of Buckitch from Assignment 1, in which scores are kept in the following format. You may wish to refer to the Assignment 1 specification for background. D1D2M1M2Y1Y2Y3Y4H1H2WS1S2S3S4S5S6 where D1D2 are two digits of the day of the date M1M2 are two digits of the month of the date Y1Y2Y3Y4 are four digits of the year of the date H1 and H2 are the characters representing the two houses involved (one of c, d, l, s) W is the character for the winning house (one of c, d, l, s) S1S2S3 is the three-digit winning house’s score S4S5S6 is the three-digit losing house’s score The following constraints apply here. D1 ∈ {0, 1, 2, 3} M1 ∈ {0, 1} Y1 ∈ {1, 2} D2,M2, Y2, Y3, Y4, S1, S2, S4, S5 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} S3 = S6 = 0 (a) Construct a Turing machine M1 which given a string of any length over the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, c, d, l, s} performs as follows. (3 marks) If the string is not of length 17, the machine loops forever. If the string is of length 17 but is not formatted according to the above rules, the machine loops forever. Otherwise – If the winning house is Dragonbreath (d) or Serpentine (s) * each of the digits 5, 6, 8 and 9 is replaced with 7 4 * each of the digits 0, 2, 3 and 4 is replaced with 1 * each of the three houses (H1, H2, W ) is replaced with 7 * the machine terminates – If the winning house is Crowfoot (c) or Liongate (l) * each of the digits 0, 2, 3 and 4 is replaced with 7 * each of the digits 5, 6, 8 and 9 is replaced with 1 * each of the three houses (H1, H2, W ) is replaced with 1 * the machine terminates (b) Construct a Turing machineM2 which given a string of any length over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} performs as follows. (3 marks) If the number of 1’s is even and the number of 7’s is even, the machine loops forever. If the number of 1’s is odd and the number of 7’s is odd, the machine loops forever. If the number of 1’s is even and the number of 7’s is odd, the machine halts and rejects the string. If the number of 1’s is odd and the number of 7’s is even, the machine halts and accepts the string. (recall that 0 is an even number). (c) Consider the machine formed by combining M1 and M2 as above in sequence into a new machine M3, so that