Finite state transducers and morphology
Morphology as a transduction problem
- Analysis: surface form to lexical form (annotated with grammatical information)
- Generation: lexical form (annotated with grammatical information) to surface form
- Analysis and generation mediated by a set of context-sensitive rules governing alternation and a set of morphotactic constraints
Finite state transducers
- Regular relations
- FSTs
- Acceptors (recognizers) of string pairs
- Translators of one string into another
- English noun morphotactics implemented as an FST
- An English orthographic rule implemented as an FST
+ → e / S _ s #
S = {s, z, h, x}
- The sigma alphabet and the unknown symbol
- Operations defined in FSTs
- Union
- Concatenation
- Inversion: FSTs are reversible
- Composition
- Transducing the output of one transducer with a second
- Combining the two transducers into one
- A cascade of composed FSTs
- FSTs are not closed under intersection unless the input and output strings are the same length: the shared set of output strings of two FSTs may
be a non-regular language
- Ambiguity and non-determinism in FSTs
- Two-level approaches and multilevel approaches using composition
- Ordered traditional rules, intersection, and composition
