E-Book Overview
The name Computational Linguistics already suggests that this displine comprises two related objects of research: natural language (NL) is studied and operational methods are developed. Both fields are investigated in their own right and divide into various topics. This course introduces a variety of NL phenomena together with appropriate implementations in the programming language Prolog. The topics dealt with are among others Morphology, Finite State Techniques, Syntax, Context Free Grammars, Parsing, and Semantics Construction.
E-Book Content
Algorithms for Computational Linguistics Kristina Striegnitz Patrick Blackburn Katrin Erk Stephan Walter Aljoscha Burchardt Dimitra Tsovaltzi
MiLCA, Saarbrücken
Abstract The name Computational Linguistics already suggests that this displine comprises two related objects of research: natural language (NL) is studied and operational methods are developed. Both fields are investigated in their own right and divide into various topics. This course introduces a variety of NL phenomena together with appropriate implementations in the programming language Prolog. The topics dealt with are among others Morphology, Finite State Techniques, Syntax, Context Free Grammars, Parsing, and Semantics Construction.
MiLCA, Computerlinguistik, Universität des Saarlandes, Saarbrücken, Germany May 2003 This course is also available online:
http://www.coli.uni-sb.de/ albu/courses/coal/
Contents 1 Finite State Automata
1
1.1 Finite State Recognizers and Generators . . . . . . . . . . . . .
1
1.1.1 A Simple Machine that can laugh . . . . . . . . . . . . . .
1
1.1.2 Finite State Automata . . . . . . . . . . . . . . . . . . . .
3
1.2 Some Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3 Deterministic vs.