Available in 2021
Course code



10 units


2000 level

Course handbook


This course introduces formal models of computation and the problems that they can solve. It presents Turing machines and equivalent models of computation. It also discusses the fundamental limitations of what can be computed. It covers finite state machines, regular expressions and regular grammars as well as context-free languages and grammars and non-context free grammars. It includes algorithms and decision procedures for regular and context-free languages, Turing machine, decidability and complexity analysis

Availability2021 Course Timetables


  • Semester 1 - 2021

Learning outcomes

On successful completion of the course students will be able to:

1. Explain the importance of automata as modelling tools and apply them to computational problems

2. Explain the role of context-free languages and their limitations

3. Explain the basis of theory of computation, in particular the role of key problems in defining classes of equivalent problems from a computational perspective

4. Discuss the limitations of computational procedures


  1. Preliminaries (review of basic mathematical concepts)
  2. Finite automata
  3. Language theory
  4. Turing machine
  5. Decidability and reducibility
  6. Complexity theory 

Assumed knowledge

MATH1510 Discrete Mathematics, SENG1120 Data Structures

Assessment items

Written Assignment: Assignment 1

Written Assignment: Assignment 2

In Term Test: Class Test 1

In Term Test: Class Test 2

Online Learning Activity: Online multiple choice questions

Formal Examination: Formal Examination *

* This assessment has a compulsory requirement.

Compulsory Requirements

In order to pass this course, each student must complete ALL of the following compulsory requirements:

Course Assessment Requirements:

  • Formal Examination: Minimum Grade / Mark Requirement - Students must obtain a specified minimum grade / mark in this assessment item to pass the course. - Students whose overall mark in the course is 50% or more, but who score less than 40% in the compulsory item and thus fail to demonstrate the required proficiency, will be awarded a Criterion Fail grade, which will show as FF on their formal transcript. However, students in this position who have scored at least 25% in the compulsory item will be allowed to undertake a supplementary 'capped' assessment in which they can score at most 50% of the possible mark for that item.

Contact hours



Face to Face On Campus 2 hour(s) per Week for Full Term


Face to Face On Campus 2 hour(s) per Week for Full Term starting in week 2

The University of Newcastle acknowledges the traditional custodians of the lands within our footprint areas: Awabakal, Darkinjung, Biripai, Worimi, Wonnarua, and Eora Nations. We also pay respect to the wisdom of our Elders past and present.