Book description
Introduction to Formal Languages, Automata Theory and Computation presents the theoretical concepts in a concise and clear manner, with an in-depth coverage of formal grammar and basic automata types.
Table of contents
- Copyright
- About the Authors
- Preface
- Acknowledgements
- 1. Preliminaries
- 2. Grammars
- 3. Finite State Automata
- 4. Finite State Automata: Characterization, Properties, and Decidability
- 5. Finite State Automata with Output and Minimization
-
6. Variants of Finite Automata
- 6.1. Two-Way Finite Automata
- 6.2. Multihead Finite State Automata
- 6.3. Probabilistic Finite Automata
- 6.4. Weighted Finite Automata and Digital Images
- Problems and Solutions
- Exercises
- 7. Pushdown Automata
- 8. Context-Free Grammars–Properties and Parsing
- 9. Turing Machines
- 10. Variations of Turing Machines
-
11. Universal Turing Machine and Decidability
- 11.1. Encoding and Enumeration of Turing Machines
- 11.2. Recursive and Recursively Enumerable Sets
- 11.3. Universal Turing Machine
- 11.4. Problems, Instances, and Languages
- 11.5. Rice’s Theorem
- 11.6. Reduction of Problems to Show Undecidability
- 11.7. Post’s Correspondence Problem
- 11.8. Computable Functions
- Problems and Solutions
- Exercises
- 12. Time and Space Complexity
-
13. Recent Trends and Applications
- 13.1. Regulated Re-writing
- 13.2. Marcus Contextual Grammars
- 13.3. Lindenmayer Systems
-
13.4. Grammar Systems and Distributed Automata
- Grammar Systems
- 13.4.1. CD Grammar Systems
- 13.4.2. PC Grammar Systems
- 13.4.3. Distributed Automata
- Distributed Nondeterministic FSA
- Power of Acceptance of Different Modes
- Distributed Nondeterministic Pushdown Automata
- Acceptance Power of NPDA
- Acceptance by Empty Store
- Equivalence
- Distributed k-turn PDA
-
14. New Models of Computation
- 14.1. DNA Computing
-
14.2. Membrane Computing
- Operations with Strings and Languages
- P Systems with Labeled Membranes
- Rewriting P Systems
- P Systems with Sequential Rewriting
- P Systems based on Sequential Rewriting with Membranes of Variable Thickness
- P Systems with Replicated Rewriting
- Solving SAT and HPP
- P Systems with Active Membranes
- Solving SAT in Linear Time
- Tissue P Systems
- Multiple Choice Questions (Set I)
- Multiple Choice Questions (Set II)
- Bibliography
- Illustrations
Product information
- Title: Introduction to Formal Languages, Automata Theory and Computation
- Author(s):
- Release date: April 2009
- Publisher(s): Pearson India
- ISBN: 9788131723562
You might also like
book
Introduction to Automata Theory, Formal Languages and Computation
Formal languages and automata theory is the study of abstract machines and how these can be …
book
Express Learning: Automata Theory and Formal Languages
Express Learning is a series of books designed as quick reference guides to important undergraduate computer …
book
Formal Languages and Automata Theory
Formal Languages and Automata Theory deals with the mathematical abstraction model of computation and its relation …
book
Formal Languages and Computation
This computer science book gives a clear, comprehensive introduction to formal language theory and its applications …