Send us a comment.
2.1 Finite-state transition networks 2.2 A notation for networks 2.3 Deterministic FSTNs in Pop11 2.4 Non-deterministic FSTNs in Pop11 2.5 Traversing FSTNs 2.6 Traversing FSTNs in Pop11 2.7 Finite-state transducers 2.8 Limitations of finite-state machines
Finite-state automata (FSAs) are among the simplest computing machines that can be envisaged. They are well understood mathematically, easy to implement and efficient at doing what they do. If an NLP problem can be conveniently solved with a finite-state automaton, then it is probably a good idea to solve it that way. However, FSAs are subject to certain formal limitations that render them ill suited to certain computational linguistic tasks. This chapter provides a fairly comprehensive introduction to these machines and their implementation, indicates possible areas of application and gives some concrete examples of their use, and examines their limitations.
We begin this chapter by presenting finite-state transition networks (FSTNs). An FSTN can be regarded as a neutral description of a language (a set of sequences of symbols), but it can also be interpreted, for instance, as a specification of an FSA to recognize elements of the language or as a specification of an FSA to generate elements of the language. We move on to consider a simple extension to the basic FSTN notation, which then allows networks to be interpreted as finite-state transducers, which are FSAs that can recognize elements of one language, while generating elements of another. We conclude the chapter with a look at what FSAs can and cannot do.
Send us a comment.