Overview
The finite state formalisms developed so far describe two related classes. FSAs describe the regular languages, while FSTs describe the rational relations between strings. But where does their expressive power end?
We’ll first introduce the pumping lemma, which gives a necessary property of every regular language. Its proof is the repeated-state argument used in the classical theory of finite automata (Rabin and Scott 1959). Then we’ll use the lemma to separate unbounded copying from bounded copying and to state more carefully what finite state models can and cannot do for morphology.
This separation also clarifies the transition to the next module. Context-free grammars will give us hierarchical structure, but they do not solve every nonregular mapping problem. In particular, unbounded total reduplication remains outside the context-free languages.