Formal Languages and Automata

Course code COMP6270Units 10Level 6000Faculty of Engineering and Built EnvironmentSchool of Electrical Engineering and Computer Science

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.

Available in 2014

Callaghan CampusSemester 1
Previously offered in 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006
Objectives(1) To introduce students to the structure of automata and formal languages
(2) To give students understanding of the limitations on the capabilities of computers
(3) To give students an understanding of Formal Languages and their application to Safety-Critical Systems and Proofs of Correctness.
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
Replacing Course(s)N/A
TransitionN/A
Industrial Experience0
Assumed KnowledgeGood programming skills.
Knowledge of discrete mathematics.
Modes of DeliveryInternal Mode
Teaching MethodsLecture
Tutorial
Assessment Items
Essays / Written Assignmentsas per course outline
Examination: FormalA final examination according to the university's examination timetable.
Contact HoursTutorial: for 2 hour(s) per Week for Full Term
Lecture: for 3 hour(s) per Week for Full Term
Compulsory Components
Compulsory Course ComponentStudents must obtain 40% in the final exam to pass the course.
Student achieving >25% but less that 40% will be offered an alternate assessment if, and only if, all other assessment items have been submitted.
Students obtaining <25% will not be offered an alternate assessment, and will fail the course, unless students have submitted Adverse Circumstances in accordance with the Adverse Circumstances Policy.
Timetables2014 Course Timetables for COMP6270