Formal Languages and Automata

Description

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.

Availability

Callaghan Campus

  • Semester 1 - 2015

Learning Outcomes

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.

Content

  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

Formal Examination: Examination: Formal *

Written Assignment: Essays / Written Assignments

* 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

Lecture

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

Tutorial

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