Overview
Gorman and Sproat (2021) on finite state transducers and their use in text processing.
So far, we have mainly used finite state automata (FSAs) to state constraints on strings. We began with some candidate language, often all of \(\Sigma^*\), and intersected it with automata that exclude strings containing a prohibited pattern.
But what if the grammar needs to relate an underlying form to one or more surface forms? We can describe it as a relation between two strings. We will call this formulation the transduction view.
A finite state transducer (FST) implements the transduction view by placing two labels on each transition: an input label from \(\Sigma \cup \{\epsilon\}\) and an output label from \(\Gamma \cup \{\epsilon\}\) (Mohri 1997). A successful path thus spells out a pair of strings rather than a single string. The relations that can be described in this way are known as the rational relations (Kaplan and Kay 1994).
This relation-based formulation matters for phonology. It lets one machine be used in the generative direction, from an underlying form to its surface realizations, or in the analytic direction, from a surface form to its possible underlying forms. Kaplan and Kay use this two-way interpretation to compile rule systems into a single transducer, while Mohri develops the corresponding application and optimization algorithms (Kaplan and Kay 1994; Mohri 1997).
We’ll begin by following a path through one FST and reading its two labels. Then we’ll ask how to combine these string relations, recover their paths and outputs, and compile phonological rewrite rules. This will give us the machinery needed to represent rule ordering and weighted alternatives.