Computing Theory COSC 1107/1105
Assignment 1: Fundamentals
Assessment TypeIndividual assignment. Submit online via Canvas → As- signments → Assignment 1. Marks awarded for meeting re- quirements as closely as possible. Clarifications/updates may be made via announcements/relevant discussion forums.Due DateWeek 6, Sunday 27th August 2023, 11:59pmMarks125 worth 15% of your final assessment
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.
2 Assessment details
A Note on Notation of Regular Expressions: Unfortunately there isn’t a uniformly accepted standard notation for regular expressions. Given we are using JFLAP, our notation should be as consistent as practicable with that, but that also means some things get quite cumbersome. 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 an 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 now obvious!
Regular expressions and languages (15 marks)
The game of Buckscratch has a history that goes back centuries, including being played at the legendary school Pigspimple. Matches at Pigspimple began shortly after the first recorded match in 1177, and have been held regularly since between the four Pigspimple houses of Echidna, Goanna, Possum and Wallaby. Records of all Buckscratch matches at Warthogs since 1177 have been kept in a handwritten archive. To save precious parchment and ink, the records of each match were kept as a string, using one character for each house (e, g, p,, and w respectively) in the match, and including the date, winner and scores. Such strings were written as follows.
where
D1D2M1M2Y1Y2Y3Y4H1H2SESc1 − Sc2
D1D2 are two digits of the day of the date
M1M2 are two digits of the month of the date
Y1Y2Y3Y4 are four digits of the year of the date
H1 and H2 are the characters representing the two houses involved
S is the sequence of scores in the match
E is either the character q or the character t (indicating what caused the match to end)1
S1 and S2 are the total score for each team in the match (separated by the character −)
Note that D1 can only be 0, 1, 2 or 3, M1 can only be 0 or 1 and Y1 can only be 1 or 2.
The sequence of scores is in the format of the character representing one house, followed by a sequence of consecutive scores for that house. Each score can either be 1, 2 or 3 (referred to as a “single”, “double” and “triple” respectively. For example, a sequence of scores for a match between Echidna (e) and Wallaby (w) could be e131111w22e13123w2111111.
When recording H1 and H2, scribes obeyed the rule that these would be strictly in alphabetical order. Hence H1 could only be one of {e, g, p} and H2 could only be one of {g, p, w}.
Scores were written one after the other on the parchment as one enormous string. In order to analyse the history of Buckscratch, 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 sometime 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.
1The rules of Buckscratch are unclear and subject to debate, but it seems that there were at least two ways in which matches came to an end.
Give a regular expression for the following cases.Any match taking place on July 7th involving Echnida or Goanna. (1 mark)Any match on or after January 1st 1900 in which the end event was q. (1 marks)Any ”syntactically correct” record of a match. This means the recorded entry must have M1 being either 0 or 1, the houses must be one of the four above, and scores must consist of digits. Anything not ”syntactically correct” must be an obvious error, such as the date 496618888 or the score sequence e1e1e1d2d2. (3 marks)Any match on a day in August involving Goanna in which the opposition scored at least three triples. (2 marks)
Is it possible to give a regular expression for the following? Explain either why it is possible or why it is not.Any match in which either of the scores is a palindrome. (2 marks)The longest sequence of consecutive matches for each house. (2 marks)A sequence of matches in which no triples were scored by either side. (2 marks)
Determining which house was the first to reach 100 victories. (2 marks)
Grammars (15 marks)
Consider the grammar below.
S → SHN | λ N → D | DN
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
H → e | g | p | w
Give derivations in G of the strings e111g3, e1g2p3w1 and p1111 (3 marks)Is λ ∈ L(G)? Explain your answer (1 mark)Express L(G) in set notation. Explain why your answer is correct. (4 marks)Sneaky Wobbler, the legendary housemaster of Goanna house at Pigspim- ple, claims that this grammar correctly specifies the sequence of scores in a Buckscratch match (i.e. the sequence labelled S above). Explain why Sneaky’s claim is not correct. (3 marks)
Give a (correct) grammar for specifying the two houses and the possible se- quences of scores (i.e. the string labelled H1H2S above). Explain how you derived your grammar and why it is correct. (4 marks).
Finite State Automata (18 marks)
Consider the finite state automaton M1 below. You can download this from Canvas here.
Give three examples of strings in L(M1) of length at least 8. There must be at least one example for which execution finishes in the state q5, and similarly for q10 and q19. (3 marks)
Explain why M1 is non-deterministic. Give at least four examples of states for which there is more than one successor state for some input in your explana- tion. (3
marks)
What is L(M1)? Explain your answer. (4 marks)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). (4 marks)
Consider the machine M3 which is derived from M1 as follows. Is M3 equivalent to M1? Explain your answer. (4 marks)
Delete all transitions from state q5.
Add the transition δ(q5, λ) = q1.
Delete all transitions from state q10.
Delete the transition δ(q15, λ) = q11.
Delete the transition δ(q19, λ) = q15.
Add the transition δ(q19, 3) = q12.
Pushdown Automata (15 marks)
Consider the pushdown automaton M4 below. You can download this from Canvas here.
Give a PDA M5 such that L(M5) = aibjckblam i+j < l+m, i, j, k, l, m 0 . Explain why your machine is correct. (4 marks)
Turing machines (12 marks)
Consider the Turing machine M6 below. You can download this from Canvas here.
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. (4 marks)Consider the Turing machine M7 obtained from M6 by deleting the transitions δ(q1, c) = (c, R, q1) and δ(q1, Y ) = (Y, R, q1). Is M7 equivalent to M6? Explain your answer. (4 marks)
Consider now the Turing machine M8 obtained from M6 adding the transition
δ(q3, a) = (a, R, q3). Is M8 equivalent to M6? Explain your answer. (4 marks)
Get Creative! (20 marks)
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 the Adobe Creative Cloud suite, to which all RMIT students have access. You can find the details about the Adobe Creative Cloud at this link.
There are many aspects of Computing Theory that allow you to show your in- vestigative 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 rele- vant 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 Lang- ton’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 re- striction to a one-dimensional 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 pro- saic). 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.
The Platypus game For this task you will need to be familiar with the Platypus game. (30 marks)
You have been allocated a number of machines, based on your student number.
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.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 score 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. (2 marks)Examine your top 10 machines. Are they any key similarities or differences between them? In your analysis, what makes these the top performers? (2 marks)How does your top 10 change if the ranking is based on overall points for, rather than as above? (2 marks)
Examine your bottom 10 machines. Were there any machines without a win? What is the difference between these machines and the top perform- ers? (2
marks)
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. (2 marks)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 took 156.5 seconds on a Windows 10 desktop with an Intel i7 processor and 16GB of RAM.” (2 marks)
A tournament of this form involving n teams requires n(n + 1)/2 matches.2 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. (3 marks)
nMatchesEstimated time100 1,000 10,000 100,000 1,000,000
Calculate the largest Platypus tournament you can play on your machine in 3 hours, ie 3 60 60 = 10, 800 seconds. Use the value calculated above for how long it takes you to play a match. (2 marks)
The Platypus game is entirely deterministic, and hence a little boring as en- tertainment. Suggest at least two ways in which the game can be extended to increase player involvement in the game. (4 marks)
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 Report your results in a table like this.
StandardTreeGreenShortLongTiebreakerTime Top 10 Wins Draws Winless machines
You should identify your top ten machines by the overall number, ie in the range 1 to 268,435,456. (5 marks)
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 Hungar Games” if you are familiar with it). In other words, the objec- tive 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 platy- pus somewhere in the fourth row, and that this state be reachable from the kangaroo state (so that it is possible for the machine to 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. (4 marks)
3 Submission
You should submit the following.
A PDF file containing your answers to the questions.
All .csv files generated by running your tournaments.
No other file formats will be accepted.
4 Rubric
Your assignment will be graded in accordance with the rubric in Canvas (which will be available shortly).
The post Computing Theory COSC appeared first on Universal Assignment.