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

1. Cover
2. Title page
3. Brief Contents
4. Contents
5. Preface
6. Acknowledgements
7. List of Important Symbols
8. List of Important Abbreviations
10. 1. Mathematical Preliminaries and Formal Languages
1. 1.1 Set Theory
2. 1.2 Relations
3. 1.3 Functions
4. 1.4 Alphabet, String and Language
5. 1.5 Graphs and Trees
6. 1.6 Theorem Proving
7. Summary
9. Fill in the Blanks
10. Objective Question Bank
11. Exercises
11. 2. Finite Automata
1. 2.1 Finite-state Machine
2. 2.2 Language Acceptance
3. 2.3 Two Types of Finite Automata
4. 2.4 Equivalence of DFAs and NFAs
5. 2.5 Converting NFA (MN) to DFA (MD)âSubset Construction
6. 2.6 NFA with Epsilon-(Îµ) Transitions
7. 2.7 Comparison Method for Testing Equivalence of Two FAs
8. 2.8 Reduction of Number of States in FA
9. 2.9 Finite Automata with Output
10. 2.10 Applications of Finite Automata with Output
11. Solved Problems
12. Summary
14. Fill in the Blanks
15. Objective Question Bank
16. Exercises
12. 3. Regular Languages and Regular Grammars
1. 3.1 Regular Expressions
2. 3.2 Regular Sets
3. 3.3 Identity Rules for Regular Expressions
4. 3.4 Algebraic Laws for Regular Expressions
5. 3.5 Equivalence of Finite Automata with Regular Expressions
6. 3.6 Constructing Regular Expression for Given DFA
7. 3.7 Pumping Lemma of Regular Expressions
8. 3.8 Regular Grammar
9. 3.9 Closure Properties of Regular Sets
10. 3.10 Applications of Regular Expressions
11. 3.11 Decision Properties of Regular Languages
12. Solved Problems
13. Summary
15. Fill in the Blanks
16. Objective Question Bank
17. Exercises
13. 4. Context Free Grammars and Context Free Languages
1. 4.1 Context Free Grammars
2. 4.2 Derivation of CFGs
3. 4.3 Understanding the Language Defined by Grammars
4. 4.4 Ambiguous Grammar
5. 4.5 Simplification of Grammars
6. 4.6 Normal Forms
7. 4.7 Pumping Lemma for CFL
8. 4.8 Decision Algorithms for CFLs
9. 4.9 Membership
10. 4.10 Closure Properties of CFLs
11. 4.11 Applications of CFG
12. Solved Problems
13. Summary
15. Fill in the Blanks
16. Objective Question Bank
17. Exercises
14. 5. Push Down Automata
1. 5.1 Pushdown Automata
2. 5.2 Equivalence of Acceptance of Final State and Empty Stack
3. 5.3 Types of PDAs
4. 5.4 Equivalence of PDAâs and CFGâs
5. 5.5 Two-stack PDA
6. 5.6 Applications of PDA
7. Solved Problems
8. Summary
10. Fill in the Blanks
11. Objective Question Bank
12. Exercises
15. 6. Turing Machines
1. 6.1 Turing Assumptions
2. 6.2 Turing Machine as a Computational Machine
3. 6.3 Techniques for Turing Machine Construction
4. 6.4 Types of Turing Machines
5. 6.5 Churchâs Thesis
6. 6.6 Turing Machines as Enumerators
7. 6.7 Universal Turing Machine
8. 6.8 Counter Machine
9. 6.9 Recursive and Recursively Enumerable Languages
10. 6.10 Linear Bound Automata and Context Sensitive Language
11. Solved Problems
12. Summary
14. Fill in the Blanks
15. Objective Question Bank
16. Exercises
16. 7. Undecidability and Computability
1. 7.1 Decision Problems
2. 7.2 Decidability and Decidable Languages
3. 7.3 Halting Problem
4. 7.4 Diagonalization Method
5. 7.5 Postâs Correspondence Problem
6. 7.6 Reducibility
7. 7.7 Recursion Theorem
8. 7.8 Riceâs Theorem
9. 7.9 Ackermannâs Function
10. Solved Problems
11. Summary
13. Fill in the Blanks
14. Objective Question Bank
15. Exercises
17. 8. Non-deterministic Polynomial Completeness
1. 8.1 NP-hard and NP-complete
2. 8.2 P Problems
3. 8.3 NP Problems
4. 8.4 Tractable Problems
5. 8.5 NP-complete
6. 8.6 NP-hard
7. 8.7 Examples of Problems in Different Classes
8. 8.8 NP-completeness
9. 8.9 Reduction
10. Solved Problems
11. Summary
13. Fill in the Blanks
14. Objective Question Bank
15. Exercises
18. 9. LR(k) and LL(1) Grammars
19. Appendix A: Proposition and Predicate Logic
20. Appendix B: Frequently Asked University Questions with Solutions
21. References