Reference no: EM132677271

COSC 1107 Computing Theory - RMIT University

Question 1. Consider the grammar derivations below.
S ⇒ aSbb ⇒ aaSbbbb ⇒ aa#bbbb S ⇒ ccBd ⇒ ccccBdd ⇒ cccc#dd
S ⇒ ccBd ⇒ ccAd ⇒ cc1A1d ⇒ cc1#1d S ⇒ A ⇒ 2A2 ⇒ 2C2 ⇒ 2cCc2 ⇒ 2c#c2

(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. (4 marks) (c)Is the grammar G regular? Explain your answer.

d)Is there a deterministic finite state automaton for L(G)? Explain your answer. (2 marks) (e)Construct a context-free grammar for the language L2 below.
L2 = {w1 a2i cj al dk bi w2 | w1, w2 ∈ 1, 2∗, |w1| = |w2|, i ≥ 1, j, k, l ≥ 0, j < k}
(f)Explain why there is not necessarily a context-free grammar for L2.

Question 2. Legolas Brownbean, a friend of a more famous Legolas, has written the following discussion. There are 6 incorrect statements in the paragraph below. Identify all 6 incorrect statements and justify each of your answers.
Note: A single sentence counts as one statement.

"Algorithms are an expression of knowledge that makes computers work. In order to solve a particular computational problem, such as finding the factors of a given number, or sorting a list of students by their student number, an algorithm must be developed and implemented. It comes as a great surprise to many people that there are some problems for which there is no algorithm possible. These are known as undecidable problems and include the Halting problem for Turing machines, the busy beaver problem, the tile problem and the vertex cover problem. Alan Turing was the first to show there was an undecidable problem, and since that time many other problems have been shown also to be undecidable. This is done by reducing a problem (say A) with unknown status to a problem known to be undecidable (say B). From this reduction it is simple to show that problem A must be undecidable using the Pumping Lemma. The existence of undecidable problems means that certain properties of programs cannot be guaranteed. So anyone faced with an undecidable problem should refuse to work on it, as no instance of any such problem can ever be solved. The Church-Turing thesis, which states that anything computable can be performed by a Turing machine, indicates that we cannot avoid undecidable problems by changing technologies. Undecidable problems are only an issue for nondeterministic Turing machines, as anything that can be executed on a deterministic Turing machine is decidable. Unrestricted grammars also do not have any issues with undecidable problems. Note though that NP-complete and other intractable problems are all decidable. The limits on computing with such problems is practical rather than fundamental."

Question 3. The generalised 3-player Platypus game is defined as follows. Let M1, M2, and M3 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 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 3-player Platypus game 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 to some problem A, can this reduction be used to conclude that A is NP-complete? Why or why not? Explain your answer.

(c) Katie the Koala loves playing Platypus tournaments. She is particularly fond of the 4-player variety, for which a tournament of n machines will require n(n + 1)(n + 2)(n + 3)/24 matches.

She ran her own tournament on her own laptop for 200 machines, which took 97.65 seconds. Encouraged by this, she resolves to run the largest tournament that she can in 10 hours. Calculate the largest number of machines for which Katie can run a tournament in this amount of time.

(d) Katie is disappointed by the previous result and so turns to playing the same 4-player game but in a different tournament format suggested by her friend the Wombat. She works out that using this format the tournament takes (1.1)n/(1.05)n matches for n machines where n 200, using the Platypus game as in the previous question. Calculate the largest number of machines for which Katie can run a Wombat-style tournament in 10 hours.

(e) Never one to quit, Katie asks some friends for help. They work out that they have 10 identical computers between them, each of which can run a 4-player game in exactly the same time as Katie, and they agree to divide up the matches equally between them. Katie decides that they will attempt to collectively run a tournament for 2,000 machines in the original 4-player format. How long will each machine have to run to complete each person's share (ie 10%) of the matches? We will call this time t1.

(f) Flushed with their success, the group of friends that each one of them will dedicate the same time as calculated in the previous question for running as large a Wombat-style tournament as they can. Calculate the number of machines for which they can complete a Wombat-style tournament this way. In other words, what is the largest number of machines for which they can run a Wombat-style tournament in time t1?

4.(a)Student numbers at the University of Minas Tirith are strings of length 7 over the alphabet 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. The first digit of each number must be 7 and the final digit must be 1. Construct a Turing machine which recognises such student numbers. Any string of length 6 or less should be rejected, as should any string of length 8 or more.

(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

(c) Given a Minas Tirith student number (as in the previous question), the internal string is the 5 digits of the number excluding the 7 at the start and the 1 at the end. For example, given the student number 7654321, the internal string is 65432. The Steward of the university, Denethor the Demented, announces that he is especially interested in student numbers whose internal string is either a palindrome or contains at least three 9s, which he calls Palantir numbers. Note that the string has to be a valid student number as well in order to be a Palantir number. For example, 7643461 and 7299991 are both Palantir numbers, and 7666441 and 7992281 are valid student numbers but not Palantir numbers, and 199991 and 63399332 are neither.

Which of the following machines can be used to recognise valid student numbers that are also Palantir numbers? Briefly justify each of your answers. You do not have to explicitly construct any machines in your answer.

ˆ A deterministic Turing machine
ˆ A non-deterministic PDA
ˆ A non-deterministic finite state automaton (NFA)
ˆ A deterministic finite state automaton (DFA)

(d) Some time later, Denethor changes his mind about both Minas Tirith student numbers and Palantir numbers. He decrees that from now on student numbers can be of any odd length, provided the first digit is 7 and the final digit is 1. He also decrees that Palantir numbers must be palindromes only. For example, 711 and 798654321 are now both valid student numbers, but 7992281 is no longer a Palantir number, whereas 71234543211 is a Palantir number.
Given these changes, which of the following machines can be used to recognise valid student numbers that are also Palantir numbers? Briefly justify each of your answers. You do not have to explicitly construct any machines in your answer.
ˆ A deterministic Turing machine
ˆ A non-deterministic PDA
ˆ A non-deterministic finite state automaton (NFA)
ˆ A deterministic finite state automaton (DFA)

Question 5. (a)Construct a Turing machine M1 which given as input a string of length 7 over 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 performs as follows.
ˆ The fourth digit, whatever it is, is replaced with a blank.
ˆ Any of the digits 5,6,7,8 or 9 is replaced with 0,1,2,3 or 4 respectively.
ˆ The machine must terminate on all strings over 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 ∗ (including the empty string).
ˆ The machine only halts in an accepting state if the input string has exactly 7 digits.
Strings of any other length are rejected.
(b) Construct a Turing machine M2 which given as input two string of digits over 0, 1, 2, 4, 5 separated by a blank performs as follows.
ˆ If either string has length less than three, the machine halts with rejection.
ˆ If the final digit of both strings is 0, 2 or 4, then machine halts with acceptance.
ˆ If the final digit of either string is 1 or 3, the machine loops forever (i.e. it does not terminate).
(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.
ˆ 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) An evil wizard now changes M1 to another machine M0. This is the same as M1 except that rather than deterministically replacing 5, 6, 7, 8 or 9 with 0, 1, 2, 3 or 4, M0 non- deterministically replaces each of these digits with one of 0, 1,2,3, or 4. For example, if there is a transition such as δ(qi, 5) = (qj, 0, R) in M1, there are 5 transitions in M0, i.e. δ(qi, 5) = {(qj, 0, R), (qj, 1, R), (qj, 2, R), (qj, 3, R), (qj, 4, R), } in M0.
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?
ˆ For which inputs does M4 not halt?
In each case, justify your answer.

Question 6.(a)Prove that the language L1 = aibjcjdi i, j 0 is not regular by using the Pumping Lemma. Use the string anbncndn at an appropriate point in the proof.
(b) Write out the proof of the same result which uses the string b2nc2n and i = 4 instead. Which steps are different? Which steps remain the same?
(c) Give a PDA for the language L1 = aibjcjdi i, j 0 . Is your machine deterministic or non-deterministic? Briefly explain your answer.
(d) Is there a context-free grammar for the language L2 = aibjcidj i, j 1 ? Explain your answer.
(e) The language L3 = {aibjcidj|1 ≤ i, j ≤ 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 = aibjcidj 1 i, j 6 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 L5 = aibjcjdi i, j 1 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.
S → aA|Aa|a A → aBaa|Baa B → abc

Question 7. Snivelling Sam the Shonky Snake Oil Salesman has heard about your work on Turing machines. This is of great interest to Sam, who wishes to set up a Gallery of Important Turing Machines which are Useful and Brilliant (GITMUB). This will showcase various Turing machines, which must be of the acceptor/rejector type (i.e. Turing machines which accept a given language by terminating in an accepting state). Sam is keen to ensure that he only has the "best and brightest" Turing machines on display from those submitted to GITMUB by the general public, and so insists on the following policy on adding machines. Let the machine to be added to GITMUB be M, and the machines already in GITMUB be M1, . . . , Mn. If L(M ) L(Mi) for all 1 ≤ i ≤ n, then M is added to GITMUB. Otherwise, (i.e. L(M ) = L(Mi) for some 1 ≤ i ≤ n) then Sam makes a choice between M and Mi, and either rejects M as a member of GITMUB, or ejects Mi from GITMUB and replaces it with M (according to what he perceives as the ‘inherent artistic merit' of each machine). This means that Sam can boast that GITMUB's machines are all guaranteed to be unique representatives of machines accepting a particular language.

(a) Explain why, under the above policy, GITMUB can never be guaranteed to contain more than one machine.
(b) Suggest one way that Sam could relax his policy on adding machines to the gallery in order to have a larger collection of machines in GITMUB while remaining as true as possible to his original aim.
(c) Sam is also interested in the history of Turing machines, and runs a competition to find the Greatest Ingenious Turing Machine of All Time (the GIMOAT). Sam asks you for your choice of a Turing machine to enter into this competition. What machine would be your choice? Justify your answer.

Attachment:- Final Exercise.rar