32
$\begingroup$

I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.

|cite|improve this question
$\endgroup$

11 Answers 11

35
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 7
    $\begingroup$ I second Sipster. I use it for my course. $\endgroup$ – Dave Clarke Oct 5 '10 at 17:36
  • 2
    $\begingroup$ I spent a whole summer doing problems from the old HU book. Fun times... $\endgroup$ – Suresh Venkat Oct 5 '10 at 18:21
  • 7
    $\begingroup$ I strongly prefer Hopcroft&Ullman without Motwani. HU&M took out all the good problems! $\endgroup$ – Jeffε Oct 7 '10 at 2:12
  • 2
    $\begingroup$ @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. $\endgroup$ – Kurt Oct 7 '10 at 16:47
  • 2
    $\begingroup$ @Kurt: Your comments are too good to be left as just comments! Why not post them as answers? $\endgroup$ – M.S. Dousti Oct 7 '10 at 18:37
9
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
9
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If we are talking only about automata theory, this must be the best book about the subject. I'm reading it and loving it! $\endgroup$ – Marcos Villagra Nov 29 '13 at 4:33
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
5
$\begingroup$

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

http://www-igm.univ-mlv.fr/~berstel/Lothaire/

|cite|improve this answer
$\endgroup$
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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
|cite|improve this answer
$\endgroup$
1
$\begingroup$

There is also Elements of the Theory of Computation by H.Lewis and C.Papadimitriou. It's a well written introduction to automata theory.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Understanding Computation

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.