Formal Languages and Automata


Introduces Formal Languages and their application to Safety-Critical Systems and Proofs of Correctness.

Discusses automata and their relationship to regular, context-free and phrase-structure languages. The computability theory is presented, including Turing machines, decidability and recursive functions.



  • Semester 1 - 2016

Learning Outcomes

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

1. understand the importance of automata as a modelling tool of computational problems

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

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

4. understand the limitations of computational procedures.


  1. Formal Languages
  2. Safety-Critical Systems
  3. Proving Programs Correct.
  4. Finite automata and regular languages
  5. Push-down automata and context-free languages
  6. Turing machines and phrase-structured languages; Church-Turing Thesis
  7. Decidability
  8. Recursive functions

Assumed Knowledge

Good programming skills. Knowledge of discrete mathematics.

Assessment Items

Written Assignment: Assignment 1

Written Assignment: Assignment 2

In Term Test: Class Test 1

In Term Test: Class Test 2

Formal Examination: Formal Examination *

Quiz: Online multiple choice questions

* 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 must obtain 40% in the final exam to pass the course.

Contact Hours



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


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