Overview

What does an FSA look like when it describes a phonological pattern? We’ll start with a small application to English syllable structure. English allows up to three consonants in an onset and several consonants in a coda, but the possible clusters are heavily constrained. The machine below is a toy syllable automaton: it records a few broad ordering generalizations, not the complete English inventory.

The broad natural-class labels make the machine readable, but they also make it overgenerate. For instance, an edge labeled \(P\) followed by one labeled \(L\) admits every stop-liquid combination, including combinations English excludes. A full grammar would replace these class labels with the individual transitions that the language actually licenses.

Each state is labeled with its role in the toy syllable structure: Sib tracks the special behavior of /s/ in onsets, Obs tracks obstruents that can start clusters, App is the pre-nucleus position where approximants and other singleton-only consonants land, and so on.

The state labels reflect where you are in the syllable structure:

State	Meaning
ini	Initial state; beginning of syllable
Sib	Onset: /s/ consumed (the sibilant that begins three-consonant onsets)
Obs	Onset: a stop or fricative consumed
sP	Onset: /s/ + stop consumed (as in sp, st, sk)
App	Onset complete; approximant or other final onset consonant consumed; ready for vowel
Nuc	Nucleus: vowel produced (accepting)
Dip	Nucleus: diphthong offglide produced (accepting)
Son	Coda: sonorant (nasal or liquid) consumed (accepting)
Ob₁	Coda: first obstruent consumed (accepting)
Ob₂	Coda: second obstruent consumed (accepting)
Ob₃	Coda: final /s/ consumed (accepting)

Now consider the notation. The labels on the transitions—\(P\), \(F\), \(N\), etc.—are not individual symbols but natural classes: shorthand for sets of phonemes. An edge labeled \(P\) actually represents six separate transitions, one for each stop consonant. Similarly, an edge labeled \(\varepsilon\) is an epsilon transition: it allows the automaton to move between states without consuming any symbol from the input. For instance, the \(\varepsilon\) on the edge from Obs to App lets the automaton treat a single obstruent as a complete onset (skipping the approximant position).

The following table defines each natural class:

Label	IPA members	Description
\(s\)	{s}	The sibilant /s/, which has a special role in English onsets
\(P\)	{p, b, t, d, k, g}	Stops (plosives)
\(F\)	{f, v, θ, ð, ʃ, ʒ, h}	Fricatives other than /s/
\(Aff\)	{tʃ, dʒ}	Affricates
\(N\)	{m, n, ŋ}	Nasals
\(L\)	{l, r}	Liquids
\(G\)	{w, j}	Glides
\(V\)	{i, ɪ, e, ɛ, æ, ɑ, ɔ, o, ʊ, u, ʌ, ə}	Vowels (monophthongs)
\(V_g\)	{ɪ, ʊ}	Offglide vowels (for diphthongs like /aɪ/, /aʊ/)
\(Ob\)	{p, b, t, d, k, g, f, v, θ, ð, s, z, ʃ, ʒ}	Obstruents (stops and fricatives, in coda clusters)

To trace through some examples, the word string /stɹɪŋ/ follows ini \(\xrightarrow{s}\) Sib \(\xrightarrow{P}\) sP \(\xrightarrow{L}\) App \(\xrightarrow{V}\) Nuc \(\xrightarrow{N}\) Son. The word a /ə/ follows ini \(\xrightarrow{\varepsilon}\) App \(\xrightarrow{V}\) Nuc. And cats /kæts/ follows ini \(\xrightarrow{P}\) Obs \(\xrightarrow{\varepsilon}\) App \(\xrightarrow{V}\) Nuc \(\xrightarrow{Ob}\) Ob₁ \(\xrightarrow{Ob}\) Ob₂.

There are a few components to notice here:

1. The circles represent the states of the finite state automaton. As you might expect, there are a finite number of them.
2. The arrows represent the transitions between states.
3. The labels on the arrows are the labels of the transitions, which always come from some alphabet \(\Sigma\) (just like in regular expressions).
4. There are two kinds of special states:
   • The initial state, which is the one that the automaton starts in.
   • The final states, which are the ones that the automaton can (but need not) end in.

The way we can tell whether an FSA generates a string is by starting at the initial state and following the transitions, choosing one symbol on each transition and collecting them to form a string. We’re allowed to (but need not) stop when we hit a final state. As long as we stop in a final state, the string we’ve built is generated by the automaton.