38
$\begingroup$

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

Improve this question
$\endgroup$

12 Answers 12

Reset to default
36
$\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.

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

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.

Improve this answer
$\endgroup$
1
  • 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, 2013 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.

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/

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.

Improve this answer
$\endgroup$
4
$\begingroup$

Handbook of Automata Theory: Volumes I (Theoretical Foundations) and II (Automata in Mathematics and Selected Applications)

enter image description here

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.

Readership

Graduate students and researchers interested in mathematics and computer science.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I took a look on this book. It is great, but I was really disappointed by noting that it only deals with finite state automata. I would be happy if a book with the same level on PDA exists. $\endgroup$
    – Lamine
    Jan 8, 2022 at 17:15
2
$\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.

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

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.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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