Morphological Analysis and Generation › Finite-State Morphology

Finite-state morphology is the classical answer, developed in the 1980s and 1990s by Kimmo Koskenniemi, Lauri Karttunen, and others. It remains an important approach in morphological analyzers, spell checkers, and hyphenation systems. Its core claim is elegant: many practically useful accounts of word structure can be expressed with finite-state automata extended to emit symbols in two alphabets at once.

Building on your knowledge of regular expressions from Part I, Chapter 3, recall that a finite-state automaton recognizes a regular language: it reads a string and answers yes or no. A finite-state transducer (FST) generalizes this from a recognizer to a translator: it reads a string and produces another string.

The power of this formalism for morphology comes from its closure properties. Regular relations remain regular under composition and union, and they can also be inverted: the inverse of an analyzer relation can serve as its generator relation. Because analysis and generation use the same encoded relation, they cannot drift apart as two separately maintained implementations might. The guarantee is relative to the grammar: the machine is consistent with what its lexicon and constraints encode, not automatically with every fact of the natural language. A lexicon transducer can also feed a cascade of rewrite-rule transducers. If $L$ is the lexicon transducer and $R_1, \ldots, R_k$ are sequential rule transducers, the whole relation is their composition $R_k \circ \cdots \circ R_1 \circ L$.

where:

• $L$: the lexicon transducer, which maps lexical strings (stems plus morpheme labels) to intermediate strings
• $R_1, \ldots, R_k$: the phonological rule transducers, applied in order, with $R_1$ first
• $R_k \circ \cdots \circ R_1 \circ L$: the composed transducer, which maps a lexical string directly to its surface form

Composition is what lets the pipeline behave like one relation: each transducer's output is paired with the next transducer's input, and the composite relation is still regular, so it can be inverted. Practically, this means you can develop the lexicon and each rule as separate, testable artifacts, then compile them into one transducer for efficient lookup.

Koskenniemi's two-level morphology, the foundational design, models a word as a pairing between a lexical string (morphemes with their identity intact) and a surface string (what is written). Between the two levels sit correspondence rules that map pairs of symbols in parallel: rather than rewriting a string sequentially, rule by rule, two-level rules constrain, at each position, which lexical symbol may correspond to which surface symbol.

For the English noun plural, the lexicon would generate the lexical string watch +N +PL, conceptually w a t c h ^ s with a morpheme boundary, and the constraints must license the surface form watches. In two-level notation, one writes rules over symbol pairs, where each symbol in the rule is an upper:lower pair. A schematic sibilant-epenthesis constraint looks like this:

where:

• $\epsilon{:}e$: the correspondence pair, with nothing in the lexical string and a surface e on the other side
• $\textit{Sibilant}$: a symbol class matching one sibilant consonant; in a complete grammar, the environment also identifies the plural morpheme boundary
• $\_$: the position of the $\epsilon{:}e$ correspondence itself
• $s{:}s$: the identity correspondence for the plural s, which passes through unchanged
• $\Leftrightarrow$: the biconditional operator

Read this as: "the pair $\epsilon{:}e$ (nothing in the lexical string, an e on the surface) corresponds exactly in the environment where a sibilant precedes the plural s." The biconditional operator $\Leftrightarrow$ means the rule fires exactly in this environment and nowhere else. Different operators encode different logical strengths, and choosing the right one for each rule is part of the grammarian's job:

• $\to$ surface constraint: the correspondence is permitted only in this environment and is blocked everywhere else (this rules out illicit occurrences).
• $\Leftarrow$ obligatory: whenever the left side occurs in this environment, it must be rewritten.
• $\Leftrightarrow$ if and only if: both of the above.

Two-level constraints are evaluated in parallel over the same lexical–surface correspondence; they do not feed or bleed one another through an ordering. For party $\to$ parties, a complete grammar would constrain the lexical y to correspond to surface i in the plural environment and would license surface e before the plural s. Both constraints describe the same aligned pair rather than successively rewriting party+s. That distinguishes the method from an ordered rewrite cascade.

Sequential rewrite transducers are also useful, and they compose. Because an FST denotes a relation rather than necessarily a function, composition is set-valued:

where:

• $x$: an input string, for example a lexical string produced by the lexicon
• $R_1$: the first rule applied, for example the y-to-i rule
• $R_2$: the second rule applied, for example the epenthesis rule
• $y$: one possible intermediate string licensed by $R_1$
• $R_2(y)$: the set of outputs licensed by $R_2$ for that intermediate string

In other words, the composite transducer retains every path whose intermediate output from $R_1$ matches an input to $R_2$. It produces one combined relation, but that relation need not be deterministic. Building the analyzer means compiling the lexicon (which morphemes exist and in what order, a constraint called morphotactics) and the alternation constraints (how morphemes change in contact, called morphophonology) into a transducer that can be used in both directions.

Why is it legitimate to model many sound alternations with finite-state machines? Contexts like "preceded by a sibilant" or "followed by a suffix starting with a front vowel" are the kinds of finite-context patterns regular expressions capture. Kaplan and Kay's classic 1994 treatment showed that the standard, non-self-applying interpretation of finite-context rewrite rules denotes regular relations; FST closure under composition then preserves regularity for a finite cascade. The restrictions matter: arbitrary cyclic or self-feeding rule application is not covered by the claim.

This gives finite-state morphology a precise, grammar-relative guarantee. An analyzer returns exactly the pairs licensed by its compiled lexicon and constraints. It can still accept a non-word if the grammar overgenerates or miss a real word if the lexicon or rules are incomplete. Neural models offer a different tradeoff: their architecture does not hard-code the same closed set of licensed pairs, so they can produce forms outside the observed language patterns.

Let's walk through a small but real example: the Finnish word taloissa, meaning "in the houses." Finnish nouns inflect for number and case, and the case suffixes obey vowel harmony, so a single noun stem generates dozens of forms whose suffix vowels depend on the stem.

The lexicon says a noun stem like talo ("house") inflects by concatenating a number marker and a case marker. The lexical string contains the stem plus abstract markers, some of which (like the plural i and the archiphoneme A inside the case suffix) are later rewritten by the rules:

Notice that the plural has an i allomorph (Finnish uses i or j before most cases) and that the case suffix ssa contains the back vowel a, because the last vowel of the stem is o, a back vowel. A front-vowel stem selects ssä. The form käsissä from käsi additionally involves plural-stem alternation and vowel deletion; harmony alone selects the suffix vowel but does not derive the complete form. In two-level notation, harmony can be expressed with an archiphoneme, a symbol in the lexical alphabet that has not yet decided which vowel it will become:

• $A$: the archiphoneme in the lexical string, the underspecified vowel of the case suffix
• $A{:}a$ / $A{:}\ddot{a}$: the correspondence pair, mapping the underspecified $A$ to the back surface vowel $a$ or the front surface vowel $\ddot{a}$
• $\textit{BackVowel}$ / $\textit{FrontVowel}$: a symbol class matching one harmony-triggering back vowel ($a$, $o$, $u$) or front vowel ($\ddot{a}$, $\ddot{o}$, $y$)
• $\textit{Neutral}^{*}$: zero or more harmony-neutral vowels ($i$ or $e$), such as the plural allomorph $i$, which neither trigger harmony nor block it
• $C_0$: zero or more intervening consonants between the triggering vowel (after any neutral vowels) and the archiphoneme
• $\_$: the position of the $A{:}a$ or $A{:}\ddot{a}$ correspondence itself
• $\Leftrightarrow$: the biconditional, meaning the pair is rewritten exactly in this environment and nowhere else

The lexical string talo i ssA (the A being the archiphoneme inside the case suffix) passes through the harmony rule, which skips the harmony-neutral plural i and commits the A to a because the nearest preceding stem vowel is back. The composed transducer then aligns the two strings character by character:

Lexical:  t a l o   i   s s A
Surface:  t a l o   i   s s a     →  taloissa

where:

• row 1 (Lexical): the lexical string talo i ssA, with the archiphoneme A standing in for the not-yet-harmonized first vowel of the inessive suffix
• row 2 (Surface): the surface string taloissa, after the harmony rule commits A to a
• characters at the same position are aligned in columns, showing that each lexical symbol corresponds to exactly one surface symbol (the +PL and +INE labels are grammatical features rather than surface characters)

The harmony constraint licenses A:a because the preceding harmony-triggering stem vowel is o, a back vowel. For a front-vowel stem it licenses A:ä; separate alternation constraints account for the stem changes in forms such as käsissä.

Running the same transducer in the analysis direction, the input taloissa is scanned left to right: talo matches a noun stem, i matches the plural allomorph, ssa matches the inessive allomorph, and the end of input is reached in a final state. The machine emits talo +N +PL +INE. If we fed it talon, it would emit talo +N +SG +GEN ("of the house"); with no suffix, talo yields talo +N +SG +NOM. Ambiguity arises when multiple lexical paths accept the same surface string. Resolving among such analyses requires sentence context, which is exactly the role Viterbi-style decoding over a sequence tagger plays, as you saw in Part VI, Chapter 6.

A plain FST answers a yes/no question per string pair: is this analysis licensed? Real systems want the most plausible analysis, because a raw enumeration of licensed analyses is often long and mostly useless without a ranking. Weighted FSTs attach a weight to each arc, typically a negative log probability:

where:

• $\text{path}$: one accepting route through the transducer, from the start state to a final state, consuming the input string and emitting a candidate analysis
• $\text{arc}$: a single weighted transition on that path
• $p(\text{arc})$: the probability associated with taking that arc, so that $-\log p(\text{arc})$ is its cost
• $\sum_{\text{arc} \in \text{path}}$: the sum of the arc costs over the whole path

When a path probability is factorized into arc probabilities, which may be conditional on the state and history encoded by the machine, multiplication becomes addition under the negative logarithm. An arc with probability zero has infinite cost. The best analysis of a surface form is then the minimum-weight accepting path, found by the same dynamic programming idea as Viterbi decoding from Part VI, Chapter 6, just over a transducer instead of an HMM. Weights can come from a lexicon of word frequencies, a corpus, or a character-level language model, and they let the analyzer rank flie+s below fly+s without hard-coding a rejection.

To make the ranking concrete, we first attach toy corpus frequencies to the candidate analyses of flies and convert them to path costs.

Because the correct reading carries the bulk of the corpus mass, its cost is far below the spurious analysis, which is exactly the separation a weighted FST exploits. Note that the spurious path remains available at finite cost: weighting softens the all-or-nothing character of the unweighted machine while preserving the complete enumeration of licensed analyses.

In one downstream design, a disambiguating sequence tagger consumes these costs alongside sentence context and selects among the candidate analyses. Other pipelines expose candidates without their original FST weights or combine scores differently. Either way, keeping a candidate at finite cost leaves it available when context favors it.

Several mature toolchains implement this pipeline. Xerox tools (lexc for lexicons, twolc for two-level rules) are the historical standard. HFST and foma are widely used open-source implementations, and pynini brings weighted FSTs into Python. GiellaLT, developed by the Giellatekno community, supports language-technology resources for Sámi and other languages. UniMorph provides a cross-lingual schema and inflection datasets, while UniDive coordinates work on universal and cross-lingual morphology; they are related resources, not FST analyzer toolchains. A high-quality analyzer for a new language can require substantial expert work: enumerating the lexicon, writing morphotactic continuation classes, and testing morphophonological constraints. That cost helped motivate data-driven approaches, which we examine next.