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)

Suffix Trees (PDF) (Program)

- A large set of slides on building suffix trees (PDF)

Suffix Arrays (PDF)

CKY Parsing (PDF)

Earley Algorithm (PDF)