1 Finite State Automata

In this lecture we will

1. introduce finite state automata and show how they can be used to recognize and generate (formal) languages,

2. explain the difference between deterministic and non-deterministic automata,

3. say something about the limitations of finite state methods,

4. and finally, we will write a simple Prolog recognizer/generator for finite state automata.

• 1.1 Finite State Recognizers and Generators
  • 1.1.1 A Simple Machine that can laugh
  • 1.1.2 Finite State Automata

• 1.2 Some Examples

• 1.3 Deterministic vs. Non-deterministic FSAs

• 1.4 FSAs in Prolog
  • 1.4.1 Representing FSAs in Prolog
  • 1.4.2 A Recognizer and Generator for FSAs without Jump Arcs
  • 1.4.3 A Recognizer and Generator for FSAs with Jump Arcs

• 1.5 Finite State Methods in Computational Linguistics and their Limitations

• 1.6 The Prolog Files

• 1.7 Practical Session

• 1.8 Exercises and Solutions
  • 1.8.1 Exercises

• 1.9 Further Reading