Computing Theory
COSC 1107/1105
Final Exercise (Practice version Answers)
1 Assessment details
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 → cSd and S → λ. From the second derivation we can add the rules S → A, A → xAy,
A → B@, B → xB and B → x. From the third derivation we can add the rules A → @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))R | i 6= 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 6=
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 6= 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 6= 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
let L = 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.
i j 2j
0 1 2
1 1 2
2 2 4
3 2 4
4 3 6
5 3 6
So for L1 we get G1 below.
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
1 0 0
3 1 2
5 2 4
7 3 6
This leads us to the grammar G2 below.
S → xxSy | C
C → Cy | Dy
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.
2
2. Drogo the Dreary, a distant relative of Thorin Oakenshield, 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
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 Cost ($s)
100 2.70
1,000 20,959.16
2,000 439286205.05
3,000 9207067941189.81
4,000 192972369947324000.00
5,000 4044537935523770000000.00
6,000 84770100073685200000000000.00
7,000 1776709720877430000000000000000.00
8,000 37238335563086900000000000000000000.00
9,000 780484070759879000000000000000000000000.00
10,000 163,58,287,111,890,900,000,000,000,000,000,000,000,000,000.00
Enough said!
4. (a) 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.
(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
Answer: 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
7 70,000,000 2100s = 35 minutes
10 1011 34.7 days
15 1.5× 1016 14,259 years
20 2× 1021 1,901,285,269 years
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.
(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 Halt state
1211 1211#1121 accepting
22001 22001#10022 accepting
1 1 non-accepting
20 20 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 w
R 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
(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.
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.
6. (a) 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 6= λ
iii. xyiz ∈ L for all i ≥ 0
Let w = 1n2#21n. Then w ∈ L1 and |w| ≥ n, and so 1n2#21n = xyz. As |xy| ≤ n, this
means that y must be of the form 1j for some j ≥ 1.
Consider xy2z. As y = 1j, we have xy2z = 1n+j2#21n, and so xy2z 6∈ L1. This is a
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 6= λ
iii. xyiz ∈ L for all i ≥ 0
Let w = 2n12n#12n2n . Then w ∈ L1 and |w| ≥ n, and so 2n12n#12n2n = xyz . As |xy| ≤ n,
this means that y must be of the form 2j for some j ≥ 1.
Consider xy3z . As y = 2j , we have xy3z = 2n+2j12n#12n2n , and so xy3z 6∈ L1 . This is
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
(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

欢迎咨询51作业君