**Introduction to Formal Languages & Automata By Peter Linz**

This article reviews the book **“ An Introduction to Formal Languages and Automata“** by Peter Linz.

The article covers-

- Special features of book
- Analysis of Content
- Analysis of Exercises
- Necessary Instructions
- Conclusion

**Why Should Be Read?**

**Special Features of Book-**

The special features of this book are-

- It is the best book among the all the available reference books for this subject.
- It covers all the GATE topics in detail without getting verbose.
- It explains the content in a pretty simple and straight forward language.
- It makes the subject fun to read.
- It is suitable for beginners as well as intermediate students.
- Turing Machines and Undecidability are covered in a very clear and crisp manner.
- It contains large number of exercise questions yet the quality is pretty good.

**Analysis of Content-**

The following table analyzes sections of the book that are relevant for GATE-

Chapter No. | GATE Relevant Sections | GATE Topics Covered |

1 | All Sections | Introduction |

2 | 2.1 | Deterministic Finite Automata (DFA) |

2.2 | Non-Deterministic Finite Automata (NFA) | |

2.3 to 2.4 | Equivalence of DFA and NFA, Minimizing States | |

3 | 3.1 to 3.2 | Regular Expression, Regular Language and Regular Grammar |

4 | 4.1 to 4.3 | Closure Properties, Pumping Lemma for Regular Languages |

5 | 5.1 to 5.3 | Context Free Grammars- Parsing and Ambiguity |

6 | 6.1 | Grammar Transformations (Removing Epsilon and Unit Productions) |

6.2 | Chomsky and Greibach Normal Forms | |

7 | 7.1 to 7.3 | Non-Deterministic PDA, Deterministic PDA and Context-Free Languages |

8 | 8.1 | Pumping Lemma for Context Free Languages |

8.2 | Closure Properties of Context Free Languages | |

9 | 9.1 to 9.3 | Turing Machine |

10 | All Sections | Variations of Turing Machine and Linear Bound Automata |

11 | All Sections | Hierarchy of Languages |

12 | All Sections | Undecidability, TM Halting Problem, Post Correspondence Problem |

**Covering Only These Sections Is Enough**

**Analysis of Exercises-**

The following table analyzes exercises of the book that are relevant for GATE-

Chapter No. | Question No. |

2 | 2.1-1 to 2.1-16, 2.1-24, 2.2-2 to 2.2-16, 2.3-1, 2.3-2, 2.3-3, 2.3-6, 2.3-7, 2.3-8, 2.3-9, 2.3-11, 2.3-12, 2.3-14, 2.3-15, 2.4-1, 2.4-2, 2.4- 4, 2.4-5, 2.4-9 |

3 | 3.1-1 to 3.1-17, 3.1-24, 3.1-25, 3.1-26, 3.2-1 to 3.2-6, 3.2-8 to 3.2- 13, 3.2-17, 3.2-18, 3.3-1 to 3.3-13, 3.3-16 |

4 | 4.1-2, 4.1-5, 4.1-6 to 4.1-18, 4.1-22 to 4.1-26, 4.3-1 to 4.3-15, 4.3- 17, 4.3-18 |

5 | 5.1-2 to 5.1-22, 5.2-1 to 5.2-8, 5.2-10 to 5.2-16 |

6 | 6.1-2, 6.1-3, 6.1-5 to 6.1-9, 6.1-14, 6.1-19, 6.1-22 to 6.1-24, 6.2-2 to 6.2-16 |

7 | 7.1-1 to 7.1-15, 7.2-1 to 7.2-16, 7.3-1 to 7.3-18 |

8 | 8.1-1 to 8.1-15, 8.1-20, 8.2-1 to 8.2-19 |

9 | 9.1-2 to 9.1-12, 9.2-2 to 9.2-5 |

10 | 10.1-1, 10.1-4, 10.1-7, 10.2-1 to 10.2-6, 10.4-5, 10.4-8, 10.4-9, 10.5-4 to 10.5-6 |

11 | 11.1-1 to 11.1-19, 11.2-1, 11.2-4, 11.2-7, 11.3-1 to 11.3-4 |

12 | 12.1-5, 12.1-7, 12.1-9, 12.1-13, 12.1-16, 12.2-2 to 12.2-8, 12.3-1, 12.3-3, 12.3-5, 12.4-2 to 12.4-9 |

**Practicing Only These Exercises Is Enough**

**Necessary Instructions-**

Keep the following instructions in mind while reading the book-

- The book has nearly 400 pages.
- The number of pages is considerably less as compared to other books.
- Apart from two chapters, all the chapters have GATE relevant topics.
- So, there is not much to filter while reading the book.
- Lay down extra emphasis on the topics of Undecidability.
- This portion gets asked every year in the GATE exam.
- Sections like Regular Languages and CFLs are also asked every year.
- The book contains the proofs for theorems but they are not required for GATE.
- You may go through the proofs for thorough understanding if you have ample time.
- Once you start understanding the intuition of proofs, you will start loving this subject.
- The questions asked in exam are numerical in nature.
- So, focus on practicing numerical questions for thorough grip over the subject.
- Solving even 75% of the exercise questions mentioned above is more than enough for GATE.

**Conclusion-**

- The content of this textbook is quite close to all the topics mentioned in the GATE syllabus.
- So, reading this book will ensure all the topics are covered.
- The exercise questions are pretty good for numerical practice while preparing for GATE.

THIS BOOK IS A ONE STOP SOLUTION FOR GATE EXAM. |

**Amazon Rating**

**Student’s Reviews-**

**Ot****her Recommended Books-**

**Introduction to Automata Theory, Languages & Computation By Ullman-**

**Introduction to the Theory of Computation By Michael Sipser-**

Summary

Article Name

Introduction to Formal Languages & Automata | Automata Books

Description

Automata Books for GATE CSE- Introduction to Formal Languages and Automata by Peter Linz is the best Theory of Automata and Computation book for GATE CSE. Introduction to Automata Theory, Languages and Computation by Ullman and Introduction to the Theory of Computation by Michael Sipser are other recommended books.

Author

Akshay Singhal

Publisher Name

Gate Vidyalay

Publisher Logo