Book description
Formal Languages and Automata Theory deals with the mathematical abstraction model of computation and its relation to formal languages. This book is intended to expose students to the theoretical development of computer science. It also provides conceptual tools that practitioners use in computer engineering. An assortment of problems illustrative of each method is solved in all possible ways for the benefit of students. The book also presents challenging exercises designed to hone the analytical skills of students.Table of contents
 Cover
 Title page
 Brief Contents
 Contents
 Preface
 Acknowledgements
 List of Important Symbols
 List of Important Abbreviations
 About the Authors
 1. Mathematical Preliminaries and Formal Languages

2. Finite Automata
 2.1 Finitestate Machine
 2.2 Language Acceptance
 2.3 Two Types of Finite Automata
 2.4 Equivalence of DFAs and NFAs
 2.5 Converting NFA (MN) to DFA (MD)—Subset Construction
 2.6 NFA with Epsilon(ε) Transitions
 2.7 Comparison Method for Testing Equivalence of Two FAs
 2.8 Reduction of Number of States in FA
 2.9 Finite Automata with Output
 2.10 Applications of Finite Automata with Output
 Solved Problems
 Summary
 Short Answers
 Fill in the Blanks
 Objective Question Bank
 Exercises

3. Regular Languages and Regular Grammars
 3.1 Regular Expressions
 3.2 Regular Sets
 3.3 Identity Rules for Regular Expressions
 3.4 Algebraic Laws for Regular Expressions
 3.5 Equivalence of Finite Automata with Regular Expressions
 3.6 Constructing Regular Expression for Given DFA
 3.7 Pumping Lemma of Regular Expressions
 3.8 Regular Grammar
 3.9 Closure Properties of Regular Sets
 3.10 Applications of Regular Expressions
 3.11 Decision Properties of Regular Languages
 Solved Problems
 Summary
 Short Answers
 Fill in the Blanks
 Objective Question Bank
 Exercises

4. Context Free Grammars and Context Free Languages
 4.1 Context Free Grammars
 4.2 Derivation of CFGs
 4.3 Understanding the Language Defined by Grammars
 4.4 Ambiguous Grammar
 4.5 Simplification of Grammars
 4.6 Normal Forms
 4.7 Pumping Lemma for CFL
 4.8 Decision Algorithms for CFLs
 4.9 Membership
 4.10 Closure Properties of CFLs
 4.11 Applications of CFG
 Solved Problems
 Summary
 Short Answers
 Fill in the Blanks
 Objective Question Bank
 Exercises
 5. Push Down Automata

6. Turing Machines
 6.1 Turing Assumptions
 6.2 Turing Machine as a Computational Machine
 6.3 Techniques for Turing Machine Construction
 6.4 Types of Turing Machines
 6.5 Church’s Thesis
 6.6 Turing Machines as Enumerators
 6.7 Universal Turing Machine
 6.8 Counter Machine
 6.9 Recursive and Recursively Enumerable Languages
 6.10 Linear Bound Automata and Context Sensitive Language
 Solved Problems
 Summary
 Short Answers
 Fill in the Blanks
 Objective Question Bank
 Exercises

7. Undecidability and Computability
 7.1 Decision Problems
 7.2 Decidability and Decidable Languages
 7.3 Halting Problem
 7.4 Diagonalization Method
 7.5 Post’s Correspondence Problem
 7.6 Reducibility
 7.7 Recursion Theorem
 7.8 Rice’s Theorem
 7.9 Ackermann’s Function
 Solved Problems
 Summary
 Short Answers
 Fill in the Blanks
 Objective Question Bank
 Exercises
 8. Nondeterministic Polynomial Completeness

9. LR(k) and LL(1) Grammars
 9.1 LL(1) Grammar
 9.2 Rules for Verifying Whether the Given Grammar Is LL(1) or Not
 9.3 LR(K) Grammars
 9.4 Properties of LR(k) Grammars
 9.5 Construction of LR(0) Items for Context Free Grammars
 9.6 Definition of LR(0) Grammar
 9.7 LR(1) Grammar
 Solved Problems
 Summary
 Short Answers
 Fill in the Blanks
 Objective Question Bank
 Exercises

Appendix A: Proposition and Predicate Logic
 A.1 Propositions
 A.2 Connectives
 A.3 WellFormed Formula
 A.3.1 Truth Table for a Wellformed Formula
 A.4 Logical Identities
 A.5 Normal Forms of Wellformed Formals
 A.5.1 Construction to Obtain a Disjunctive Normal Form of a Given Formula
 A.6 Principal Disjunctive Normal Form
 A.6.1 Construction to Obtain the Principal Disjunctive Normal Form of a Given Formula
 A.7 Predicate Calculus
 A.8 Universal and Existential Quantifier
 A.9 Wellformed Formulas of Predicate Calculus
 A.10 Rules of Inference for Predicate Calculus
 Summary
 Appendix B: Frequently Asked University Questions with Solutions
 References
 Copyright
Product information
 Title: Formal Languages and Automata Theory
 Author(s):
 Release date: April 2015
 Publisher(s): Pearson Education India
 ISBN: 9789332558274
You might also like
book
An Introduction to Formal Languages and Automata, 6th Edition
The Sixth Edition of An Introduction to Formal Languages and Automata provides an accessible, studentfriendly presentation …
book
Essentials of Discrete Mathematics, 3rd Edition
Written for the oneterm course, the Third Edition of Essentials of Discrete Mathematics is designed to …
book
Data Science from Scratch, 2nd Edition
To really learn data science, you should not only master the tools—data science libraries, frameworks, modules, …
book
Head First Design Patterns, 2nd Edition
You know you don’t want to reinvent the wheel, so you look to design patterns—the lessons …