1 Overview
Computing Theory COSC 1107/1105 Sample Exercise 2
This is mock version of the final exercise. The final exercise will be similar, but of course will not be exactly the same. Therefore treat this as a guide, not as a precise specification. I haven’t included marks for each question here.
Solutions will be available shortly. I strongly suggest you attempt these before you have access to the solutions; otherwise it is not a completely realistic practice for the final exercise, and it is all too easy to believe that you know how to find the answer when it is easily available to you.
2
Assessment details
1. Consider the grammar derivations below.
S ⇒ aSb ⇒ aaSbb ⇒ aacSdbb ⇒ aacdbb
S ⇒ A ⇒ xAy ⇒ xxAyy ⇒ ⇒ ⇒ S ⇒ A ⇒ @C ⇒ @Cy ⇒ @Cyy ⇒ @yyy
(a) From the above derivations, construct rules that must exist in any context-free grammar G for which these derivations are correct.
(b) Assuming that these are all the rules in G, give L(G) in set notation.
(c) Is there a regular grammar for L(G)? Explain your answer.
(d) Construct a context-free grammar for the language below.
L = {xi yj | i ̸= 2j,i,j ≥ 0,|w1| = |w2|,w1 ∈ {a,c}∗,w2 ∈ {b,d}∗}
2. Drogo the Dreary, a distant relative of , has written the following discussion of intractability. There are 5 incorrect statements in the paragraph below. Identify all 5 incorrect statements and justify each of your answers.
“There are a number of problems which can be solved in principle, but in practice can be very difficult to solve. These problems are often referred to as NP-complete problems, and include the Travelling Salesperson problem, 3-SAT, factorisation and vertex cover. These problems are certainly intractable, i.e. all algorithms for these problems have exponential running times. 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. For example, the best known algorithm for the Travelling Salesperson problem can take up to 2n10 + 7n2 operations for a graph of size n. This means it is in the class O(n10) and is thus intractable. 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). 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. The name NP-complete problems comes from the property that such problems have run in at most polynomial-time on a nondeterministic Turing machine.”
3. The generalised Platypus game with Gandalf the White is played as follows (we will abbreviate the name of this to GPGGW). There are three machines, with two being the usual platypus machines (as in the generalised Platypus game from Assignment 2), with the third machine being Gandalf the White, which has the transition table as below. For simplicity we assume all three machines have the same alphabet Σ. The tape is infinite in both directions, and is initially blank.
q0 blank blank R q1 q0 X X R q1 q1 blank blank L q0 q1 X X L q0
where X denotes any non-blank symbol in Σ.
(a) Show that the halting problem for the GPGGW is undecidable. You may use any reduction you like. Note that you may assume that the generalised Platypus problem from Assignment 2 is undecidable if you would find that helpful.
(b) Suppose the GPGGW is played on a Turing machine with a finite tape (making the halting problem decidable), and also that there is a decidable problem A for which there is a reduction from A to the GPGGW. This information could be used as an argument that the GPGGW is NP-complete, provided that some further information is known. What further information is needed? Explain your answer.
(c) Freddo the optimistic Frog likes playing Platypus tournaments. He particularly likes the 3- player version, for which a tournament of n machines will require n(n + 1)(n + 2)/6 matches. He ran a tournament for 100 machines which took 42.42 seconds on the family desktop computer. Encouraged with his success, he attempts to run a tournament with 10,000 machines, but when it was discovered the computer took well over a day without coming close to finishing, he was given a strict limit of 8 hours for all such tournament play (so that tournaments could be run at night when all the other frogs were asleep). What is the largest tournament size that Freddo can play within this limit? Show your working. We will call this number n1.
(d) Having despaired of realising his dream of a complete 3-player tournament, Freddo hears of a similar tournament game, known as Krazy Koalas. His friend Choco tells him that he can also run a 100-machine tournament in 42.42 seconds, but the Koala tournament “only” requires n6/(1000000) matches. Given Freddo’s time limit of 8 hours, what is the largest Koala tournament he can run? Show your working. We will call this number n2.
(e) Freddo, being an optimist, decides he wants to investigate the two types of tournament a little further. Given he knows it takes just under 8 hours to run a Platypus tournament with n1 machines and a Koala tournament of n2 machines, how long will it take to run a Platypus tournament with n2 machines? And how long will it take to run a Koala tournament with n1 machines? Show your working in each case.
(f) Freddo’s activities attract the attention of a spambot (secretly installed on the family desk- top), and gets an unsolicited offer from Hammy Spam Solutions to provide a host server for running his tournaments, at a cost of $(1.01)n for a Platypus tournament of n machines, where n could be as high as 10,000. After a small amount of thought, Freddo deletes the offer and tells all his family and friends to avoid Hammy Spam Solutions at all times. Explain
2
4. (a)
why Freddo did this, with particular reference to the cost for a tournaments involving 100, 1,000 and 10,000 machines.
Construct a Turing machine M1 which recognises your student number. This machine should accept only your student number; 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 your student number.
(b) Which of the following machines could also be used to recognise your student number, as above? Briefly justify each of your answers.
A non-deterministic 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.
(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 3 × 10−5 seconds. Show your working and explain your reasoning.
Show your answers for n = 7,10,15 and 20 in the table below. Use the most appropriate units of time in each case.
n Transitions Time 7
10
15
20
3
5. (a)
(b)
Construct a Turing machine which given a seven-digit number as input, deletes the first digit (whatever it is) and replaces the remaining six digits with their value modulo 3 (i.e. the remainder when divided by 3, or if x is a digit, the value of x mod 3). For example, given the input 7654321, the machine write a blank over the 7, and leave the string 021021 on the tape after terminating. The machine must terminate on all strings over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}∗ (including the empty string), and only halt in an accepting state if the string has exactly 7 digits.
Construct a Turing machine M3 which takes a string of digits over {0, 1, 2} with length at least 3 as input, and halts in an accepting state with w#wR on the tape, where w is the input string and wR is the reverse of the string w. If the input string w is of length 2 or less, the machine must halt in a non-accepting state and leave w on the tape. This means that the machine must halt on all inputs. Some example inputs and outputs are below.
Input Output Halt state
1211 1211#1121 accepting 22001 22001#10022 accepting
1 1 non-accepting 20 20 non-accepting
Describe how to use the machine M3 from the question above to construct a machine which string of digits over {0, 1, 2} with length at least 3 as input, and halts in an accepting state with on the tape, where w is the input string and wR is the reverse of the string w. As above, if the input string w is of length 2 or less, the machine must halt in a non-accepting state and leave w on the tape.
Naturally you could write this machine from scratch, but that answer is not appropriate here.
Your answer should describe how you can reuse M3 as much as possible (which might include copying a section of the machine and making some minor changes to it). You do not have to explicitly construct the new machine; your answer should describe the process to generate this new machine from the previous one.
Describe how to use the machine M3 from the question above to construct a machine which recognises strings of the form w#wR where w is a string of length at least 3 over {0, 1, 2}. If w has length 2 or less then the string should be rejected. This machine must halt for all inputs.
Input Accept?
1211#1121 yes 22001#10022 yes 1 no 20 no 1211#1211 no 02011#1111 no
Again, your answer should describe how you can reuse M3 as much as possible.
Prove that the language L1 = {w#wR | w ∈ {0, 1, 2}∗} is not regular by using the Pumping
Lemma. Use the string 1n2 at an appropriate point in the proof.
Write out the proof of the same result which uses the string 2n12n and i = 3 instead. Which
steps are different? Which steps remain the same? 4
6. (a) (b)
(c)
(d)
(c) Give a PDA for the language L1 = {w#wR | w ∈ {0, 1, 2}∗}. Is your machine deterministic or non-deterministic? Briefly explain your answer.
(d) Is there a context-free grammar for the language L2 = | w ∈ {0, 1, 2}∗}? Explain your answer.
(e) The language L3 = {01s#s10 | s ∈ {0, 1, 2}} is regular. Construct a finite state automa- ton which accepts L3 (and only L3). Your machine can be either deterministic or non- deterministic.
(f) The language L4 = {w#wR | w ∈ {0, 1, 2}∗, |w| ≤ 3} is also regular. If you were to extend your previous machine to accept this language, how many transitions would you need? In other words, if there are k transitions in your machine for L3, give a formula for your estimated number of transitions required in the machine for L4.
(g) Give a context-free grammar for L3 with at most 4 rules. The number of rules is the number of different right-hand sides in the grammar; for example, the grammar below has 6 rules (3 for S, 2 for A and 1 for B).
S → aA|Aa|a A → aBaa|Baa B → abc
7. Snivelling Sam the Shonky Snake Oil Salesman hears about your work on Turing machines, and is so impressed that he commissions you to extend M to a machine N by extending the language of the input string from {0, 1, 2}∗ to {a − z, A − Z, 0 − 9}∗. Naturally extending M to N is trivial for you. Sam also wants to license N from you for use in his pet project, which is a personalised cloud-based Turing machine service. His idea is to get a customer to send him a Turing machine C, which will take as input the blank tape and output a specific string w. The machine C will then be prepended to your machine N, and then the combined machine Sam(C,N) will be run, which will take the blank tape as input, run C on the blank tape producing w, and then run N on w producing w#wR, which Sam then digitally frames in an artistic manner and sells to the customer for megabucks. You may assume that in the machine Sam(C,N) the final state of C is the same as q0, the initial state of N, and that whenever N is run in this fashion, the first configuration available to N in the combined machine will be q0w where w is the string output by C. Naturally Sam asks you to ensure that N will terminate no matter what input it is given, and once you have assured him of that, Sam boasts that he will guarantee to his customers that they will either get their output as promised, or will have their machine C returned to them with the message “Your machine does not terminate” (and that the latter will only happen when C does not terminate on the blank input).
(a) Explain why Sam’s idea, as specified above, will not work, no matter how much sophisticated computer technology he has at his disposal.
(b) Suggest one way that Sam could achieve something along these lines by giving a less strong guarantee about the performance of C.
3 Submission
You should submit PDF file containing your answers to the questions. You may generate this PDF file in any manner that suits you (such as word processors, scanning handwritten notes, or a combination of these).
5