MT4512 Automata, Languages and Complexity

2024 to 2025 Semester 2

Curricular information may be subject to change

Further information on which modules are specific to your programme.

Key module information

SCOTCAT credits

The Scottish Credit Accumulation and Transfer (SCOTCAT) system allows credits gained in Scotland to be transferred between institutions. The number of credits associated with a module gives an indication of the amount of learning effort required by the learner. European Credit Transfer System (ECTS) credits are half the value of SCOTCAT credits.

SCQF level

SCQF level 10

The Scottish Credit and Qualifications Framework (SCQF) provides an indication of the complexity of award qualifications and associated learning and operates on an ascending numeric scale from Levels 1-12 with SCQF Level 10 equating to a Scottish undergraduate Honours degree.

Availability restrictions

This module will run in alternate (even) years: 2020-21, 2022-23, 2024-25, etc. Not available to Joint Honours Mathematics and Computer Science students.

Planned timetable

10am Mon (even weeks), Tue and Thu

This information is given as indicative. Timetable may change at short notice depending on room availability.

Module coordinator

Prof C M Roney-Dougal

This information is given as indicative. Staff involved in a module may change at short notice depending on availability and circumstances.

Module Staff

Dr Sophie Huczynska

This information is given as indicative. Staff involved in a module may change at short notice depending on availability and circumstances.

Module description

This module concerns formal languages, and the machines that recognise them. It begins with regular languages and finite state machines, both deterministic and non-deterministic. We then go on to study pushdown automata and context-free grammars. Turing machines are introduced, followed by studies on decidability and the Halting problem. In the final third of the course, we introduce big-O notation, and study the complexity classes P, NP, co-NP, NP-hard, etc..

Relationship to other modules

Pre-requisites

BEFORE TAKING THIS MODULE YOU MUST PASS MT2504 OR ( (PASS CS2001 OR PASS CS2101) AND PASS CS2002 )

Anti-requisites

YOU CANNOT TAKE THIS MODULE IF YOU TAKE CS3052

Assessment pattern

90% exam, 10% continual assessment

Re-assessment

Oral examination = 100%

Learning and teaching methods and delivery

Weekly contact

2.5 lectures (X 10 weeks), 1 tutorial (X 10 weeks).

Intended learning outcomes

Design finite state automata, pushdown automata and Turing machines to recognise (or decide) appropriate languages
Use the Pumping Lemmas to prove that languages are not regular or not context free, and the Halting Theorem to prove that languages are undecidable
Prove that a given language is in complexity class P or NP, and show that a given language is NP-complete
State and prove all key results from lectures