School of Computing and Information Systems
COMP30026 Models of Computation
Assignment 2
Released: 22 Sep. 2023; Deadline: 15 Oct. 2023
Aims & Procedure
The aim of Assignment 2 is to consolidate and build upon your understanding of automata theory
and languages, and different forms of reasoning. Moreover, this assignment should help you develop
skills in analysis and formal reasoning about complex concepts.
You are required to solve the questions individually. The total amount of marks on this
assignment is 90. The marks listed on each question do not always reflect the difficulty. We aim
to ensure that anyone with a basic comprehension of the subject matter receives a passing mark.
Getting full marks is intended to be considerably more difficult; the harder questions provide an
opportunity for students to distinguish themselves.
Submission
Questions 1–3 are on Grok, in a module titled “Assignment 2”. Question 4 is described in this
document, and will be submitted on Gradescope.
Late policy
Late submissions are possible, but will receive an initial penalty of 10 marks, and then a further
penalty of 10 marks for every 12 hours late.
If you get stuck
In this assignment, individual work is required, but if you get stuck, you can ask questions on
the discussion board. If your question is simply to clarify some aspect of the assignment, your post
can be public. However, if reveals anything about your attempted solution or approach,
make sure it is private.
Academic honesty
By submitting work for assessment you implicitly declare that you understand the University’s
policy on academic integrity and that the work submitted is your original work. You declare
that you have not been unduly assisted by any other person. Soliciting help from sources other
than the above will be considered cheating and will lead to disciplinary action.
Q4 – Pumping Lemma for Regular Languages
(20 marks) Use the pumping lemma to prove that the language {010 ∣ divides } is not
regular.