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