Overview

We’ll start with an application of FSAs to modeling licit English syllables. To get a sense for what FSAs look like, let’s consider the following example, which aims to model possible English syllables:

The symbols along the arrow represent collections of symbols.

Class Symbol	IPA Symbols	Description
Cstop	[p, b, t, d, k, g]	Stop consonants/plosives
Cfric	[f, v, θ, ð, s, z, ʃ, ʒ, h]	Fricatives
Caffr/nas	[tʃ, dʒ, m, n, ŋ]	Affricates and nasals
Cliq/glide	[l, r, w, j]	Liquids and glides
Cliq	[l, r]	Liquids only
Cglide	[w, j]	Glides only
Cobstr	[t, d, s, z, θ, ð]	Obstruents in coda clusters
Cs	[s]	Just /s/, common in complex codas
Csyl	[n̩, m̩, l̩, r̩]	Syllabic consonants

Class Symbol	IPA Symbols	Description
Vfront	[i, ɪ, e, ɛ, æ, a]	Front vowels
Vback	[ɑ, ɔ, o, ʊ, u, ʌ, ə, ɝ]	Back vowels
Vglide	[ɪ, ʊ]	Vowels that can form glides in diphthongs

There’s 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.