2 Finite State Parsers and Transducers

In this lecture, we will introduce finite state parsers and transducers. We will

1. learn what the difference between a parser and a recognizer is,

2. implement a finite state parser and a finite state transducer in Prolog, and

3. see an important application of finite state transducers: morphology.

• 2.1 Building Structure while Recognizing
  • 2.1.1 Finite State Parsers
  • 2.1.2 An Example
  • 2.1.3 Separating out the Lexicon

• 2.2 Finite State Transducers
  • 2.2.1 What are Finite State Transducers?
  • 2.2.2 FSTs in Prolog

• 2.3 An Application: Morphology
  • 2.3.1 Morphology
  • 2.3.2 Morphological Parsing
  • 2.3.3 From the Surface to the Intermediate Form
  • 2.3.4 From the Intermediate Form to the Morphological Structure
  • 2.3.5 Combining the two Transducers
  • 2.3.6 Putting it in Prolog
  • 2.3.7 Further Reading

• 2.4 The Complete Programs

• 2.5 Practical Session

• 2.6 Exercises