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 20: Lecture 1: Introduction and Course Administration (JL+AL)
Sep 22: Lecture 2: Course Roadmap (JL+AL).
VIDEO
Sep 23: Lecture 3: Finite Automata (JL).
VIDEO |
-- |
-- |
-- |
Kozen chapters 2,3,5,6; J&M[2nd Ed] chapters 1, 2 (sec 2.2), 16 (intro and sec 16.1);
Wikipedia: Chomsky (see Note 1) |
2 | Sep 27: Lecture
4: Constructions on Finite Automata (JL).
VIDEO
Sep 29: Lecture
5: Regular Expressions and Kleene's Theorem (JL).
VIDEO
Sep 30: Lecture
6: Applications to String and Pattern Matching (JL).
VIDEO |
-- |
-- |
-- |
Kozen chapter 3, 4, 11, 12, 2 |
3 | Oct 04: Lecture
7: Lexing and Other Applications (JL).
VIDEO
Oct 06: Lecture
8: The Pumping Lemma: limitations of regular languages (JL).
VIDEO
Oct 07: Lecture
9: Context-free Languages (JL).
VIDEO |
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 11: Lecture
10: Pushdown Automata (JL).
VIDEO
Oct 13: Lecture
11: LL(1) Predictive Parsing (JL).
VIDEO (sound mostly OK despite mic failure)
Oct 14: Lecture
12: Automatic Generation of LL(1) Parsers (JL).
VIDEO |
Tutorial 2 |
Lab 2: Introduction to Python/NLTK, Part II |
-- |
Earlier year's lecture notes relevant lectures 10 and 11:
Note 9,
Note 10,
Note 12.
Earlier year's tutorial sheet.
|
5 | Oct 18: Lecture 13:
Types and Static Type Checking (JL).
VIDEO
Oct 20: Lecture 14:
Fixing Problems with Grammars (JL).
VIDEO
Oct 21: Lecture 15: Natural language processing, morphology, and
finite-state transducers (AL) |
Tutorial 3 |
|
Oct 18: Assignment 1 issued |
Kozen chapters 26 and 27;
J&M sections 3.1--3.7
|
6 | Oct 25: Lecture
16: Parts of speech in natural language (AL). VIDEO
Oct 27: Lecture
17: Part-of-speech Tagging (AL). VIDEO
Oct 28: Lecture
18: Fun with weigthed FSTs (AL) VIDEO |
Tutorial 4 |
Lab 3: Support for Assignment 1 |
-- |
J&M sections 5.1--5.5, 6.1--6.4;
NLTK: Chapters 3 and 5.
Penn Treebank tagging guide
|
7 | Nov 01: Lecture
19: Phrase Structure and Parsing as Search (AL) VIDEO
Nov 03: Lecture
20: The CYK Algorithm (AL) VIDEO
Nov 05: Lecture
21: The Earley Algorithm
(AL)
|
Tutorial 5 |
-- |
Nov 01: Assignment 1 deadline (4pm) |
J&M Chapters 13.4,
14 (up to 14.5), 16.3--16.4.
NLTK: Chapter 8. Rosenberg, The Hardest Natural Languages |
8 | Nov 08: Lecture
22: Probabilistic Context-free Grammars (AL) VIDEO
Nov 10: Lecture
23: Probability; Agreement and Types in Natural Language
(AL) VIDEO
Nov 11: Lecture
24: Semantics for Natural Languages (AL) VIDEO |
Tutorial 6 |
-- |
Nov 11: Assignment 2 issued |
J&M Chapters 12.9,
14.10, 17--18;
NLTK: Chapter 10 |
9 | Nov 15: Lecture
25: Computing Natural Language Semantics (AL) VIDEO
Nov 17: Lecture
26: Complexity of Human Languages (AL) VIDEO
Nov 18: Lecture
27: Complexity (continued); Models of Human Parsing (CCG example) (AL) VIDEO |
Tutorial 7 |
Lab 4: Support for Assignment 2, feedback on Assignment 1 |
-- |
Lecture Notes: Semantics; |
10 | Nov 22: Lecture
28: Semantics of Programming Languages (JL).
VIDEO
Nov 24: Lecture
29: Context-sensitive languages (JL).
VIDEO
Nov 25: Lecture
30: Turing Machines and Linear Bounded Automata (JL).
VIDEO
|
Tutorial 8 |
Lab 5: Support for Assignment 2 |
-- |
Kozen chapter 28, 29, 31, 32;
Wikipedia: CSG, Turing |
11 | Nov 29: Lecture 31: Undecidability (JL)
Dec 01: Lecture 32: Revision Lecture (JL+AL) VIDEO
|
Tutorial 9 |
Extra labs for Assignment 2 support |
Dec 02: Assignment 2 deadline (4pm) |
Hauser et al. (2002) |