1.    Introduction (January 8 – 10)

Overview and motivation
Mathematical Preliminaries
Languages

2.    Finite Automata (January 10 – 15)

Definition
Execution
Regular Languages

3.    Nondeterministic Finite Automata (January 15 – 17 )

Definition
Execution
DFAs and NFAs
The subset construction

4.    Regular Expressions (January 17 – 24)

Definition
Converting REs to NFAs
Converting DFAs to REs
Regular equations
Derivatives of Languages

5.    Properties of Regular Languages (January 24–February 7)

Closure
Periodicity
Minimisation of DFAs
Decision Properties

6.    Context-Free Grammars (February 14)

Context-free languages
Proofs about grammars
Regular grammars
Derivations and parse trees

7.    Pushdown Automata (February 14 – 28)

Language of a PDA
Acceptance by final state, by empty stack
PDAs and CFGs
Deterministic PDAs Ambiguity

8.    Properties of Context-Free Languages (February 28 – March 12)

Chomsky Normal Form
Pumping Lemma
Closure properties
Decision properties

9.    Turing Machines (March 21 – 28)

Computation
Recursively enumerable languages
Recursive languages
Multiple tracks; multiple tapes; nondeterministic; semi-infinite
Multistack machines
Counter machines

10.  Undecidability (March 28 – April 4)

Classes of problems
Problems about TMs
Diagonalisation language
Universal language
Reductions
Properties of RE languages - Rice's Theorem
Post's Correspondence Problem
Problems about CFGs