Formal Languages and Automata

10 Units

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.

Faculty Faculty of Engineering and Built Environment
School School of Electrical Engineering and Computer Science
Availability Semester 1 - 2016 (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.
  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 *
Contact Hours
  • Lecture: for 3 hour(s) per Week for Full Term
  • Tutorial: for 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 2016 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