COSC 1107/1105 - Computing Theory Assignment

Assignment Task

1 Overview

This assignment is intended both for introducing you to some basic concepts that we will use in various ways later in the course, and to provide some early feedback on your progress. The are six key concepts that we will return to again and again, which are formal languages, regular expressions, grammars, finite state automata, pushdown automata and Turing machines. A common thread in all of these is nondeterminism. This will come up in various contexts, as you will see. Much of this assignment is concerned with these concepts, to ensure that you are well-versed in these fundamentals. There is another part which deals with the Platypus game, and another which allows you to show off your creative or investigative skills.

2 Assessment details

A Note on Notation of Regular Expressions: Unfortunately there isn’t a uniformly accepted standard notation for regular expressions. The two main issues are the specification of alternatives, and how to abbreviate some obvious patterns like letters and numbers. So in this assignment the following syntactic rules will be used.

• ’+’ will be used to denote both alternatives (as in (1+2)∗ ) and also to denote one or more applications of Kleene star (as in a +, meaning the language {a n |n ≥ 1}). You must take its application within the context in which it is applied (so you will need to use your brains!).
• Ranges such as all letters or all digits will be represented as [a − z] meaning (a + b + c + d + e + f + g + h + i + j + k + l + m + n + o + p + q + r + s + t + u + v + w + x + y + z). Hopefully the reason for using ranges is obvious!

1. Regular expressions and languages 

Historians have long debated the role and significance of the ceremony known as Stagscratch, which appears to have been practiced for many centuries, including at the legendary school Pigwarts. Ceremonies took place at irregular intervals, although never on the 30th or 31st of any month, and involved a combination of up to three of four possible instruments, being bagpipes, drums, horns, and lutes. Records of all Stagscratch ceremonies at Pigwarts since the year 500 have been kept in a handwritten archive, although there appear to have been no such ceremonies since the last recorded on on 29th December 1899. To save precious parchment and ink, the records of each ceremony were kept as a string, using one character for each instrument (b, d, h,, and l respectively) used, and including the date, and the instruments used in that particular ceremony. Such strings were written as follows.

CY₁Y₂M₁M₂D₁D₂SE  where

• C is the century indicator
• Y1Y2 are the last two digits of the year of the date
• M1M2 are two digits of the month of the date
• D1D2 are two digits of the day of the date
• S is the sequence of instruments used in the ceremony
• E is either the character a or the character z (indicating what caused the ceremony to end)

Note that C is either a single character in {5, 6, 7, 8, 9} or string of length 2 with the first character and the second in [0 − 8], D1 is a single character in {0, 1, 2}, and M1 is a single character in {0, 1}.

While no ceremony ever used more than three instruments, each instrument could be used any number of times, and in any sequence, as long as at least one instrument was used. So the sequence S can be any non-empty sequence of up to three instruments. For example, bdbdbdbh, llllllllllldb and hlhlhlhllll are all legal sequences of instruments, but lhdb and bbdhl are not (because they both contain four instruments).

Scribes also had the habit of omitting the century, year, month and day from an entry if they were the same as the previous entry. For example the entry 5670122bbbaddz indicates two ceremonies on the 22nd of January in the year 567, whereas the entry 18341007dlbdlbdlba08bbbbbbbz indicates one ceremony on 7th October 1834 and a second on 8th October 1834.

Ceremony records were written one after the other on the parchment as one enormous string. In order to analyse the history of Stagscratch, it is necessary to write regular expressions to identify specific matches of interest somewhere in this string. Scribes were attentive and diligent, but inevitably it has been observed that there were occasionally errors made by scribes. This means that any regular expressions for such purposes must be precise, and cannot assume that any given entry is error-free.

(a) Give a regular expression for the following cases. In each case explain your answer.

i. Any ceremony taking place before the year 1000 in which neither drums nor bagpipes were used.

ii. Any ceremony in July or August after the year 1199 which began with bagpipes followed by drums. 

iii. Any “syntactically correct” record of a ceremony. This means the recorded entry must have M1 being either 0 or 1, D1 being 0, 1 or 2, include at most three instruments as above, a correct “end marker” and take into account the potential omission of the dates. Anything not “syntactically correct” must be an obvious error, such as the date 19994966 or the ceremony sequence bdlhnnnnq. 

iv. Any ceremony of the 7th of some month in which exactly two instruments were used. 

(b) Is it possible to give a regular expression for the following? Explain either why it is possible or why it is not.

i. Any two consecutive ceremonies which used exactly the same sequence of instruments. 

ii. The maximum number of times a given instrument is used in all of Pigwarts’s history.

iii. Any year in which no ceremony ever used a bagpipe. 

iv. Determining when, if ever, the lute has been used more than 1,000 times in history. 

2. Grammars 

Consider the grammar below.

S → IIS | E

I → b | d | h | l

E → a | z

(a) Give derivations in G of the strings bdbbhha, ddbhllz and ddddbba.

(b) Is λ ∈ L(G)? Explain your answer

(c) Express L(G) in set notation. Explain why your answer is correct.

(d) Dodgy Roger, a legendary graduate of Pigwarts, claims that the above grammar is a correct specification of the legal sequences of instruments used in a ceremony (followed by the required a or z of course). Give (at least) three reasons why Dodgy Roger is incorrect. 

(e) Give a (correct) grammar for specifying legal sequences of instruments used in a ceremony. Explain how you derived your grammar and why it is correct.

3. Finite State Automata 

Consider the finite state automaton M1 below. You can download this from Canvas here.

(a) Give three examples of strings in L(M1) of length at least 6. There must be at least one example string which finishes in state q6, and similarly for states q9 and q12. 

(b) Explain why M1 is non-deterministic. Give as many examples as you can find of states for which there is more than one successor state for some input in your explanation. 

(c) What is L(M1)? Explain your answer. 

(d) Is it possible to create an equivalent machine M2 with fewer transitions or states than M1? Explain your answer. Note that by equivalent we mean L(M1) = L(M2). 

(e) Consider the machine M3 which is derived from M1 as follows. Is M3 equivalent to M1? Explain your answer. 

• Delete all transitions from q7 to q2.
• Delete all transitions from q8 to q2.
• Delete the transition δ(q8, 7) = q7.
• Delete the transition δ(q9, 7) = q7.
• Delete the transition δ(q9, 3) = q2.
• Add the transitions δ(q7, x) = q7 for x ∈ {0, 1, 2, 3, 4, 5, 6, 8}.
• Add the transitions δ(q8, x) = q8 for x ∈ {0, 1, 2, 4, 5, 6, 7, 8, 9}.
• Add the transition δ(q9, 3) = q9.

4. Pushdown Automata 

Consider the pushdown automaton M4 below. You can download this from Canvas here.

(a) Show all executions of the strings 123, 132, 2124 and 213431, and determine which are accepted and which are not.

(b) What is L(M4)? Explain your answer. 

(c) Does L(M4) change if we replace the transition δ(q1, 4, λ) = (q4, λ) with the transition δ(q1, 4, C) = (q4, C)? Explain your answer.

(d) Give a PDA M5 such that L(M5) = {1 n2 m3 k2 m+11 n+2 | n, m ≥ 1}. Explain why your machine is correct. 

5. Turing machines 

Consider the Turing machine M6 below. The input alphabet to this machine is {1, 2, 3, 4}.You can download this from Canvas here.

(a) What is L(M)? Show some examples of strings accepted and rejected to justify your answer. You must show at least one accepted string of length at least 6, and at least one rejected string of length at least 6. 

(b) Consider the Turing machine M7 obtained from M6 by adding the transitions δ(q4, x) = (x, L, q5) for x ∈ {2, 3, 4}. Is M7 equivalent to M6? Explain your answer. 

(c) Consider now the Turing machine M8 obtained from M6 by adding the transitions δ(q0, x) = (x, R, q1) for x ∈ {3, 4}. Is M8 equivalent to M6? Explain your answer. 

6. Get Creative! 

This will form part 1 of an investigation or creative artefact; you will be able to build on and extend on this topic (or explore a different one if you wish) in Assignment 2. You are strongly encouraged to use Adobe Express, to which all RMIT students have access. You can find the details about Adobe Express and other tools at this link. There are many aspects of Computing Theory that allow you to show your investigative or creative skills. This could be in the form of an investigation into a particular topic (Universal Turing machines, Langton’s Ant, Paterson’s Worms, two-dimensional Turing machines, ...) or by coming up with a creative artefact (story, movie, VR experience, images, ...) which takes as its subject a topic relevant to Computing Theory. Investigations will typically generate empirical data, often by using existing software (with some possible modification of your own if need be). One such investigation would be to use Colmerauer’s universal Turing machine (or any other explicitly defined universal Turing machine). Another would be to generate your own experimental data on well-known concepts such as Langton’s Ant or Patersons’s Worms. If creative practice is more to your liking, then coming up with a creative story involving a Turing machine of some kind, or a topic of similar relevance to Computing Theory (such as the Enigma machine, or Chomsky’s work on grammars). You could also present this in animated or video form, or as text. You may also propose an alternative topic of your choice if you wish. The idea is to allow you some “space” to develop your own understanding of a particular topic of interest. But please do seek the approval of the lecturer for any alternative topic.

Some more details on particular topics are below.

Two-dimensional Turing machines

Turing machines were conceived in a less visual era. Whilst in principle the restriction to a onedimensional tape does not reduce the scope of programs that can be written, there is a modern reason why a two-dimensional version is much more interesting: the predominance of the computer monitor as an output device. In particular, in the modern computing environment, there is every reason to consider abstract computations which use images as basic symbols, rather than numerals or similar strings (which, for all their mathematical properties, are visually rather prosaic). There are several varieties of two-dimensional such machines that have some rather curious properties, such as Langton’s ant, Turmites and Paterson’s worms.

Small universal Turing machines

Universal Turing machines are often rather large. In 2007, a competition was held to determine whether or not a given 2-state 3-symbol machine was universal or not. The question was settled in the affirmative, with the winner of a US$25,000 prize being a 20-year-old undergraduate. The quest for small universal machines continues, as there is some issue about the precise definition of universality used in the competition. You can write a report about the competition itself, or on aspects of the quest for small universal Turing machines. Perhaps pick a side in the debate (i.e. was the winning machine actually universal? Should the definition of universality be changed as a result?) and argue for it. Or argue for both sides and come to your own conclusion.

Notable universal Turing machines

It is remarkably difficult to find ’good’ explicit examples of Turing machines. Some well-known examples include Turing’s original machine, and machines built in particular ways by Minsky, Colmerauer and Wolfram. For example, Colmerauer built his machine as a means of teaching assembly language programming (!!), and intended it to be programmable. Minsky, on the other hand, derived his machine from principles of tag systems, and while it is certainly universal, it is harder to imagine programming it. There is also a relatively recent universal machine in two dimensions constructed by Dershowitz and Dowek, for which a Java implementation is available via Github.

7. The Platypus game For this task you will need to be familiar with the Platypus game. 

You have been allocated a number of machines, based on your student number.

(a) Play a tournament amongst your entire list of machines. There is SWI-Prolog code available for you to do this in Canvas. The main thing you need to do is to use your particular list of machines for the tournament. You should report your results as follows.

i. Report the top 10 machines performance, ranked in “football” order, ie by number of wins, and if the wins are equal, by the ratio of points scored for to points scored against. You should include both the tournament.csv file generated by the software in your submission, as well as include a table in your PDF file with the top 10 according to this ranking. 

ii. Examine your top 10 machines. Are they any key similarities or differences between them? In your analysis, what makes these the top performers? 

iii. How does your top 10 change if the ranking is based on overall points for, rather than as above? Explain your answer. 

iv. Examine your bottom 10 machines. Were there any machines without a win? What is the difference between these machines and the top performers? 

v. Suggest at least one way in which the game rules can be changed which would alter the outcome of the tournament. Keep in mind that each tournament typically involves thousands of games, so any such change must not require input from the user during the game. 

(b) Time how long it takes your tournament to run. Record that time along with the basics of the machine on which it was run. For example, “My tournament involved 42,132 matches which 6 took 156.5 seconds on a Windows 10 desktop with an Intel i7 processor and 16GB of RAM.” 

(c) A tournament of this form involving n teams requires n(n + 1)/2 matches.3 Use your time above to calculate the average time it takes for a match on your machine, and use this value to calculate long it would take to run a tournament for 100, 1,000, 10,000, 100,000, and 1,000,000 matches. Present your results in the form of a calculation and a table of the form below. 

(d) Calculate the largest Platypus tournament you can play on your machine in 4 hours, ie 4×60× 60 = 14, 400 seconds. Use the value calculated above for how long it takes you to play a match.

(e) The Platypus game is entirely deterministic, and hence a little boring as entertainment. Suggest at least two ways in which the game can be extended to increase player involvement in the game.

(f) As discussed in class, some variations of the Platypus game seem appropriate. Your tasks is to rerun your tournament with your allocated machines, with different parameters, and to compare the results. You should include at least the variations below (and more if you wish). The code to do all this will be provided.

Variation              Description

Standard                No changes; this is the original version

Tree                       5 points for whenever either tree is reached

Green                    2 points rather than 1 for changing green to yellow

Short                      Maximum game length of 50 rather than 100

Long                      Maximum game length of 200 rather than 100 

Tiebreaker             A random starting configuration is chosen with game length is 200 

For each of the variations above, you should report the following results.

• Time taken
• Top 10 machines
• Number of wins
• Number of draws
• Number of winless machines

(g) One suggestion from previous semesters is to have a “Battle Royale”, in which each student in the class nominates a particular machine, and a single game is played in which all machines compete at once. The object is to see which machine can avoid termination for the longest time (making this a bit like “The Hunger Games” if you are familiar with it). In other words, the objective of each machine is not to score the most points, but to avoid termination. To make this fair, we would need to require each machine to contain a platypus somewhere in the fourth row, and that this state be reachable from the kangaroo state (so that the machine can terminate).

Which of your machines, if any, would you choose as your representative in this event? Would you prefer to use some other machine? Explain your answer.

This IT and Computer Science has been solved by our PhD Experts at My Uni Papers. Our Assignment Writing Experts are efficient in providing a fresh solution to this question. We are serving more than 10000+ Students in Australia, the UK, and the US by helping them to score HD in their academics. Our Experts are well-trained to follow all marking rubrics and referencing styles.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.