Programme And Module Handbook
Course Details in 2024/25 Session

If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title LC Theories of Computation
SchoolComputer Science
Department Computer Science
Module Code 06 35393
Module Lead Dr Paul Levy
Level Certificate Level
Credits 20
Semester Semester 2
Co-requisites LC Mathematical and Logical Foundations of Computer Science - (06 35324)
Restrictions Incoming exchange students should have the equivalent of grade A at A-level in Mathematics.
Contact Hours Lecture-44 hours
Practical Classes and workshops-22 hours
Guided independent study-134 hours
Total: 200 hours
Description Computers have been used to solve an astonishing range of different problems, but this does not mean that they can be used to solve all possible problems: some cannot be solved efficiently, and some cannot be solved at all. In this module, we will introduce a set of principles and techniques for formalising computation and computability to understand what problems can be solved, how efficiently they can be solved, and what problems cannot be solved. We will develop mathematical models of computations using ideas such as sutomata theory (including Turing machines), of formal languages using ideas such as regular expressions and grammars, and will conclude by considering the notions of non-computability and complexity.
Learning Outcomes By the end of the module students should be able to:
  • Explain and apply mathematical models of computations
  • Explain and apply concepts from automata theory, formal language theory, computability theory and complexity theory
  • Describe and use the connection between finite automata and regular language
  • Explain non-computability and undecidability issues
Assessment 35393-01 : Continuous Assessment : Coursework (20%)
35393-03 : Exam : Exam (Centrally Timetabled) - Written Unseen (80%)
Assessment Methods & Exceptions Assessment:
Examination (80%),
Continuous Assessment (20%)

Examination (100%)
Other (Edgbaston version of Dubai module 35392)
Reading List