Chomsky’s Syntactic Structures was a public manifesto of the cognitive revolution in psychology. Contrary to the Behaviorist theory of the time, it implied that language processing and learning conceal complex, unconscious mental processes—and that a good way to start to understand them was to try and construct a formal system as a model. Chomsky proposed to study what kind of functions, or more generally, computations, are capable of simulating the mental processes of language, starting with some coarse criteria like whether they can put elements correctly together into sentences and words (models of syntax and morphology) or describe the patterns governing the pronunciation of words (models of phonology).

Over the last sixty years, we have sometimes managed to specify these computations in extremely precise mathematical terms, and thereby learn a lot about human language. This course covers the basics of what we have learned about phonology in this way.

Syntactic Structures argued that human language does not put words together into sentences using a simple n-gram based approach, the way, say Google Translate does, as in, the big + big dogs + dogs run = the big dogs run, nor does it use the equivalent of simple phrase structure models. The arguments have turned out to be correct.

But, for phonology, in contrast, the n-gram model works for a large and coherent class of phenomena; and, where that does not work directly, the models needed are not too much more complex; phonological computations fall well within the very restrictive class of finite state transductions, or regular relations. This suggests that human language phonology is rather different from human syntax, or even morphology.

In this course we will do three things. We will sharpen exactly what object of study is meant when we talk about human phonology, morphology, and syntax. We will explain the important formal systems, with as much opportunity as possible to do interactive pencil-and-paper and/or computer exploration of the models and their capacities; we will see how we can use them to abstract over a lot of details of different grammatical theories which, for our purposes, won’t matter. And, of course, we will survey basic classes of phonological phenomena—stress, local segmental processes, and long-distance processes—and we will see how the types of computations capable of handling each are distinct from each other, and from what is necessary in syntax and morphology (and what they have in common).


Substantial previous experience doing phonology problems and a familiarity with basic syntactic and morphological phenomena is essential for this course. Familiarity with the scientific philosophy of generative grammar and some of the basic theoretical issues in phonology will be very helpful, but are not strictly necessary. No particular mathematical or computer science background is expected. The logic of the theoretical arguments will be discussed largely without use of mathematical notation and vocabulary. Interested students with experience doing mathematical proofs will be given opportunities to explore the issues more deeply.

From Day 4

Materials from today

Slides from Day 4

Interactive part of Day 4

Interactive part of Day 2 (go over this with the rules)

From Day 3

Materials from today

Slides from Day 3

From Day 2

Materials from today

Slides from Day 2

Interactive part of Day 2

From Day 1

Materials from today

Slides from Day 1

Interactive part of Day 1

Foma setup

Setting up Foma is not entirely trivial if you haven't downloaded and installed command line tools before. To visualize the FSAs, you need to install a separate program called "Graphviz", and both Foma and Graphviz require a little bit of command line knowledge to get running (changing directories, mainly). Please email me or come find me if you want help.

The "view" command will not work on Windows (foma will crash). There is still a way to view a net if you have GraphViz installed, in two steps. (This is also necessary on a Mac if you install GraphViz from the package rather than from the port; see below.)

Simply replace

print dot > FILE
where FILE is the name of a file where you would like to save a graph. You can then open GraphViz and open this file.

Website for Foma: The download link is on the main page; once you've extracted the archive file (tar.gz on Mac/Linux, zip on Windows), the folder it creates has everything you need to run Foma from the command line (change to that folder and type, on Mac/Linux, "./foma", on Windows just "foma")

Website for Graphviz:On Windows, download this package. There are two ways to install GraphViz on a Mac, one of which allows you to open it easily as a normal application (a "package"), and the other of which puts it in a place where Foma can find it so that "view" works. To do it the first way, you'll need first to install MacPorts or Homebrew (which can both take a while because they involve large downloads); then type

port install graphviz
brew install graphviz
depending on which you've installed. The other way is using this package.

Some of the automata from today

read regex a;

read regex a; read regex b;

read regex a a* ; 

read regex [a a]* ; 

read regex a [a a]* ; 

Nondeterministic FSA from the end

Determinized version of the same FSA


Background (this would be good to read in advance)

Syntactic Structures, 1, 2.1–2.3, 3.1–3.3, 4.1–4.3

Heinz and Idsardi (2011): Sentence and word complexity

Heinz (2011a): Computational Phonology I

Hopcroft et al., Chapter 1, Introduction, Sections 1.1.1–1.1.3, 1.5.1–1.5.3

For reading ahead on the theoretical contents

Chandlee (2014): Strictly local phonological processes

Heinz (2009): On the role of locality in learning stress patterns

Heinz (2010): Learning long distance phonotactics

For details on technical matters

Kaplan and Kay (1994): Regular models of phonological rule systems

Hopcroft et al., Chapter 1 (whole thing, try and do some exercises)

Heinz (2011b): Computational Phonology II

Hopcroft et al., Chapter 2 (until the end of section 2.3, do some exercises)

Hopcroft et al., Chapter 3 (until the end of section 3.2, do some exercises)