Introduction to Formal Languages & Automata | Automata Books

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 SectionsGATE Topics Covered
1All SectionsIntroduction
22.1Deterministic Finite Automata (DFA)
2.2Non-Deterministic Finite Automata (NFA)
2.3 to 2.4Equivalence of DFA and NFA, Minimizing States
33.1 to 3.2Regular Expression, Regular Language and Regular Grammar
44.1 to 4.3Closure Properties, Pumping Lemma for Regular Languages
55.1 to 5.3Context Free Grammars- Parsing and Ambiguity
66.1Grammar Transformations

(Removing Epsilon and Unit Productions)

6.2Chomsky and Greibach Normal Forms
77.1 to 7.3Non-Deterministic PDA, Deterministic PDA and Context-Free Languages
88.1Pumping Lemma for Context Free Languages
8.2Closure Properties of Context Free Languages
99.1 to 9.3Turing Machine
10All SectionsVariations of Turing Machine and Linear Bound Automata
11All SectionsHierarchy of Languages
12All SectionsUndecidability, 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.
22.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
33.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
44.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
55.1-2 to 5.1-22, 5.2-1 to 5.2-8, 5.2-10 to 5.2-16
66.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
77.1-1 to 7.1-15, 7.2-1 to 7.2-16, 7.3-1 to 7.3-18
88.1-1 to 8.1-15, 8.1-20, 8.2-1 to 8.2-19
99.1-2 to 9.1-12, 9.2-2 to 9.2-5
1010.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
1111.1-1 to 11.1-19, 11.2-1, 11.2-4, 11.2-7, 11.3-1 to 11.3-4
1212.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.




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





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-



Introduction to Formal Languages & Automata | Automata Books
Article Name
Introduction to Formal Languages & Automata | Automata Books
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.
Publisher Name
Gate Vidyalay
Publisher Logo