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 Marks
1 Overview
Computing Theory COSC 1107/1105 Final Exercise
Saturday 6th November 2021, 9.00am 110 worth 50% of your final assessment
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.
2
Assessment details
1. Consider the grammar derivations below.
S ⇒ 00S1 ⇒ 0000S11 ⇒ 00000S111 ⇒ 00000#A#111 ⇒ 00000#B#111 ⇒ 00000#C#111 ⇒
00000#cDd#111 ⇒ 00000#c2d#111
S ⇒ #A# ⇒ #aAb# ⇒ #aaBbb# ⇒ #aacCdbb# ⇒ #aaccCddbb# ⇒ #aacccDdddbb# ⇒
#aaccc3dddbb#
S ⇒ 0S1 ⇒ 0#A#1 ⇒ 0#aaAbb#1 ⇒ 0#aaBbb#1 ⇒ 0#aaCbb#1 ⇒ 0#aacCddbb#1 ⇒
0#aaccDdddbb#1 ⇒ 0#aacc2dddbb#1
(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 the grammar G context-sensitive? Explain your answer.
(d) What happens to L(G) if the rule S → SS is added to G? Explain your answer (but there
is no need to give the new language in set notation). (3 marks)
(e) Construct a context-free grammar for the language L2 below. (4 marks)
L2 ={ai 0j wcl edl wR 1k b2i |w∈{2,3}∗,k≥j,i,j,k≥0,l≥1}
(f) Explain why there is not necessarily a deterministic pushdown automaton for L2. (2 marks)
(2+3+2+3+4+2 = 16 marks)
(2 marks) (3 marks) (2 marks)
2.
The following discussion was discovered in some ancient archives. There are between 6 and 12 incorrect statements in the paragraph below. Identify all incorrect statements and justify each of your answers.
Note: A single sentence counts as one statement.
”The Chomsky Hierarchy is a way of classifying languages and the classes of grammars that generate them. The distinct classes of grammar are labelled as Type 0 to Type 4 inclusive. Each class of grammar is distinct, meaning that no grammar appears in more than one class. For each class of grammar there is a corresponding class of automata, and these automata can be either deterministic or non-deterministic. For every nondeterministic automaton in any of these classes there is an equivalent deterministic automaton which recognises the same language. It is also the case that for every possible input for every automaton in these classes, the computation on that input always terminates, although this may take a very long time. This means that we can divide the decidable problems into two classes – the tractable ones, which can be decided in at most polynomial time on a deterministic Turing machine, and the intractable ones which take at least exponential time on a deterministic Turing machine. Some well-known examples of intractable problems include the vertex cover problem, the Hamiltonian circuit problem, the Travelling Salesperson problem and the Halting problem for Turing machines. It is remarkable that many of these intractable problems are related by being NP-complete, which means they are all of a similar level of complexity. The problems in NP are those which can be solved in polynomial space on a nondeterministic Turing machine. To be NP-complete, a problem has be in NP, but also be at least as hard as every other problem in NP. This property is shown by a process known as reduction, in which a problem is shown to be NP-complete by showing that it can be reduced to some already known NP-complete problem. Starting with a theorem from the early 1970’s, which showed that 3SAT is NP-complete, a large library of NP-complete problems and their relationships has been built up over the years. Known NP-complete problems include the knapsack problem, the bin packing problem, integer factorisation and the 3-colouring problem. It is strongly suspected that all NP-complete problems are intractable, i.e. cannot be solved in polynomial time. In order to show that P ̸= NP, it would be sufficient to show that one NP-complete problem is certainly intractable. NP-complete problems also have the intriguing property that a purported solution can be checked in polynomial time, which makes them potentially useful for zero-knowledge proofs. ” (12 marks)
(a) Prove that Empty Language problem for Turing machines is undecidable by reducing the Halting problem to it. Make sure all the details of the reduction are clearly specified. You may use a diagram to assist with this if you wish. (4 marks)
(b) A similar problem is the All Inputs problem for Turing machines. How similar is the proof for the undecidability of this problem to the above proof for the Empty Language problem? Explain your answer. (4 marks)
(c) The sun is around 4.5 billion years old, and is expected to use up its hydrogen reserves (leading to it becoming a red giant) in about 5 billion years. The Tower of Hanoi is a game that is known to require 2n − 1 moves to complete for a tower of height n. The 4-player Platypus game is known to require n(n + 1)(n + 2)(n + 3)/24 matches for a tournament with n entries. Assuming that moves in the Tower of Hanoi take 0.1 seconds each and n = 64, and 4-player Platypus matches take 0.001 seconds each and n = 500, 000, calculate which process is more complete by the time the sun uses up its hydrogen reserves. In other words, at that time, which will be greater – the percentage of the Tower of Hanoi moves that are completed out of the total when n = 64 or the percentage of the matches for a tournament
3.
2
of n machines that are completed out of the total when n = 500, 000? Explain your answer and include all relevant calculations. (4 marks)
(d) How does your answer change if the moves for the Tower of Hanoi now take 0.01 seconds and those for the Platypus game now take 0.01 seconds? Explain your answer. (2 marks)
(4+4+4+2 = 14 marks)
4. “Everything in triplicate” is the motto of the University of Warthogs, which means that student numbers are of the form www where |w| = 3 and w ∈ {0,1,2,4,5,7,8}∗. The digits 3, 6 and 9 are not used in such numbers, as these are considered sacred digits. For example 014014014, 778778778 and 224224224 are valid student numbers.
(a) Construct a Turing machine to recognise such numbers. Note that any string of length 8 or less should be rejected, as should any string of length 10 or more. In addition, any string of length 9 containing a 3, 6 or 9 should be rejected. (3 marks)
(b) Which of the following machines could also be used to recognise such numbers? 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
(2 marks)
(c) The Chancellor of the University of Warthogs, Pumbaa the Magnificent, soon realises that limiting the number of students in his university to a few hundred is not a good idea. So he then decrees that student numbers can now be of the form www or wwRw or wwwR or wwRwR where |w| = 3 and w ∈ {0,1,2,4,5,7,8}∗
Which of the following machines can be used to recognise the new student numbers? Briefly justify each of your answers. You do not have to explicitly construct any machines in your answer. (3 marks)
A deterministic Turing machine
A non-deterministic PDA
A non-deterministic finite state automaton (NFA) A deterministic finite state automaton (DFA)
(d) Having finally received some better advice, Pumbaa further decrees that from now on, all student numbers will be of the form wwRw where |w| ≥ 3 and w ∈ {0, 1, 2, 4, 5, 7, 8}∗.
Given these changes, which of the following machines can be used to recognise this latest definition of valid student numbers? Briefly justify each of your answers. You do not have to explicitly construct any machines in your answer. (3 marks)
A deterministic Turing machine
A non-deterministic PDA
A non-deterministic finite state automaton (NFA) A deterministic finite state automaton (DFA)
(e) After a particularly bad nightmare, Pumbaa (who changes his mind like the wind) now insists that in addition to the conditions in the previous question, all numbers must have
3
5.
the property that the w in wwRw cannot repeat any digits. In other words, the only valid student numbers are wwRw where |w| ≥ 3 and w ∈ {0, 1, 2, 4, 5, 7, 8}∗ and there are no repeated digits in w. For example, 122442211224 is no longer a valid student number as the string 1224 has a repeated 2. Does this change your answer to the previous question? If so, why and how? If not, why not? (3 marks)
(3+2+3+3+3 = 14 marks)
(a) Construct a Turing machine M1 which given a string of length 7 over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} performs as follows. (3 marks)
The machine only halts in an accepting state if the input string has exactly 7 digits and commences with 3. Strings of any other length are rejected. Strings of length 7 that do not commence with 3 cause the machine to loop forever.
If the last digit is 1, 3, 7 or 9, the machine replaces each of these digits with 5, and each of the digits 2, 4, 6 and 8 with 0.
If the last digit is 2, 4, 6 or 8, the machine replaces each of these digits with 5, and each of the digits 1, 3, 7 and 9 with 0.
If the last digit is 0 or 5, the machine loops forever.
(b) Construct a Turing machine M2 which given a string over {0, 1, 2, 3, 4, 5} performs as follows.
(3 marks)
If there are no 5’s in the input string, the machine loops forever. Otherwise
– if there are an even number of 5’s in the input string, the machine replaces each 5 with a 2.
– If there are an odd number of 5’s in the string, the machine replaces each 5 with a 1.
All 0’s in the string are replaced with a 3.
(c) Consider the machine formed by combining M1 and M2 as above in sequence into a new machine M3, so that M3 first performs as M1 does, rewinds the tape head to the appropriate point on the tape and then performs as M2 does. Clearly the behaviour of M3 will depend on the behaviour of M1 and M2. (4 marks)
For which inputs does M3 halt with rejection?
For which inputs does M3 halt with acceptance? For which inputs does M3 not halt?
In each case, justify your answer.
(d) Consider now the machine M0, which is the same as M1 except that rather than determin- istically replacing 1,3,7, and 9 with 5, M0 nondeterministically replaces each of these digits with one of 5 or 2, and rather than deterministically replacing 2,3,6, and 8 with 5, M0 non- deterministically replaces each of these digits with one of 5 or 3. For example, if there is a transition such as δ(qi, 3) = (qj , 5, R) in M1, there are 2 corresponding transitions in M0, i.e. δ(qi,3) = {(qj,5,R),(qj,2,R)} in M0. (4 marks)
The same combination technique as above is used to combine M0 and M2 into M4. For which inputs does M4 halt with rejection?
For which inputs does M4 halt with acceptance? 4
For which inputs does M4 not halt? In each case, justify your answer.
(3+3+4+4 = 14 marks)
6. (a) (b) (c)
Prove that the language L1 = {ww | w ∈ {0,1,2}∗} is not regular by using the Pumping Lemma. Use the string 1n2n at an appropriate point in the proof. (5 marks)
Write out the proof of the same result which uses the string 2n10 and i = 3 instead. Which steps are different? Which steps remain the same? (4 marks)
There are some errors in the proof below that the language L2 = {1i 2j 3i 4i | i, j ≥ 0} is not context-free. Find and correct all such errors. The best way to do this is to write out the correct proof, highlighting the differences between the correct proof and the one below. (4 marks)
Claim: The language L2 = {1i 2j 3i 4i | i, j ≥ 0} is not context-free.
Proof: Assume L2 is regular. Then the Pumping Lemma applies and so for all n ≥ 1 such
that for some w ∈ L such that |w| ≥ n, w = xyzuv where
|yzu| ≤ n
y̸=λandu̸=λ
xyizuiv∈Lforalli>0
Choosew=1n2n3n4n andsow∈Land|w|≥n. SobythePumpingLemmaw=xyzuv= 1n2n3n4n and |yzu| < n. This means that y and u can contain at most two different digits.
Now if y or u contains 12, or 23 or 34, then xy2zu2v ∈ L, as there would be some digits out of order.
So both y and u contain at most one type of digit. But this also means that xy2zu2v ̸∈ L, as then there will not be equal numbers of 1’s, 3’s and 4’s in xyzu3v.
This is a contradiction, and so L2 is not context-free.
Give a PDA for the language L3 = {1i 2j 3j 4i | i, j ≥ 0}. Is your machine deterministic or
non-deterministic? Briefly explain your answer. (2 marks)
Is there a PDA for the language L4 = {w | w ∈ {1, 2, 3, 4}∗, n1(w) = n4(w), n2(w) = n3(w)}? Note that this is similar to L3 but without any constraint on the order of the digits (i.e. the number of 1’s and 4’s in w must be the same, and the number of 2’s and 3’s in w must be the same). Explain your answer. Note that there is no need to either construct a PDA or give a proof that there is none to answer this question; a few sentences of argument will suffice. (3 marks)
Give a context-free grammar for L5 = {2# 1i 2j 0 3j 4i#3 | i,j ≥ 0} with at most 5 rules. The number of rules is the number of different right-hand sides in the grammar; for example, the grammar below has 6 rules. (2 marks)
S → aA|Aa|a A → aBaa|Baa B → abc
(5+4+4+2+3+2 = 20 marks)
(d) (e)
(f)
7. Gregor the Grammar Goblin hears about your work in Computing Theory, and is of course very impressed. He particularly loves the idea of grammars generating languages, and that in principle, everyone could specify their own grammar, and hence their own language. He is also an
5
entrepreneur, and during a conversation with you about the Chomksy hierarchy, he has an idea for a new business. This is for customers to send him an unrestricted grammar, from which he will then generate all words in the language (up to a limit of 1,000), which he will then arrange via a new artistic algorithm of his in a visually appealing manner. He will then charge the customer a very large sum of money for the artistic output. However, Gregor is not a fan of swear words, and so he wants to incorporate in the process a means to check the words generated by the grammar against his list of offensive words. If any of the words on Gregor’s list are in the language specified by the customer’s grammar, Gregor will refuse to generate the artistic output, and instead fine the customer for offensive language. Naturally Gregor looks to you to develop this process, and insists that this process must work for any possible grammar that the customer may have.
(a) Explain why Gregor’s idea will not work, no matter how much computing power he may use. (4 marks)
(b) Gregor also hears on his social media channels about universal Turing machines, thinks they are very cool, and suggests to you that a solution to his original problem may be to encode the customer’s unrestricted grammar as an input to a universal Turing machine. Explain why this approach will be no help. (2 marks)
(c) Suggest a way in which Gregor can accomplish something like his original intention by an appropriate relaxation of his policy. (3 marks)
(d) Gregor is rather stubborn, though, and would like to be able to guarantee that his process of checking for swear words will work. What classes of grammar from the Chomsky hierarchy, if any, could be used for this purpose? Explain your answer. (3 marks)
(4+2+3+3 = 12 marks)
8. Consider the definitions below.
A universal Turing machine U is a Turing machine that takes the encoding of a Turing machine M and an input string w and emulates the computation of M on w. More specifically, U takes as input code(M)code(w), (where code() is a function which encodes Turing machines and inputs into the input language of U ) and for every configuration in the computation of M on w, there is a corresponding configuration in the computation of U on code(M)code(w).
A universal Turing machine U is steadfast if for every M and w, whenever M terminates on w, U terminates on code(M)code(w).
A universal Turing machine U is dedicated if for every M and w, whenever M does not terminate on w, U does not terminate on code(M)code(w).
A universal Turing machine is constant if U is steadfast and dedicated.
(a) Is it possible to have a universal Turing machine which is steadfast but not dedicated? Is it possible to have a universal Turing machine which is dedicated but not steadfast? Explain your answers. (4 marks)
(b) Should it be a requirement for a universal Turing machine to be constant? Or is it reasonable for a universal Turing machine not to be constant? Explain your answer, using appropriate
examples.
(4 marks) (4+4 = 8 marks)
6
3 Submission
You should submit one PDF file containing your answers to the questions. Do not use a .zip file. No file formats other than PDF will be accepted.
7