Not currently offered
Course code

COMP6270

Units

10 units

Level

6000 level

Course handbook

Description

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.


Availability

Not currently offered.

This Course was last offered in Semester 1 - 2020.


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.

5. explore a research aspect in the theory of computation.


Content

  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, SENG6120 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
Compulsory Requirement: Pass requirement 40% - Must obtain 40% in this assessment item to pass the course.

Course outline

Course outline not yet available.