Links to the lecture slides will become live at the time of the lecture in question.
Should you wish to look at the material in advance of the lecture,
feel free to look at
last year's slides.
These are not guaranteed to be identical to this year's slides,
but in practice the content will be mostly the same.
Week | Lectures | Tutorials | Practicals | Assignments | Readings |
1 | Sep 17: Lecture 1: Introduction and Course Administration (MC+SC), Intro to 2nd Year, Student Support
Sep 19: Lecture 2: Course Roadmap (MC+SC).
Sep 21: Lecture 3: Finite Automata (MC).
|
-- |
-- |
-- |
Kozen chapters 2,3,5;
J&M[2nd Ed] chapters 1, 2 (sec 2.2), 16 (intro and sec 16.1);
Wikipedia: Chomsky (see Note 1) |
2 | Sep 24: Lecture
4: Constructions on Finite Automata (MC).
Sep 26: Lecture
5: Regular Expressions and Kleene's Theorem (MC).
Sep 28: Lecture
6: Applications to String and Pattern Matching (MC).
|
-- |
-- |
-- |
Kozen chapters 6, 4, 13-14, 7, 8, 9;
J&M[2nd Ed] sections 2.1, 2.3 (brief).
|
3 | Oct 01: Lecture
7: Lexing and Other Applications (MC).
Oct 03: Lecture
8: The Pumping Lemma: limitations of regular languages (MC).
Oct 05: Lecture
9: Context-free Languages (SC).
|
Tutorial 1 |
Lab 1: Introduction to Python/NLTK, Part I |
-- |
Kozen chapter 5, 9;
J&M chapter 2; chapter 16.2;
Vidal et al. 2005 |
4 | Oct 08: Lecture
10: Pushdown Automata (MC).
Oct 10: Lecture
11: LL(1) Predictive Parsing (MC).
Oct 12: Lecture
12: Automatic Generation of LL(1) Parsers (MC).
|
Tutorial 2 |
Lab 2: Introduction to Python/NLTK, Part II |
-- |
Kozen chapters 19, 23, 25 (E, 25, F). Also
old lecture notes relevant to lectures 11-12:
Note 9,
Note 10,
Note 12.
Earlier year's tutorial sheet.
|
5 | Oct 15: Lecture 13:
Fixing Problems with Grammars (MC).
Oct 17: Lecture 13:
Fixing Problems with Grammars cont'd. (MC).
Oct 19: Lecture 14:
Types and Static Type Checking (MC). |
Tutorial 3 |
|
Oct 17: Assignment 1 issued |
Note 11 (of "former" lecture notes),
Kozen chapters 26 and 27;
|
6 | Oct 22: Lecture 15:
Natural language processing, morphology, and finite-state
transducers (SC)
Oct 24: Lecture 16:
Parts of speech in natural language (SC).
Oct 26: Lecture 17:
Part-of-speech Tagging (SC). |
Tutorial 4 |
Lab 3: Support for Assignment 1 |
-- |
J&M sections 3.1--3.7; J&M sections 5.1--5.5, 6.1--6.4;
NLTK: Chapters 3 and 5.
Penn Treebank tagging guide
|
7 | Oct 29: Lecture 18:
Fun with weighted FSTs (SC)
Oct 31: Lecture 19:
Phrase Structure and Parsing as Search (SC)
Nov 02: Lecture
20: The CYK Algorithm (SC)
|
Tutorial 5 |
-- |
Oct 30: Assignment 1 deadline (4pm) |
J&M Chapters 13.4,
NLTK: Chapter 8. Rosenberg, The Hardest Natural Languages |
8 | Nov 05: Lecture 21: The Earley Algorithm; Earley parsing example (SC)
Nov 07: Lecture
22: Probabilistic Context-free Grammars (SC)
Nov 09: Lecture
23: Parameter Estimation and Lexicalisation of PCFGs (SC) |
Tutorial 6 |
-- |
Nov 09: Assignment 2 issued |
J&M Chapters 14 (up to 14.5),
NLTK: Chapter 10 |
9 | Nov 12: Lecture
24: Grammar Writing Exercise (SC)
Nov 14: Lecture
25: Agreement, Types and Natural Language Semantics (SC)
Nov 16: Lecture
26: Computing Semantics (SC) |
Tutorial 7 |
|
-- |
J&M Chapters
17--18; Lecture Notes: Semantics; |
10 | Nov 19: Lecture
27: Complexity of Human Languages (SC)
Nov 21: Lecture
28: Semantics of Programming Languages (MC).
Nov 23: Lecture
29: Context-sensitive languages (MC). |
Tutorial 8 |
Lab 5: Support for Assignment 2 |
-- |
J&M Chapters 16.3--16.4; Kozen chapter 28, 29, 31, 32;
Wikipedia: CSG, Turing |
11 |
Nov 26: Lecture
30: Turing Machines and Linear Bounded Automata (MC).
Nov 28: Lecture 31: Undecidability (MC)
Nov 30: Lecture 32: Revision Lecture (MC+SC)
|
Tutorial 9 |
Extra labs for Assignment 2 support |
Nov 30: Assignment 2 deadline (4pm) |
Hauser et al. (2002) |