COMP6270

Theory of Computation

10 Units

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.

Faculty Faculty of Engineering and Built Environment
School School of Electrical Engineering and Computer Science
Availability Semester 1 - 2017 (Callaghan)
Learning Outcomes

On successful completion of this 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
  • Formal Examination: Formal Examination *

* This assessment has a compulsory requirement.

Contact Hours

Callaghan

Lecture

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

Workshop

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

Compulsory Requirements
  • Course Assessment Requirements: 1. 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.)
Timetable 2017 Course Timetables for COMP6270
Got a question?

Contact us for advice on how to apply, enrol, or for more information.

Ready to start?

Once you’ve read our Application guide you’re ready to apply