1
Assessment details
Computing Theory COSC 1107/1105 Sample Exercise 2 Answers
1. Consider the grammar derivations below.
S ⇒ aSb ⇒ aaSbb ⇒ aacSdbb ⇒ aacdbb
S ⇒ A ⇒ xAy ⇒ xxAyy ⇒ xxB@yy ⇒ xxxB@yy ⇒ xxxx@yy 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.
Answer: From the first derivation we can see that the rules must include S → aSb, S→cSdandS→λ. FromthesecondderivationwecanaddtherulesS→A,A→xAy, A→B@,B→xBandB→x. FromthethirdderivationwecanaddtherulesA→@C, C → Cy and C → y.
As this covers all the derivation steps in all three derivations above, we get the rules below.
S → aSb | cSd | A | λ A → xAy | B@ | @C B → xB | x
C → Cy | y
(b) Assuming that these are all the rules in G, give L(G) in set notation.
Answer: L(G) = {wxi@yj(bd(w))Rorw(bd(w))R | i ̸= j,i,j ≥ 0,w ∈ {a,c}∗} where bd(w)
is w with all a’s replaced by b’s and all c’c replaced by d’s, and wR is the reverse of w.
This may seem a little complicated but consider a string like aabax@yycdcc. If we replaced all d’s in the grammar with c’s and b’s with a’s, then the language would be {wxi@yjwR|i ̸= j, i, j ≥ 0, w1 ∈ {a, c}∗}. So all we need to do to get the language of the original grammar is replace the a’s and c’s in wR with b’s and d’s respectively.
Another point to note is that this language is not the same as the one below. {w1xi@yjw2 | i ̸= j,i,j ≥ 0,w1 ∈ {a,c}∗,w2 ∈ {b,d}∗,|w1| = |w2|}
Note that this latter language contains strings such as aabxx@yddd, which cannot be derived by the grammar.
where na(w) is the number of a’s in w, and similarly for b, c and d. (c) Is there a regular grammar for L(G)? Explain your answer.
Answer: There is no regular grammar for L(G). This language is context-free but not regular because there is a need to count the number of x’s and y’s to make sure that they are different, as well as counting the number of a’s or c’s and making sure there is an equal number of b’s or d’s.
(d) Construct a context-free grammar for the language below.
L = {xi w1@w2 yj | i ̸= 2j,i,j ≥ 0,|w1| = |w2|,w1 ∈ {a,c}∗,w2 ∈ {b,d}∗}
Answer: It is best to split this up into two cases and then combine the two grammars. So letL=L1∪L2 where
L1 = {xi w1@w2 yj | i < 2j,i,j ≥ 0,|w1| = |w2|,w1 ∈ {a,c}∗,w2 ∈ {b,d}∗}
and L2 = {xi w1@w2 yj | i > 2j,i,j ≥ 0,|w1| = |w2|,w1 ∈ {a,c}∗,w2 ∈ {b,d}∗}
For a constraint like i < 2j it can be helpful to use a table like the one below.
So for L1 we get G1 below.
i j 2j 012 112 224 324 436 536
S → xxSy | XA A → Ay | By X→x|λ
B → aBb | aBd | cBb | cBd | @
For L2 with the constraint i > 2j the corresponding table is below.
i j 2j 100 312 524 736
S → xxSy | C
C →xC |xD
D → aDb| | aDd | cDb | cDd | @
We can then combine these together for a grammar G for L = L1 ∪ L2.
S→T|U
T → xxTy | XA
A → Ay | By
X→x|λ
B → aBb| | aBd | cBb | cBd | @ U → xxUy | C C → Cy | Dy
D → aDb | aDd | cDb | cDd | @
There are ways this could be simplified, but that is not required. Constructing the grammar
this way gives confidence in its correctness, which is less obvious otherwise.
This leads us to the grammar G2 below.
2
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.”
Answer:
(a) Factorisation is probably intractable, but it is not known to be NP-complete. So it is incorrect to list it as an NP-complete problem.
(b) NP-complete problems are almost certainly intractable, but it is incorrect to say that these are certainly intractable.
(c) The best known algorithm for the Travelling Salesperson problem is exponential, and so the statement of the running time here is certainly incorrect.
(d) Algorithms with a running time of O(n10) are in the polynomial class, and hence are con- sidered tractable.
(e) The Hamiltonian Circuit problem is NP-complete, as is the Travelling Salesperson problem. So these are either both intractable or both tractable, i.e. in the same complexity class.
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 we will abbreviate to GW), 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.
3
Answer: The simplest proof of this will be to reduce the generalised Platypus problem from Assignment 2 (which you can assume is undecidable) to this problem. The key obser- vation is that the Gandalf the White machine never changes any cell on the tape, and never terminates. This means that the generalised Platypus game with Gandalf the White halts iff the generalised Platypus game (from Assignment 2) halts. In terms of machines, consider the diagram below. Note that the machine the GPGGW only needs the machines M1 and M2 as input.
It is also possible to use a reduction from the blank tape problem to the GPGGW problem as follows. Let M be the machine we want to analyse for the blank tape problem. Then M will halt on the blank tape iff the generalised Platypus problem with Gandalf the White halts for M and GW.
In terms of machines, consider the diagram below.
(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.
4
Answer: To show that a problem is NP-complete, we need to show that the problem is in NP, and that the problem is NP-hard, i.e. that there is a polynomial-time reduction to it from every other problem in NP. The simplest way to show the latter property is to find a polynomial-time reduction from a known NP-complete problem to it.
So given the information above, we also need to know the following.
i. That GPGGW is in NP.
ii. That the problem A is NP-complete.
iii. That the reduction from A to the GPGGW is polynomial-time.
(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.
Answer: A tournament of 100 machines will require 100 × 101 × 102/6 = 171, 100 matches. Doing this in 42.42 seconds means that this takes 0.000247059 seconds per match. An 8-hour limit gives Freddo 8 × 60 × 60 = 28, 800 seconds, and hence 8 × 60 × 60/(0.000247059) = 116, 571, 345 matches. When n = 886, the numebr of matches is 116, 310, 536, and for n = 887 it is 116,704,364. So n1 = 886, i.e. Freddo can play a tournament of up to 886 machines.
(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.
Answer: From the previous answer we know that Freddo can run up to 116,571,345 matches. When n = 221, we have n6/(1000000) = (221)6/(1000000) = 116,507,435, and when n = 222, it is 119, 706, 531. So n2 = 221, i.e. Freddo can play a tournament of up to 221 machines.
(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.
Answer: A Platypus tournament with n2 = 221 machines will take 1,823,471 matches, which will take 450.5 seconds, i.e. 7.5 minutes. A Koala tournament with n1 = 886 machines will take 483,729,230,338 matches which will take 119, 509, 574.55 seconds, i.e. 3.78 years.
(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
5
4. (a)
Enough said!
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.
Answer: We will assume your student number is 7654321. A Turing machine which recognises this is below. There are others of course, but note that this machine rejects any string of length 6 or less, as well as rejecting any string of lenth 8 or more.
and tells all his family and friends to avoid Hammy Spam Solutions at all times. Explain why Freddo did this, with particular reference to the cost for a tournaments involving 100, 1,000 and 10,000 machines.
Answer: The cost is exponential, and sooner or later will become far too expensive. Freddo knows he can run a Platypus tournament of 886 machines at no cost (apart from 8 hours on the familiy desktop). Consider the table below.
Machines 100 1,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000
Cost ($s) 2.70 20,959.16 439286205.05 9207067941189.81 192972369947324000.00 4044537935523770000000.00 84770100073685200000000000.00 1776709720877430000000000000000.00 37238335563086900000000000000000000.00 780484070759879000000000000000000000000.00 163,58,287,111,890,900,000,000,000,000,000,000,000,000,000.00
(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
Answer: All of these can be used to recognise your student number. There is no memory required, and it is simple to write a DFA for it. This means that all other types of automata can be used as well.
6
(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.
Answer: This machine nondeterministically replaces every x on the input tape with one of the digits 0-9. Given the input of xxxxxx to the machine, this has the effect of guessing a 7-digit number, no matter what that 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.
7
n Transitions Time 7
10
15
20
As the deterministic execution of M2 may take up to n × 10n transitions to guess the correct n-digit number, the maximum time for it to terminate will be n×10n ×3×10−5 = 3n × 10n−5 seconds. Note that each number takes n transitions.
n Transitions Time
Answer:
5. (a)
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.
Answer: One such machine is below.
7 70,000,000 10 1011
15 1.5 × 1016 20 2 × 1021
2100s = 35 minutes 34.7 days
14,259 years 1,901,285,269 years
(b)
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
1211 1211#1121 22001 22001#10022 1 1
20 20
Halt state
accepting accepting non-accepting non-accepting
8
Answer: One such machine is below.
(c) 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 w#wR@w 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.
Answer: Given that the reverse of wR is w, it is simple to reuse much of M3 (specifically states q1, q2, q3, q4 and q5) to use wR to produce wR@w just as M3 has ’converted’ w into w#wR. Specifically, we modify the transition from q5 to q9 to imitate the transition from q0 to q1 but outputting @ instead of # and then copy states q1, q2, q3, q4 and q5.
9
6. (a)
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.
Answer: The key idea is that transitions which replace blanks with other characters become transitions that recognise such characters. Specifically we replace the blanks in the transitions between q0 and q1, q2 and q1, q3 and q1 and q4 and q1 with #, 0, 1 and 2 respectively. This produces the required machine.
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.
Answer: We will prove the language L1 = {w#wR | w ∈ {0, 1, 2}∗} is not regular. Assume L1 is regular. Then there is an n ≥ 1 such that for all strings w ∈ L such that
|w| ≥ n, there exists strings x, y and z such that w = xyz and
i. |xy| ≤ n ii. y̸=λ
iii. xyiz∈Lforalli≥0
Letw=1n2#21n. Thenw∈L1 and|w|≥n,andso1n2#21n =xyz. As|xy|≤n,this
meansthatymustbeoftheform1j forsomej≥1.
Consider xy2z. As y = 1j, we have xy2z = 1n+j2#21n, and so xy2z ̸∈ L1. This is a
(d) 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.
contradiction, and so we conclude that L1 is not regular. QED
(b) 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?
Answer: We will prove the language L1 = {w#wR | w ∈ {0, 1, 2}∗} is not regular. Assume L1 is regular. Then there is an n ≥ 1 such that for all strings w ∈ L1 such that
|w| ≥ n, there exists strings x, y and z such that w = xyz and
i. |xy| ≤ n
ii. y̸=λ
iii. xyiz∈Lforalli≥0
Let . Thenw∈L1 and|w|≥n,andso
thismeansthatymustbeoftheform 2j forsomej≥1. Consider . As ,wehave
. As|xy|≤n, ,andso . Thisis
w = 2n12n#12n2n
a contradiction, and so we conclude that L1 is not regular. QED
The differences are highlighted in boxes. The only differences are the choice of word w, and
the use of i = 3 rather than i = 2. All other parts of the proof are the same. 10
2n12n#12n2n = xyz
xy3z
y = 2j
xy3z = 2n+2j12n#12n2n
xy3z ̸∈ L1
(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.
Answer: One such machine is below. This machine is deterministic as there is at most one transition for each state and input.
(d) Is there a context-free grammar for the language L2 = {w#wR@w | w ∈ {0, 1, 2}∗}? Explain your answer.
Answer: No. This language is not context-free, as it requires a PDA to record the first instance of w on the stack and check it against wR. This means that there is no memory left for checking the second instance of w.
(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.
Answer: One such machine is below.
11
(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.
Answer: First consider the various length of strings that will be accepted. When |w| = 0, there is only one string #. This will take 1 transition. When |w| = 1, there are 3 strings accepted, which requires 9 transitions (as it requires 3 per string). When |w| = 2, there are 9 strings, each of which requires 5 transitions, making 45. When |w| = 3, there are 27 strings, each of which requires 7 transitions, making 189 transitions in total. This makes a total of 1 + 9 + 45 + 189 = 244 transitions.
(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
Answer:
S → 01A10
A → 0#0 | 1#1 | 2#2
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,
12
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.
Answer: Sam’s idea requires solving the halting problem for Turing machines with a blank tape as input, which is known to be undecidable. So Sam cannot give the above guarantee, i.e. that their machine will either produce the output as required or told that their machine does not terminate, as there can be no such algorithm to do this.
(b) Suggest one way that Sam could achieve something along these lines by giving a less strong guarantee about the performance of C.
Answer: Sam should put a limit on how long the customer’s machine can run (say 5 minutes, or 1,000 steps). This means that Sam can guarantee that either the customer will get their output as promised, or that their machine will be returned to them with the message “Your machine took too long to run”.
13