"The writing is crisp and no nonsense and, as befits a professor
at the University of Waterloo, Shallit has written a mathematically
rigorous book that has avoided the pitfall of being unduly
fussy."
-- Mark V. Lawson, Heriot-Watt University, writing in
SIAM Review, December 2009.
Written for graduate students and advanced undergraduates in computer
science, A Second Course in Formal Languages and Automata Theory treats
topics in the theory of computation not usually covered in a first
course. After a review of basic concepts, the book covers combinatorics
on words, regular languages, context-free languages, parsing and
recognition, Turing machines, and other language classes. Many topics
often absent from other textbooks, such as repetitions in words, state
complexity, the interchange lemma, 2DPDAs, and the incompressibility
method, are covered here. There is particular emphasis on the
resources needed to represent certain languages. The book also includes
a diverse collection of almost 250 exercises, suggestions for term
projects, and research problems that remain open.
Contents
Review of formal languages and automata theory
Combinatorics on words
Finite automata and regular languages
Context-free grammars and languages
Parsing and recognition
Turing machines
Other language classes
Fun Things About the Book
The image on the cover
of the book was designed by my Waterloo colleague Craig Kaplan. Thanks,
Craig!
There are some jokes in the index. See if you can find them.
Errata
Please report any errata you find. A complete list is here.
Addenda
If there is ever a second edition of the book, here are some things that will go in it.
Progress on the Research Problems
Problem 2.9.1, p. 47:
Rao and Rosenfeld
showed that one cannot avoid abelian cubes of
period 2 over a two-letter alphabet. This answers (b).
Problem 3.15.2, p. 105:
recently Zachary Chase
has improved the lower bound
to about O(n^{1/3}).
Problem 4.11.3, p. 138:
there is a claimed solution by Pálvölgyi Dömötör that I could not understand. But it may well
be correct.