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
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|
|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|
(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-|
|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|
|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
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.
|THIS BOOK IS A ONE STOP SOLUTION FOR GATE EXAM.|
Other Recommended Books-
Introduction to Automata Theory, Languages & Computation By Ullman-
Introduction to the Theory of Computation By Michael Sipser-