This page provides links to the lecture slides and other materials for
Inf2A as it was delivered in Autumn 2013.
Week | Lectures | Tutorials | Practicals | Assignments | Readings |
1 | Sep 17: Lecture 1: Introduction and Course Administration (AS)
Sep 19: Lecture 2: Course Roadmap (JL)
Sep 20: Lecture 3: Deterministic Finite Automata (AS) |
-- |
-- |
-- |
Kozen chapter 1, 2; J&M[2nd Ed] chapter 1, 16 (intro and sec 16.1);
Wikipedia: Chomsky (see Note 1) |
2 | Sep 24: Lecture
4: Non-deterministic Finite Automata (AS)
Sep 26: Lecture
5: Regular Expressions and Kleene's Theorem (AS)
Sep 27: Lecture
6: Applications to Pattern Matching and Lexing (AS) |
-- |
-- |
-- |
Kozen chapter 3, 4, 11, 12, 2 |
3 | Oct 01: Lecture
7: Limitations of Regular Languages (AS)
Oct 03: Lecture
8: Context-free Languages (AS)
Oct 04: Lecture
9: Pushdown Automata (AS) |
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: LL(1) Predictive Parsing (AS)
Oct 10: Lecture
11: Automatic Generation of LL(1) Parsers (AS)
Oct 11: Lecture
12: Fixing Problems with Grammars (AS) |
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 15: Lecture 13:
Types and Static Type Checking (AS)
Oct 17: CAREERS LECTURE
Oct 18: Lecture 14: DFAs and Morphological Parsing (JL) |
Tutorial 3 |
Lab 3: Support for Assignment 1 |
Oct 14: Assignment 1 issued |
Kozen chapters 26 and 27;
J&M sections 3.1--3.7
|
6 | Oct 22: Lecture
15: Parts-of-speech and the Lexicon in Natural Language (JL)
Oct 24: Lecture
16: Part-of-speech Tagging (JL)
Oct 25: Lecture
17: Phrase Structure and Parsing as Search (JL) |
Tutorial 4 |
Lab 4: 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 | Oct 29: Lecture
18: Chart Parsing: The CYK Algorithm (JL)
Oct 31: Lecture
19: Chart Parsing: The Earley Algorithm (JL)
Nov 01: Lecture
20: Probabilistic Context-free Grammars
(JL)
|
Tutorial 5 |
-- |
Oct 28: 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 05: Lecture
21: Parameter Estimation and Lexicalization for PCFGs (JL)
Nov 07: Lecture
22: Agreement and Types in Natural Language
(JL)
Nov 08: Lecture
23: Semantics for Natural Languages (JL) |
Tutorial 6 |
-- |
-- |
J&M Chapters 12.9,
14.10, 17--18;
NLTK: Chapter 10 |
9 | Nov 12: Lecture
24: Computing Natural Language Semantics (JL)
Nov 13: Lecture
25: Complexity and Character of Human Languages (JL)
Nov 15: Lecture
26: Models of Human Parsing (JL) |
Tutorial 7 |
Lab 5: Support for Assignment 2, feedback on Assignment 1 |
Nov 11: Assignment 2 issued |
Lecture Notes: Semantics; |
10 | Nov 19: Lecture
27: Semantics of Programming Languages (AS)
Nov 21: Lecture
28: Context-sensitive languages (AS)
Nov 22: Lecture
29: Turing Machines and Linear Bounded Automata (AS)
|
Tutorial 8 |
Lab 6: Support for Assignment 2 |
-- |
Kozen chapter 28, 29, 31, 32;
Wikipedia: CSG, Turing |
11 | Nov 26: Lecture 30: Undecidability (AS)
Nov 28: Lecture 31: Revision Lecture
|
Tutorial 9 |
Extra labs for Assignment 2 support |
Nov 28: Assignment 2 deadline (4pm) |
Hauser et al. (2002) |