A Project Seminar
Martin Kay
An introduction to complexity theory and the core algorithms for (non-statistical) computational linguistics. String searchng, suffix trees and arrays, finite-state technology and morphological analysis, backtracking and chart parsers and generators for context-free and unification grammars.
Slides:
Complexity (PDF)
String Search (PDF)
Finite-state Automata
- Motivation (PDF)
- Basic Mathematics (PDF)
English Morphgrapemic Example (Text)
Contex-free Grammar (PDF)
- A large set of slides on building suffix trees (PDF)
Suffix Arrays (PDF)
CKY Parsing (PDF)
Earley Algorithm (PDF)