COSC1107 Sample Final Assessment 2023

Computing Theory COSC 1107/1105 Sample Final Exercise 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 assessment for the entire duration of it. Any breach of this requirement may result in disciplinary action. 1. This is an OPEN NOTE assessment. This means you will be able to take in 1 A4 sheet of paper , on which you may make notes on both sides. Please note the following. You may bring in only one A4 sheet. You may write on both sides of the sheet. Your notes must be handwritten. You must write your own notes. Any breach of these conditions may be reported as academic misconduct. 2. Calculators are not allowed. 3. Bilingual dictionaries are allowed. 4. Electronic dictionaries are allowed. 5. You are expected to answer all parts of all questions. 6. If you do not understand what is required to answer a particular question, ask for clarification during the reading time. When asked to “briefly justify’ something, 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. 7. 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. 8. Write all answers in your answer booklet. Nothing written on the question paper will receive any marks. 9. Reading time will commence at 2.15pm. You may view the paper and ask questions, but no writing will be permitted at this time. 10. Writing time will commence at 2.30pm. 11. All work must be complete by 4.30pm.

You may find the following information helpful. Pumping Lemma for Regular Languages: Let L be a regular language. Then there is an integer n ≥ 1 such that for all strings w ∈ L such that | w | ≥ n , there exist strings x, y and z such that w = xyz and 1. | xy | ≤ n 2. y ̸ = λ 3. xy i z ∈ L for all i ≥ 0 Note that condition 2 is sometimes stated equivalently as length( y ) > 0. Pumping Lemma for Context-free Languages: Let L be a context-free language. Then there is an integer n ≥ 1 such that for all strings w ∈ L such that | w | ≥ n , there exist strings x, y, z, u and v such that w = xyzuv and 1. | yzu | ≤ n 2. y ̸ = λ or u ̸ = λ 3. xy i zu i v ∈ L for all i ≥ 0 Note that condition 2 is sometimes stated equivalently as length( y ) + length( v ) > 0, or that it is not the case that both y and v are λ . 2

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. 3. The generalised 3-player Platypus game is defined as follows. Let M 1 , M 2 , and M 3 be Turing machines, which share the same tape. The tape is initially blank. The initial configuration of the three machines is as shown below. As in the Platypus game, each machine takes turns to move (but there is no scoring involved). (a) Show that the halting problem for the 3-player generalised Platypus game (GPG) is unde- cidable. You may use any reduction you like. Hint: Reduce the Blank Tape problem to the halting problem for the GPG. In other words, assuming you have a machine to decide the halting problem for the GPG, use it to construct a machine to solve the Blank Tape problem. (b) Seedout, a rather adventurous and reckless hobbit, has proposed the reduction below as a way of showing the Empty Language problem is undecidable by reducing the Halting Problem to it. Unfortunately there are two errors in this reduction. Identify these errors, explain why these are incorrect and how they may be corrected. (4 marks) Seedout’s explanation is: “Assuming the Empty Language problem is decidable (and hence the existence of a Turing machine Empty which decides the problem), we can construct a solution to the Halting Problem as follows. First, given the Turing machine M and input w , we use these to construct another Turning machine M ′′ which deletes any input on the tape, writes w on the tape and then acts as M would. So the language accepted by M ′′ is empty iff M halts on w . See the diagram below for more details.” 4

(c) Suppose the GPG is played on a Turing machine with a finite tape (making the halting problem decidable), and that this problem has been shown to be NP-complete. Given your above reduction from some problem A to the GPG, can this reduction be used to conclude that A is NP-complete? Why or why not? Explain your answer. 4. (a) Consider the PDA M 1 below. Express L ( M 1 ) in set notation. Justify your answer. (b) Is there a finite state automaton (either nondeterministic or deterministic) for L ( M 1 )? Justify your answer. Note: there is no need to give either a specific automaton or a proof that no such automaton exists; an informal argument will suffice. (c) Consider the language L 2 = { 4 i 3 j 2 k 1 2 i | j ̸ = k, i, j, k ≥ 0 , } Is there a PDA for L 2 ? Justify your answer. 5

In each case, justify your answer. (d) Consider now the machine M 5 , which is the same as M 2 except that rather than determinis- tically replacing digits in the input string, it nondeterministically replaces each digit either as in M 2 above or with 7. This means that for the transitions from q 1 to q 2 we add the transitions 0; 7 , L , 1; 7 , L , 2; 7 , L , ... 9; 7 , L , to M 1 , and similarly for transitions from q 2 to q 3 and q 3 to q 4 . The same technique as above is used to combine M 5 and M 2 into a new machine M 6 . For which inputs over { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } does M 6 halt with rejection? For which inputs over { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } does M 6 halt with acceptance? For which inputs over { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } does M 6 not halt? In each case, justify your answer. 6. (a) Prove that the language L 4 = { a i b j c j d i | i ≥ 0 } is not regular. Use the string a n b n +1 c n +1 d n at an appropriate point in the proof. (b) Suppose that someone else were to prove the same result using the string b 2 n c 2 n and i = 3. In this second proof, which steps would be different? Which steps remain the same? Note: there is no need to write out the second proof; just specify clearly which steps would need to change. (c) There are some errors in the proof below that the language L 5 = { s # s R @ s | s ∈ { a, b, c } ∗ } is not context-free. Find and correct all such errors. Note: there is no need to write out the full corrected proof; just clearly specify the necessary corrections. Claim: The language L 5 = { s # s R @ s | s ∈ { a, b, c } ∗ } is not context-free. Proof: Assume L 5 is regular. Then the Pumping Lemma applies and so for some n ≥ 1 such that for some w ∈ L such that | w | ≥ n , w = xyzuv where | yzu | ≤ n y ̸ = λ and u ̸ = λ xy i zu i v ∈ L for all i ≥ 0 Choose w = a n b n c n # c n b n a n @ a n b n c n and so w ∈ L and | w | ≥ n . So by the Pumping Lemma w = xyzuv = a n b n c n # c n b n a n @ a n b n c n and | yzu | < n . This means that y and u can contain at most two of a , b and c and possibly up to one occurrence each of # and @. We will refer to the part of the string before # as zone 1 , the part of the string between # and @ as zone 2 , and the part of the string after @ as zone 3 . Now if y or u contains # or @, then clearly xy 2 zu 2 v ̸∈ L , as this would contain two occur- rences of either # or @. Hence neither u nor v contains either # or @. Now note that both y and u can only cover at most two of zone 1 , zone 2 , and zone 3 , as | yzu | ≤ n . This means that xy 2 zu 2 v ∈ L , as one of the zones will have the same string as w , but the other two will have longer strings, and hence xy 2 zu 2 v is not of the form s # s R @ s . This is a contradiction, and so L 5 is not context-free. 7. Trusty Teddy, having despaired of making any money out of snake oil, has decided to make a move into sideshows. Having heard about the wonders of Turing machines, Teddy wants to design a sideshow game as follows. A customer, having paid an exorbitant entry fee, will be able to input a 7

Turing machine of their choice into the game instrument. Then a “random” wheel is spun, which chooses a particular state s in the machine. Teddy then announces that the customer will win a grand prize if the machine enters this state on a secret input supplied by Teddy. The machine is then executed on this input, with the customer winning if the machine enters state s , and Teddy winning otherwise. Teddy is of course no fool, and he wants the game to work in the following way. He always supplies the same input to any machine, and of course he wants to make sure that he never has to give out a grand prize. So he asks you, as an expert on Turing machines, to ensure that whatever machine is supplied by the customer, the “randomly” chosen state is actually quite specifically chosen to be one that is never entered by the machine when run on Teddy’s input, thus ensuring that Teddy will never have to give out a grand prize. Teddy is prepared to supply you with whatever computing power may be needed to find the answer. (a) Explain why Teddy’s scheme will never work, no matter how much computing power is used. (b) Teddy then learns some more about Turing machines, and then asks you whether it will help if the input that he supplied is also a Turing machine (and Teddy particularly likes universal Turing machines). Explain why this will be no help. (c) Suggest at least one way in which Teddy can accomplish something like his original idea by an appropriate relaxation of his policy. Explain your answer. (d) Teddy, never one to give up when an obstacle is found, takes your advice on board, and having thought about it some more, asks you if the following variation will have a different outcome. Instead of using a fixed input for every machine, Teddy’s new proposal is that the “random” wheel not only chooses a specific state, but also chooses a specific input. This input will, of course, be similarly carefully chosen to ensure that when the customer’s machine is run on this input, the chosen state is never reached. Does this change your analysis of Teddy’s game? Explain your answer. 8