<p>The classical reference is "<a href="http://rads.stackoverflow.com/amzn/click/0321462254">Introduction To Automata Theory, Languages and Computation</a>" (by Hopcroft, Motwani, and Ullman). Some people also recommend the much older "<a href="http://rads.stackoverflow.com/amzn/click/B000XI9B9A">Formal Languages and Their Relation to Automata</a>" (by Hopcroft and Ullman).</p>

<p>I, however, like "<a href="http://rads.stackoverflow.com/amzn/click/0534950973">Introduction to the Theory of Computation</a>" (by Sipser). It is very well written, and is a relatively new book.</p>

CC BY-SA 4.0
2019-09-03T17:01:57.160Z
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
CC BY-SA 4.0
2019-09-03T17:04:14.570Z
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
CC BY-SA 2.5
2010-10-05T17:36:13.393Z
I second Sipster. I use it for my course.
Dave Clarke
CC BY-SA 2.5
2010-10-05T18:21:11.890Z
I spent a whole summer doing problems from the old HU book. Fun times...
Suresh Venkat
CC BY-SA 2.5
2010-10-05T19:00:43.400Z
Yes, HU 2nd edition.
Kaveh
CC BY-SA 2.5
2010-10-05T19:05:50.887Z
@Kaveh: Now in the 3rd edition. See the link.
Sadeq Dousti
CC BY-SA 2.5
2010-10-05T19:19:04.323Z
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
CC BY-SA 2.5
2010-10-05T22:00:40.310Z
@Sadeq: I know, that is the reason I wrote 2nd edition.
Kaveh
CC BY-SA 2.5
2010-10-05T22:02:01.137Z
Have you tried D.-Z. Du and K. Ko, Problem Solving in Automata, Languages and Complexity, 2001?
Kaveh
CC BY-SA 2.5
2010-10-06T00:10:55.773Z
@Kaveh, in the 2nd edition of the Cinderella book all the good stuff has been taken out!
didest
CC BY-SA 2.5
2010-10-06T00:21:56.183Z
@Diego: I thought that was the third edition, are you sure?
Kaveh
CC BY-SA 2.5
2010-10-06T03:09:45.833Z
@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
CC BY-SA 2.5
2010-10-06T05:30:00.063Z
@Kaveh: I thought you wanted to contrast it from the 1st edition. Is the 3rd ed. even worse than the 2nd ed.?
Sadeq Dousti
CC BY-SA 2.5
2010-10-06T23:09:00.200Z
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
CC BY-SA 2.5
2010-10-06T23:11:06.293Z
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
CC BY-SA 2.5
2010-10-07T02:12:36.973Z
I strongly prefer Hopcroft&Ullman *without* Motwani.  HU&M took out all the good problems!
Jeffε
CC BY-SA 2.5
2010-10-07T16:29:45.443Z
@Sadeq,Diego: Yes, I have checked and noticed that I meant the 1st edition from 1979, not the 2nd one.
Kaveh
CC BY-SA 2.5
2010-10-07T16:47:56.837Z
@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
CC BY-SA 2.5
2010-10-07T16:56:32.420Z
@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
CC BY-SA 2.5
2010-10-07T18:37:38.183Z
@Kurt: Your comments are too good to be left as just comments! Why not post them as answers?
Sadeq Dousti
CC BY-SA 2.5
2010-10-05T17:34:43.080Z
2010-10-05T19:05:17.520Z
2010-10-05T19:05:17.520Z
Sadeq Dousti
<p>The one I'm using the most for my courses is <a href="http://books.google.com/books?id=mawCwVxkSbMC"><em>Elements of Automata Theory</em></a> 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.</p>

CC BY-SA 3.0
2013-11-29T04:33:33.910Z
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
CC BY-SA 2.5
2010-11-20T14:29:27.137Z
2010-11-20T14:29:27.137Z
Sylvain
<p>I have a soft spot for <em>Automata &amp; Computability</em> by Dexter Kozen (<a href="http://www.cs.cornell.edu/~kozen/papers/481.ps">table of contents and sample chapters</a> [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.</p>

CC BY-SA 2.5
2010-11-16T14:50:36.427Z
2010-11-16T14:50:36.427Z
mikero
<p>"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.</p>

CC BY-SA 2.5
2010-11-18T08:54:44.420Z
2010-11-18T08:54:44.420Z
Shambo
<p>"Applied Combinatorics on Words", by Lothaire, 2004</p>

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

<p>Best of all, it's free to download, and also includes solution sets:</p>

<p><a href="http://www-igm.univ-mlv.fr/~berstel/Lothaire/">http://www-igm.univ-mlv.fr/~berstel/Lothaire/</a></p>

CC BY-SA 2.5
2010-11-16T11:39:18.883Z
2010-11-16T11:39:18.883Z
s8soj3o289
<p>I'm not sure this is the best book to prepare for exams, but the book</p>

<blockquote>
  <p><strong><a href="http://books.google.com/books?id=qNdQAAAAMAAJ">Finite Automata; Behavior and Synthesis</a></strong> by B. A. Trakhtenbrot and Ya. M. Barzdinʹ</p>
</blockquote>

<p>is quite good.  It has a surprising number of great results that I have found especially helpful in research.</p>

CC BY-SA 2.5
2010-11-20T16:56:21.070Z
2010-11-20T16:56:21.070Z
Lev Reyzin
<blockquote>
<p><a href="https://bookstore.ams.org/emshat/" rel="nofollow noreferrer">Handbook of Automata Theory: Volumes I (Theoretical Foundations) and
II (Automata in Mathematics and Selected Applications)</a></p>
<p><a href="https://i.sstatic.net/Q7EIC.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Q7EIC.png" alt="enter image description here" /></a></p>
<p>Edited by Jean-Éric Pin: Université de Paris and CNRS, France</p>
<p>A publication of the European Mathematical Society</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p><strong>Readership</strong></p>
<p>Graduate students and researchers interested in mathematics and
computer science.</p>
</blockquote>

CC BY-SA 4.0
2022-01-08T17:15:28.967Z
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
CC BY-SA 4.0
2022-01-07T19:28:17.323Z
2022-01-07T19:28:17.323Z
Clément
<blockquote>
  <p><a href="http://rads.stackoverflow.com/amzn/click/0073191469" rel="nofollow">Introduction to languages and The theory of computation</a></p>
  
  <p>John C. Martin</p>
</blockquote>

<p>I highly recommend this book for a beginner and this is a perfect choice for someone who's looking for lots of examples.</p>

CC BY-SA 3.0
2013-09-25T21:14:37.490Z
2013-09-25T21:14:37.490Z
Tharindu Rusira
<p>I enjoy the following lecture notes by Jarkko Kari:
<a href="http://users.utu.fi/jkari/automata/" rel="nofollow">http://users.utu.fi/jkari/automata/</a></p>

<p>Brief course outline:</p>

<pre><code>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
</code></pre>

CC BY-SA 3.0
2013-11-28T12:11:22.717Z
2013-11-28T12:11:22.717Z
subshift
<p>" 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.</p>

CC BY-SA 3.0
2014-07-08T11:24:39.123Z
2014-07-08T11:24:39.123Z
Prateek Bhuwania
<blockquote>
<p><a href="http://computationbook.com/" rel="nofollow noreferrer">Understanding Computation</a></p>
<p>From Simple Machines to Impossible Programs</p>
</blockquote>
<p>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.</p>

CC BY-SA 3.0
2013-11-27T15:18:26.067Z
2013-11-27T15:18:26.067Z
2020-06-17T09:38:08.363Z
guhemama
<p>I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.</p>

<reference-request><automata-theory><fl.formal-languages>
Books on automata theory for self-study
user1652
# Books on automata theory for self-study

(Asked by: username_0 on 2010-10-05)

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

**Tags:** reference-request, automata-theory, fl.formal-languages

---

## 11 answers

### Answer by username_1 on 2010-10-05. Score: 36

The classical reference is "[Introduction To Automata Theory, Languages and Computation](http://rads.stackoverflow.com/amzn/click/0321462254)" (by Hopcroft, Motwani, and Ullman). Some people also recommend the much older "[Formal Languages and Their Relation to Automata](http://rads.stackoverflow.com/amzn/click/B000XI9B9A)" (by Hopcroft and Ullman).

I, however, like "[Introduction to the Theory of Computation](http://rads.stackoverflow.com/amzn/click/0534950973)" (by Sipser). It is very well written, and is a relatively new book.

> **Comments:**
> **username_3**: I second Sipster. I use it for my course.  
> **username_4**: I spent a whole summer doing problems from the old HU book. Fun times...  
> **username_5**: Yes, HU 2nd edition.  
> **username_1**: @Kaveh: Now in the 3rd edition. See the link.  
> **username_0**: 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.  
> **username_5**: @Sadeq: I know, that is the reason I wrote 2nd edition.  
> **username_5**: Have you tried D.-Z. Du and K. Ko, Problem Solving in Automata, Languages and Complexity, 2001?  
> **username_6**: @Kaveh, in the 2nd edition of the Cinderella book all the good stuff has been taken out!  
> **username_5**: @Diego: I thought that was the third edition, are you sure?  
> **username_6**: @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.  
> **username_1**: @Kaveh: I thought you wanted to contrast it from the 1st edition. Is the 3rd ed. even worse than the 2nd ed.?  
> **username_7**: 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  
> **username_7**: 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.  
> **username_8**: I strongly prefer Hopcroft&Ullman *without* Motwani.  HU&M took out all the good problems!  
> **username_5**: @Sadeq,Diego: Yes, I have checked and noticed that I meant the 1st edition from 1979, not the 2nd one.  
> **username_9**: @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.  
> **username_9**: @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.  
> **username_1**: @Kurt: Your comments are too good to be left as just comments! Why not post them as answers?  
> **username_2**: 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...  
> **username_2**: 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).  

---

### Answer by username_12 on 2010-11-16. Score: 10

I have a soft spot for *Automata & Computability* by Dexter Kozen ([table of contents and sample chapters](http://www.cs.cornell.edu/~kozen/papers/481.ps) [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.


---

### Answer by username_10 on 2010-11-20. Score: 9

The one I'm using the most for my courses is [*Elements of Automata Theory*](http://books.google.com/books?id=mawCwVxkSbMC) 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.

> **Comments:**
> **username_11**: If we are talking only about automata theory, this must be the best book about the subject. I'm reading it and loving it!  

---

### Answer by username_13 on 2010-11-18. Score: 6

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


---

### Answer by username_14 on 2010-11-16. Score: 5

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


---

### Answer by username_15 on 2010-11-20. Score: 5

I'm not sure this is the best book to prepare for exams, but the book

> **[Finite Automata; Behavior and Synthesis](http://books.google.com/books?id=qNdQAAAAMAAJ)** 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.


---

### Answer by username_16 on 2022-01-07. Score: 4

> [Handbook of Automata Theory: Volumes I (Theoretical Foundations) and
> II (Automata in Mathematics and Selected Applications)](https://bookstore.ams.org/emshat/)
>
> [![enter image description here](https://i.sstatic.net/Q7EIC.png)](https://i.sstatic.net/Q7EIC.png)
>
> 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.

> **Comments:**
> **username_17**: 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.  

---

### Answer by username_18 on 2013-09-25. Score: 2

> [Introduction to languages and The theory of computation](http://rads.stackoverflow.com/amzn/click/0073191469)
>
> 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.


---

### Answer by username_19 on 2013-11-28. Score: 1

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


---

### Answer by username_20 on 2014-07-08. Score: 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.


---

### Answer by username_21 on 2013-11-27. Score: 0

> [Understanding Computation](http://computationbook.com/)
>
> 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.


---

