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
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.
- Formal Languages
- Safety-Critical Systems
- Proving Programs Correct.
- Finite automata and regular languages
- Push-down automata and context-free languages
- Turing machines and phrase-structured languages; Church-Turing Thesis
- Recursive functions
Good programming skills. Knowledge of discrete mathematics.
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.
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.
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