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
e made via announcements
elevant discussion forums.
Due Date Week 6, Sunday 28th August 2022, 11:59pm
Marks 130 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 you
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, ou
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 a
eviate 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
ains!).
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!
1. Regular expressions and languages (17 marks)
The game of Buckitch has a history that goes back centuries, including being played
at the legendary school Warthogs. Matches at Warthogs began shortly after the
first recorded match in 1317, and have been held regularly since between the fou
Warthogs houses of Liongate, Crowfoot, Serpentine and Dragon
eath. Records
of all Buckitch matches at Warthogs since 1317 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 (l, c, s, and d respectively) in the
match, and including the date, winner and scores. Such strings were written as
follows.
D1D2M1M2Y1Y2Y3Y4H1H2WS1S2S3S4S5S6
where
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
W is the character for the winning house
S1S2S3 is the three-digit winning house’s score
S4S5S6 is the three-digit losing house’s score
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. Note also that the score is always a multiple of 10, and can be assumed to be
no more than 990.
Buckitch matches are never drawn or incomplete. If no result is possible on the
given day, the winner is determined by random choice. This means it is possible
for the winning and losing score to be the same.
Scores were written one after the other on the parchment as one enormous string. In
order to analyse the history of Buckitch, it is necessary to write regular expressions
to identify specific matches of interest somewhere in this string.
(a) Give a regular expression for the following cases.
i. Any match in the year 1737 won by Dragon
eath. (1 mark)
ii. Any match on the 1st of April in which either score was XXXXXXXXXXmark)
iii. Any match involving Liongate after XXXXXXXXXXmarks)
iv. Any sequence of wins for Crowfoot. (3 marks)
v. Any sequence of losses in August for Serpentine before XXXXXXXXXXmarks)
(b) Is it possible to give a regular expression for the following cases? Explain
either why it is possible or why it is not.
i. Any match in which the scores are equal. (2 marks)
ii. The longest losing sequence for each house. (2 marks)
iii. Any match played on a date which is a palindrome. (2 marks)
2
2. Grammars (18 marks)
(a) Consider the G1 grammar below.
S → aaSb | A
A → cAc | B
B → ddB | λ
i. Give a derivation of a string in L(G1) which contains at least 4 occu
ences
of b. (2 marks)
ii. Give a derivation of length at least 8 of a string in L(G1). (2 marks)
iii. Is λ ∈ L(G1)? Explain your answer. (1 marks)
iv. Express L(G1) in set notation. (3 marks)
v. Let G2 be the grammar obtained from G1 by adding the rule S → AbS
to G1. This makes G2 as below. What is L(G2)? How does it differ from
L(G1)? (3 marks)
S → aaSb | Ab | AbS
A → cAc | B
B → ddB | λ
(b) Warthogs School provides its students with identifiers of the form N+I+H
where
N is a 5-digit number over {1, 3, 5, 7, 9}
I is a string over {a, b, e, f} of length at least four in which the number of
a’s and f ’s is the same
H is a string of length at least two consisting solely of one of the characters
{l, c, s, d}
For example, 13579+baaefef+llll and 53399+fafa
e+ccc are valid identi-
fiers, whereas 13579+baefef+llll and 53399+fafa
e+csl are not.
i. Give a grammar whose language contains all valid identifiers, and only
such identifiers. (2 marks)
ii. Give the derivation in your grammar for the two valid identifiers above.
(2 marks)
iii. Warthogs School now decrees that N can be at least 5 digits long or more,
ut must contain at least one 7. Give a grammar for this new version of
identifiers. (3 marks)
3
3. Finite State Automata (18 marks)
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 for which execution finishes in the state q6, and similarly
for q9 and q12. (3 marks)
(b) Explain whyM1 is nondeterministic. Do not include any ’missing’ cases in you
explanation (i.e. cases in which there is no transition for a given combination
of state and input). (3 marks)
(c) What is L(M1)? Explain your answer. (4 marks)
(d) Is it possible to create an equivalent machine M2 with fewer transitions o
states than M1? Explain your answer. (4 marks)
(e) Consider the machine M3 which is derived from M1 as follows. Is L(M3) the
same as L(M1)? Explain your answer. (4 marks)
Delete state q2 (and transitions δ(q0, λ) = q2 and δ(q2, 0) = q10).
Delete the transition δ(q0, λ) = q3.
Delete the transition δ(q0, λ) = q1.
Add the transition δ(q0, 0) = q3.
Add the transition δ(q0, 0) = q1.
4
https:
mit.instructure.com/files/ XXXXXXXXXX/download?download_frd=1
4. Pushdown Automata (12 marks)
Consider the PDA M1 below. You can download this from Canvas here.
(a) Show the execution of the strings da
a,
dcb , cacadcbc and abcdddcbadd
in M1. (4 marks)
(b) What is L(M1)? (use set notation). Explain your answer. (4 marks)
(c) Construct a PDA M2 such that L(M2) = {aibicjdj | i, j ≥ 0}. (2 marks)
(d) Explain why there is no PDA for the language {aibjcidj | i, j ≥ 0} (2 marks)
5
https:
mit.instructure.com/files/ XXXXXXXXXX/download?download_frd=1
5. Turing machines (20 marks)
Consider the Turing machine M1 below. You can download this from Canvas here.
(a) What is L(M1)? Explain your answer. 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)
(b) Consider the Turing machine M2 which is obtained from M1 by deleting the
transition below from M1. What is L(M2)? How does this compare to L(M1)?
Explain your answer. (3 marks)
State Input Output Direction New State
q6 c c L q6
(c) Recall the game of Buckitch from Question 1 and its method of recording
scores as strings. Give a Turing machine M3 which accepts a string recording
a single match if any one of the following conditions holds. (6 marks)
Changing one digit in one of the scores will make them the same. Fo
example 130 and 180 satisfy this; 270 and 480 do not, and neither do 310
and 140.
The scores were a substring of the date.
The match was won by Dragon
eath either on the 17th day of a month
or a year ending in 17 but not both.
(d) Is M3 deterministic? Explain your answer. (2 marks)
6
https:
mit.instructure.com/files/ XXXXXXXXXX/download?download_frd=1
(e) Explain how you could use M3 as the basis for a Turing machine M4 which
would output which of the above three conditions was satisfied by a given
string. You do not need to explicitly construct M4, but describe how it would
e done. (2 marks)
(f) 17th July in years which end in 17 (such as 1917 or 2017) are very special
dates in Buckitch history known as Seventeens. On such days a marathon
tournament has been played at Warthogs since 1317, with all four houses
playing as many matches as they can in that 24-hour period from midnight
to midnight. The results of each match are recorded as above. On July 18th
2017, Serpentine made the outrageous claim to have won more matches in
Seventeens than the other three houses combined, but produced no evidence
whatsoever to back up this claim. Accordingly, the Head of Warthogs, Pumbaa
the Magnificent, has asked you to design a Turing machine which, given as
input a string containing the entire records of Buckitch at Warthogs, will
output the number of matches played and won by each house on Seventeens.
Explain how you would design such a Turing machine M5. There is no need to
explicitly construct this machine. You may use any variety of Turing machine
that you wish, with particular regard to making the machine as simple as
possible to understand (as it will certainly be keenly scrutinised by the Head
of Serpentine, Scarface Shape). (3 marks)
6. Universality (20 marks)
Universal Turing machines are often discussed, but are rarely