A Second Course in Formal Languages and Automata Theory

Jeffrey Shallit
A Second Course in Formal Languages and Automata Theory
Cambridge University Press, September 30 2008.

"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.

About the Book

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

  1. Review of formal languages and automata theory
  2. Combinatorics on words
  3. Finite automata and regular languages
  4. Context-free grammars and languages
  5. Parsing and recognition
  6. Turing machines
  7. 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

    E-mail: