# 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

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

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

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