I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.
The classical reference is "Introduction To Automata Theory, Languages and Computation" (by Hopcroft, Motwani, and Ullman). Some people also recommend the much older "Formal Languages and Their Relation to Automata" (by Hopcroft and Ullman).
I, however, like "Introduction to the Theory of Computation" (by Sipser). It is very well written, and is a relatively new book.
I have a soft spot for Automata & Computability by Dexter Kozen (table of contents and sample chapters [PS]). It is quite thorough and covers some really interesting advanced topics. The proofs are formal and explicit and the notation and formatting are lovely. Most importantly, the exercises are excellent, so depending on the level of your exams it will be good study material.
The one I'm using the most for my courses is Elements of Automata Theory by Jacques Sakarovitch, Cambridge University Press, 2009. Its scope might be a bit different from the others', as it also extensively covers algebraic aspects, formal power series, and transductions. And there are many exercises.
"Applied Combinatorics on Words", by Lothaire, 2004
Is far and away my favorite. Loads of examples, and also builds up from the absolute basics all the way to some pretty interesting automata applications like Automatic Speech Recognition with Weighted Finite-State Transducers, and topics in bioinformatics.
Best of all, it's free to download, and also includes solution sets:
I'm not sure this is the best book to prepare for exams, but the book
Finite Automata; Behavior and Synthesis by B. A. Trakhtenbrot and Ya. M. Barzdinʹ
is quite good. It has a surprising number of great results that I have found especially helpful in research.
Edited by Jean-Éric Pin: Université de Paris and CNRS, France
A publication of the European Mathematical Society
Automata theory is a subject of study at the crossroads of mathematics, theoretical computer science, and applications. In its core it deals with abstract models of systems whose behaviour is based on transitions between states, and it develops methods for the description, classification, analysis, and design of such systems.
The Handbook of Automata Theory gives a comprehensive overview of current research in automata theory and is aimed at a broad readership of researchers and graduate students in mathematics and computer science.
Volume I is divided into three parts. The first part presents various types of automata: automata on words, on infinite words, on finite and infinite trees, weighted and maxplus automata, transducers, and two-dimensional models. Complexity aspects are discussed in the second part. Algebraic and topological aspects of automata theory are covered in the third part.
Volume II consists of two parts. The first part is dedicated to applications of automata in mathematics: group theory, number theory, symbolic dynamics, logic, and real functions. The second part presents a series of further applications of automata theory such as message-passing systems, symbolic methods, synthesis, timed automata, verification of higher-order programs, analysis of probabilistic processes, natural language processing, formal verification of programs and quantum computing.
The two volumes comprise a total of 39 chapters, with extensive references and individual tables of contents for each one, as well as a detailed subject index.
Graduate students and researchers interested in mathematics and computer science.
John C. Martin
I highly recommend this book for a beginner and this is a perfect choice for someone who's looking for lots of examples.
I enjoy the following lecture notes by Jarkko Kari: http://users.utu.fi/jkari/automata/
Brief course outline:
Regular languages Finite automata, regular expressions Kleene theorem Pumping lemma Closure properties and decision algorithms State minimization, Myhill-Nerode theorem Context-free languages Grammars, parsing Normal forms Pushdown automata Pumping lemma Closure properties and decision algorithms Turing machines Recursive and recursively enumerable languages Universal Turing machines Undecidability of the halting problem (Turing) Reductions, other undecidable problems
From Simple Machines to Impossible Programs
It does cover a lot of stuff, which includes automata theory. The examples are presented in Ruby, and they are pretty easy to understand. You may need another book if you want to delve deeper into theory, but this one is great to learn the basics.