Books on automata theory for self-study

Question

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

Sadeq Dousti · Answer 1 · 2010-10-05T19:05:17.520

36

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.

edited Oct 05 '10 at 19:05

answered Oct 05 '10 at 17:34

Sadeq Dousti

16,479
9
69
152

8

I second Sipster. I use it for my course. – Dave Clarke Oct 05 '10 at 17:36
2

I spent a whole summer doing problems from the old HU book. Fun times... – Suresh Venkat Oct 05 '10 at 18:21
Yes, HU 2nd edition. – Kaveh Oct 05 '10 at 19:00
@Kaveh: Now in the 3rd edition. See the link. – Sadeq Dousti Oct 05 '10 at 19:05
I've Ullman's and Peter Linz's Book. But none of them have Good examples. Like a Math text book should have. I need a book that has a lot of examples. otherwise I cannot evaluate how much I've learnt. – user1652 Oct 05 '10 at 19:19
@Sadeq: I know, that is the reason I wrote 2nd edition. – Kaveh Oct 05 '10 at 22:00
Have you tried D.-Z. Du and K. Ko, Problem Solving in Automata, Languages and Complexity, 2001? – Kaveh Oct 05 '10 at 22:02
@Kaveh, in the 2nd edition of the Cinderella book all the good stuff has been taken out! – didest Oct 06 '10 at 00:10
@Diego: I thought that was the third edition, are you sure? – Kaveh Oct 06 '10 at 00:21
@Kaveh, the 2nd took out important things like Myhill-Nerode theorem and several proofs, but as you said it has many examples. I don't know the 3rd one. – didest Oct 06 '10 at 03:09
@Kaveh: I thought you wanted to contrast it from the 1st edition. Is the 3rd ed. even worse than the 2nd ed.? – Sadeq Dousti Oct 06 '10 at 05:30
The Hopcroft & Ullman FLRA book from 1969 is available from the ACM in a nicely scanned, searchable digital form: http://portal.acm.org/citation.cfm?id=1096945 – András Salamon Oct 06 '10 at 23:09
I haven't seen either the 2nd or 3rd edition, but there is one review on the Amazon USA site that says the biggest difference between the 2nd and 3rd editions is the online tutorial material. So I would expect the "more difficult" material to still be missing in the 3rd edition. – András Salamon Oct 06 '10 at 23:11
12

I strongly prefer Hopcroft&Ullman without Motwani. HU&M took out all the good problems! – Jeffε Oct 07 '10 at 02:12
@Sadeq,Diego: Yes, I have checked and noticed that I meant the 1st edition from 1979, not the 2nd one. – Kaveh Oct 07 '10 at 16:29
4

@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 07 '10 at 16:47
@user1652: Another possibility: "Introduction to Languages and the Theory of Computation" by John Martin. It's got lots of examples, and I see that a new edition just came out this year. – Kurt Oct 07 '10 at 16:56
2

@Kurt: Your comments are too good to be left as just comments! Why not post them as answers? – Sadeq Dousti Oct 07 '10 at 18:37
1

For beginners I would recommend Micheal Sipser. After Reading this book, you will have enough experience and go for Ullman and Hopecraft to fill up few of the holes... – Sachin Kumar Sep 03 '19 at 17:01
Appart from books, you must consider solving problems and examples. In Ullman's book, at the end of every topic you have been given some tricky exercise. Try them. In Sipser, shift to at the end of the chapter(s). – Sachin Kumar Sep 03 '19 at 17:04

score 10 · Answer 2 · answered Nov 16 '10 at 14:50

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.

score 9 · Answer 3 · answered Nov 20 '10 at 14:29

9

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.

answered Nov 20 '10 at 14:29

Sylvain

3,374
26
22

1

If 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 04:33

score 6 · Answer 4 · answered Nov 18 '10 at 08:54

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

score 5 · Answer 5 · answered Nov 16 '10 at 11:39

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

score 5 · Answer 6 · answered Nov 20 '10 at 16:56

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.

score 4 · Answer 7 · answered Jan 07 '22 at 19:28

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

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.

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. — Lamine, Jan 08 '22 at 17:15

score 2 · Answer 8 · answered Sep 25 '13 at 21:14

2

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.

answered Sep 25 '13 at 21:14

Tharindu Rusira

101
2

score 1 · Answer 9 · answered Nov 28 '13 at 12:11

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

score 1 · Answer 10 · answered Dec 09 '13 at 11:57

1

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

answered Dec 09 '13 at 11:57

score 0 · Answer 11 · edited Jun 17 '20 at 09:38

0

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.

edited Jun 17 '20 at 09:38

Community

1

answered Nov 27 '13 at 15:18

guhemama

1

score 0 · Answer 12 · answered Jul 08 '14 at 11:24

0

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

answered Jul 08 '14 at 11:24

Prateek Bhuwania

1

Books on automata theory for self-study

12 Answers12

Linked