Sipser’s Introduction to the Theory of Computation (2nd Edition) is very highly recommended. Honestly, the more I read Sipser, the more I realise that a lot in the module is from that book.
tl;dr of the module is that we’d like to discuss various models of computations that abstract computers (because it’s really quite difficult to reason about actual computers and all their complexity). We start with the simplest (DFAs), then to something more powerful (PDAs), and to the big-boys (Turing Machines).
Order of reading:
Order is a bit confusing because Languages has content from many different sections of the module.
Exam Cramming
DON’T CRAM THIS MODULE!!!!!!!
But if you do…
- Probably not worth looking at “background” sections.
- Just skim and try to answer seminar problems and exam questions from that to test yourself.