58勛圖

MT4512 Automata, Languages and Complexity

Academic year

2026 to 2027 Semester 2

Further information on which modules are specific to your programme.

Key module information

SCOTCAT credits

15

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 (weeks 2, 4, 6, 8, 11), Tue & Thr

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

Module Staff

TBD

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

2-hour Written Examination = 90%, Coursework (class test) = 10%

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