Computing Theory COSC 1107/1105

Assignment 1: Fundamentals

Assessment Type	Individual 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 Date	Week 6, Sunday 27th August 2023, 11:59pm
Marks	125 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 aⁿ 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

D₁D₂M₁M₂Y₁Y₂Y₃Y₄H₁H₂SESc₁   −  Sc₂

   D₁D₂ are two digits of the day of the date

   M₁M₂ are two digits of the month of the date

   Y₁Y₂Y₃Y₄ are four digits of the year of the date

   H₁ and H₂ 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)¹

   S₁ and S₂ are the total score for each team in the match (separated by the character −)

Note that D₁ can only be 0, 1, 2 or 3, M₁ can only be 0 or 1 and Y₁ 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 H₁ and H₂, scribes obeyed the rule that these would be strictly in alphabetical order. Hence H₁ could only be one of {e, g, p} and H₂ 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.

¹The 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 M₁ 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 H₁H₂S above). Explain how you derived your grammar and why it is correct.                                                                                                      (4 marks).

• Finite  State  Automata (18 marks)

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

• Give three examples of strings in L(M₁) of length at least 8. There must be at least one example for which execution finishes in the state q₅, and similarly for q10 and q₁₉.                                                                                                             (3 marks)
  • Explain why M₁ 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(M₁)? Explain your answer. (4 marks)
  • Is it possible to create an equivalent machine M₂ with fewer transitions or states than M₁?  Explain your answer.  Note that by equivalent we mean L(M₁)   =  L(M₂).                                                                                                         (4 marks)
  • Consider the machine M₃ which is derived from M₁ as follows. Is M₃ equivalent to M₁? Explain your answer.                                                                                                      (4 marks)

   Delete all transitions from state q₅.

   Add the transition δ(q₅, λ) = q₁.

   Delete all transitions from state q₁₀.

   Delete the transition  δ(q₁₅, λ) = q₁₁.

   Delete the transition  δ(q₁₉, λ) = q₁₅.

   Add the transition δ(q₁₉, 3) = q₁₂.

• Pushdown Automata (15 marks)

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

Give a PDA M₅ such that L(M₅) =   aⁱb^jc^kb^la^m     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 M₆ 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 M₇ obtained from M₆ by deleting the transitions δ(q₁, c) = (c, R, q₁) and δ(q₁, Y ) = (Y, R, q₁). Is M₇ equivalent to M₆? Explain your answer.                                                                                                      (4 marks)
  • Consider now the Turing machine M₈ obtained from M₆ adding the transition

δ(q₃, a) = (a, R, q₃). Is M₈ equivalent to M₆? 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.² 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)

n	Matches	Estimated time
100
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.

	Standard	Tree	Green	Short	Long	Tiebreaker
Time
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).