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-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Other Recommended Books-

 

Introduction to Automata Theory, Languages & Computation By Ullman-

 

 

Introduction to the Theory of Computation By Michael Sipser-