Skip to main content

Unit information: Theory of Computation in 2019/20

Please note: Due to alternative arrangements for teaching and assessment in place from 18 March 2020 to mitigate against the restrictions in place due to COVID-19, information shown for 2019/20 may not always be accurate.

Please note: you are viewing unit and programme information for a past academic year. Please see the current academic year for up to date information.

Unit name Theory of Computation
Unit code COMS11700
Credit points 10
Level of study C/4
Teaching block(s) Teaching Block 2 (weeks 13 - 24)
Unit director Dr. Steven Ramsay
Open unit status Not open

COMS10003 Mathematical Methods for Computer Scientists, COMS10008 Imperative Programming, COMS10006 Functional Programming.



School/department Department of Computer Science
Faculty Faculty of Engineering


This unit provides an introducion to various classical models of computation, the equivalence of different computational models, and limits on what can be computed in terms of uncomputability and intractability.

Intended learning outcomes

On completion of the unit students will understand: use regular expressions to describe the language accepted by an automaton and state Kleene, convert non-deterministic finite automata to deterministic ones, design automata/machines that accept a given language (e.g. a lexer), design a grammar for a given context-free language and give its Chomsky Normal Form, be able to apply the pumping lemma (for regular and context-free languages), understand the complexity classes P, NP and reductions to NP-complete languages, understand the Church-Turing Thesis and undecidability

Teaching details

20 hours of lectures. Weekly supervised problems classes. A further 70 hours are nominally set aside for coursework, private study, etc.

Assessment Details

Exam, worth 100%

Reading and References

The course text is Introduction to the Theory of Computation, 1st or 2nd edition. The 1st edition is out of print, but still available. All these books are available in the library.

M.Sipser. Introduction to the theory of computation. International Thompson Publishing Company. 1997. ISBN: 053494728X Recommended.

M. Garey and D. Johnson. Computers and intractability: a guide to the theory of NP completeness. W. H. Freeman. 1979. ISBN: 0716710455 Background

J. Truss Discrete mathematics for computer scientists (2nd edition) Addison-Wesley. 1998. ISBN: 0201360616 Background.