Book description
Introduction to Formal Languages, Automata Theory and Computation presents the theoretical concepts in a concise and clear manner, with an indepth 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. TwoWay 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. ContextFree 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 Rewriting
 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 kturn 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
video
Python Fundamentals
51+ hours of video instruction. Overview The professional programmer’s Deitel® video guide to Python development with …
book
Head First Design Patterns
What’s so special about design patterns? At any given moment, someone struggles with the same software …
book
Programming Rust, 2nd Edition
The Rust programming language offers the rare and valuable combination of statically verified memory safety and …
book
Building Microservices, 2nd Edition
Distributed systems have become more finegrained as organizations shift from codeheavy monolithic applications to smaller, selfcontained …