G52MAL Lecture Note Index

All electronic material used during lectures will appear here. In particular, lecture slides and any major pieces of code will be available via this page.

The slides are all in PDF, and there are three versions available for each lecture. The basic version is intended for on-screen viewing only, whereas the 4 up and 9 up versions are mainly intended for printing, putting 4 and 9 slides respectively on each page.

• Lecture Notes 1-up 2-up
• Lecture 1: Administrative Details and Introduction 1-up 4-up 9-up
• Lecture 2: Alphabets, Words and Languages 1-up 4-up 9-up
• Lecture 3: Deterministic Finite Automata (DFAs) 1-up 4-up 9-up
• Lecture 4: Nondeterministic Finite Automata (NFAs) 1-up 4-up 9-up
• Lecture 5: Equivalence between NFAs and DFAs 1-up 4-up 9-up
• Lecture 6: Lazy Subset Construction 1-up 4-up 9-up
• Lecture 7: Lexical Analysis 1-up 4-up 9-up
• Lecture 8: Regular Expressions (REs) 1-up 4-up 9-up
• Lecture 9: Equivalence of Regular Expressions and Finite Automata 1-up 4-up 9-up
• Lecture 10: Minimisation of Finite Automata 1-up 4-up 9-up
• Lecture 11: Proving Languages not to be Regular 1-up 4-up 9-up
• Lecture 12: Pushdown Automata (PDAs) 1-up 4-up 9-up
• Lecture 13: The Language of a PDA 1-up 4-up 9-up
• Lecture 14: Context-Free Grammars (CFGs) 1-up 4-up 9-up
• Lecture 15: The Language of a CFG 1-up 4-up 9-up
• Lecture 16: Equivalence of PDAs and CFGs 1-up 4-up 9-up
• Lecture 17: Derivation Trees and Ambiguity 1-up 4-up 9-up
• Lecture 18: Disambiguating Context-Free Grammars 1-up 4-up 9-up
• Lecture 19: Recursive-Descent Parsing 1-up 4-up 9-up Code
• Lecture 20: Abstract Syntax Trees and Eliminating Left Recursion 1-up 4-up 9-up Code
• Lecture 21: Context-Sensitive Grammars 1-up 4-up 9-up
• Lecture 22: Turing Machines 1-up 4-up 9-up
• Lecture 23: Decidability 1-up 4-up 9-up
• Abstruse Goose 206

---

Last updated 1st February 2012.