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.
-
7
-
2I spent a whole summer doing problems from the old HU book. Fun times... – Suresh Venkat Oct 5 '10 at 18:21
-
7I strongly prefer Hopcroft&Ullman without Motwani. HU&M took out all the good problems! – Jeffε Oct 7 '10 at 2:12
-
2@user1652: I don't think you're going to find something with more examples than Linz's book. You could also take a look at "Introduction to Computer Theory" by Daniel Cohen. It has lots of examples, but is an older book and maybe not as readable as Linz. – Kurt Oct 7 '10 at 16:47
-
2@Kurt: Your comments are too good to be left as just comments! Why not post them as answers? – M.S. Dousti Oct 7 '10 at 18:37
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.
-
1If we are talking only about automata theory, this must be the best book about the subject. I'm reading it and loving it! – Marcos Villagra Nov 29 '13 at 4:33
"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.
Introduction to languages and The theory of computation
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.
