  These lecture notes are intended as a supplement to Moore and Mertens' The
Nature of Computation or as a standalone resource, and are available to anyone
who wants to use them. Comments are welcome, and please let me know if you use
these notes in a course. There are 61 exercises.
  I emphasize that automata are elementary playgrounds where we can explore the
issues of deterministic and nondeterministic computation. Unlike P vs. NP, we
can prove that nondeterminism is equivalent to determinism, or strictly more
powerful than determinism, in finite-state and push-down automata respectively.
I also correct several historical and aesthetic injustices: in particular, the
Myhill-Nerode theorem and the idea of building minimal DFAs from equivalence
classes of prefixes is restored to its rightful place above the Pumping Lemma
for regular languages. I also discuss the Pumping Lemma for context-free
languages, and briefly discuss counter automata, queue automata, and the
connection between unambiguous context-free languages and algebraic generating
functions.
