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.
"Problem Solving in Automata, Languages, and Complexity" by Du-Ko is one of my favorites after Sipser , HU and Kozen. It contains many solutions to the *rd problems of Kozen and sipser with numerous examples and related exercises. Specially useful for exam preparation.
"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.
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
There is also Elements of the Theory of Computation by H.Lewis and C.Papadimitriou. It's a well written introduction to automata theory.
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.
" Formal Languages And Automata Theory " by A.A. Puntambekar is the best book for solved examples. Most of the book contains only solved examples and little theory. Its good to pass the exams.