Morphology and Finite-State Methods

It is tempting to treat a word as the smallest unit of language, but words themselves have structure. Morphology is the study of that structure, and its basic unit is the morpheme, the smallest piece that carries meaning or grammatical function.

"Unhappiness" is three morphemes: un, meaning not, happy, the root, and ness, turning an adjective into a noun. "Cats" is two: cat and a plural s. "Walked" is walk plus a past-tense marker.

This matters computationally because of the Zipfian long tail from the first lesson. You will constantly meet word forms you have never seen, but if you can decompose them into known morphemes, they are not unknown at all. A system that knows "happy", "un", and "ness" understands "unhappiness" the first time it appears. Morphology is one of the main tools against sparsity.

The world's languages assemble words in strikingly different amounts, which sets how much morphology matters for each.

English is morphologically light: most words take only a handful of endings, so treating words as atoms nearly works. Finnish and Turkish are agglutinative, gluing many morphemes in a row, so a single Turkish verb can encode what English needs a whole clause for, and one dictionary entry yields thousands of surface forms. Arabic and Hebrew are templatic, interleaving a consonant root with vowel patterns, so k-t-b becomes kataba, kitaab, kaatib by pouring different vowels through the same frame.

The computational payoff scales with this richness. For English the gain from morphological analysis is modest; for Turkish or Finnish it is the difference between a workable system and one drowning in unseen forms. A method built only for English breaks on most of the world's languages.

Here the hierarchy from the previous lesson pays off. Syntax needed context-free power and beyond, but morphology, with rare exceptions, lives at the very bottom rung: it is regular.

The reason is that word structure has essentially no unbounded nesting. Affixes attach in sequence, and although a word can be long, it does not embed copies of itself to arbitrary depth the way a sentence embeds clauses. A pattern with no unbounded counting is within reach of a finite-state machine.

This is a genuinely fortunate fact, because finite-state machines are the fastest and best-understood devices in the whole hierarchy. They recognize in time linear in the input, compose and combine cleanly, and are easy to build and reason about. Kimmo Koskenniemi made the case concretely in his 1983 model of two-level morphology, showing that the morphology of a hard language could be captured entirely with finite-state rules.

The right tool is not a plain automaton, which only accepts or rejects a string, but a finite-state transducer, which reads one string and writes another. It defines a relation between two levels: the surface form as written, and the lexical form, the root plus its grammatical features.

Run the transducer one way, from surface to lexical, and it performs analysis: "cats" becomes "cat +Noun +Plural". Run the very same machine the other way and it performs generation: "cat +Noun +Plural" becomes "cats". A single device does both directions, because a relation has no inherent direction, which is why finite-state transducers became the backbone of morphological processing.

The theoretical grounding came from Ronald Kaplan and Martin Kay, whose 1994 paper "Regular Models of Phonological Rule Systems" proved that the rewrite rules linguists had long written by hand were exactly equivalent to finite-state transducers, uniting the linguistics with the computation.

Morphology is not just concatenation, because gluing morphemes together triggers spelling changes at the seams, and a good analyzer must undo them.

English plural of "fox" is "foxes", not "foxs": an e appears. "Try" plus s is "tries": the y becomes ie. "Big" plus er doubles the consonant to "bigger". These are orthographic and phonological rules, conditioned by the surrounding letters or sounds, and they are exactly what a naive split on morpheme boundaries gets wrong.

Transducers absorb them cleanly. You build one transducer for the abstract concatenation, cat plus plural, and separate transducers for each spelling rule, then compose them into a single machine that maps the deep form straight to the correct surface string. Because finite-state transducers are closed under composition, the result is still one finite-state transducer, as fast as any other. This composability is the practical reason the finite-state approach scaled to real languages.

Trace "studies" through an English analyzer to see the levels connect.

surface:   s t u d i e s
            |
  (spelling rule: y -> ie before s is reversed)
            |
deep:      s t u d y + s
            |
  (morpheme boundary and features assigned)
            |
lexical:   study +Verb +3rdSing
           study +Noun +Plural

The analyzer returns two readings, because "studies" is genuinely ambiguous: the verb, as in "she studies", and the plural noun, as in "two studies". This is the level-one ambiguity theme reappearing inside a single word, and the transducer correctly reports both rather than guessing. Choosing between them needs the sentence around the word, which is the syntactic level's job. A morphological analyzer's honest output is the full set of valid decompositions, not a single answer.

Hand-built transducers work well but are labour-intensive: a linguist must encode the lexicon and rules for each language. Since the 2010s the field has increasingly framed morphology as a learning problem, and Ryan Cotterell of ETH Zurich has been central to it.

The reframing is morphological inflection as a task: given a root and a set of features, produce the correct surface form, for example map "run" plus past to "ran". This is exactly the generation direction of a transducer, but learned from examples rather than written by hand, which lets a model generalize to forms it was never given. The SIGMORPHON shared tasks, which Cotterell helped organize, turned this into an annual competition spanning dozens of languages, driving neural sequence models on morphology.

The finite-state theory did not become obsolete. It remains the specification of what correct morphology is, and the yardstick a learned model is measured against.

There is a live tension worth naming. Modern language models do not use morphological analyzers at all. They split text with statistical tokenizers like byte-pair encoding, which chop words into frequent character chunks with no linguistic knowledge.

BPE wins on convenience: one algorithm, no linguist, any language. But it cuts words in linguistically arbitrary places, splitting "unhappiness" as "un", "happ", "iness" if that is what the statistics favour, and it handles the morphologically rich languages of the world markedly worse than English. Whether ignoring morphology is a real cost for these models is an active research question, and Cotterell's group is among those studying it formally. The finite-state story is not a museum piece; it is the standard the statistical shortcut is judged against.

Morphology is the level where computational linguistics most fully succeeded. Word structure turned out to be regular, so the fast, composable finite-state machines at the bottom of the hierarchy were exactly the right tool, and transducers gave a single mechanism for both analysis and generation across languages as different as English and Turkish.

That success is a direct dividend of the hierarchy. Knowing that morphology needs only regular power told the field to reach for the cheapest devices available, and they sufficed.

The final lesson turns the same hierarchy on the models that now dominate the field. If word structure is regular and syntax is mildly context-sensitive, the natural question is where a recurrent network or a transformer falls on that same ladder, and therefore which of these linguistic patterns each can and cannot represent.