## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

3. Preface
4. Acknowledgements
5. 1. Preliminaries
1. 1.1. Sets, Relations, and Functions
2. 1.2. Methods of Proof
3. 1.3. Graphs
4. 1.4. Languages: Basic Concepts
5. Problems and Solutions
6. Exercises
6. 2. Grammars
1. 2.1. Definitions and Classification of Grammars
2. 2.2. Ambiguity
3. 2.3. Simplification of CFGs
4. 2.4. Normal Forms
1. Weak Chomsky Normal Form
2. Chomsky Normal Form
3. Strong Chomsky Normal Form
4. Greibach Normal Form
5. Problems and Solutions
6. Exercises
7. 3. Finite State Automata
1. 3.1. Deterministic Finite State Automaton (DFSA)
2. 3.2. Non-deterministic Finite State Automaton (NFSA)
3. 3.3. Regular Expressions
4. Problems and Solutions
5. Exercises
8. 4. Finite State Automata: Characterization, Properties, and Decidability
1. 4.1. FSA and Regular Grammars
2. 4.2. Pumping Lemma for Regular Sets
3. 4.3. Closure Properties
4. 4.4. Decidability Theorems
5. Problems and Solutions
6. Exercises
9. 5. Finite State Automata with Output and Minimization
1. 5.1. Myhill-Nerode Theorem
2. 5.2. Finite Automata with Output
3. Problems and Solutions
4. Exercises
10. 6. Variants of Finite Automata
1. 6.1. Two-Way Finite Automata
2. 6.2. Multihead Finite State Automata
3. 6.3. Probabilistic Finite Automata
4. 6.4. Weighted Finite Automata and Digital Images
1. 6.4.1. Finite Automata and Black-White Images
2. 6.4.2. Weighted Finite Automata and Gray-Scale Images
3. 6.4.3. Inferencing and De-Inferencing
4. 6.4.4. Transformations on Digital Images
5. Problems and Solutions
6. Exercises
11. 7. Pushdown Automata
1. 7.1. The Pushdown Automaton
2. 7.2. Equivalence between Acceptance by Empty Store and Acceptance by Final State
3. 7.3. Equivalence of CFG and PDA
4. Problems and Solutions
5. Exercises
12. 8. Context-Free Grammars–Properties and Parsing
1. 8.1. Pumping Lemma for CFL
2. 8.2. Closure Properties of CFL
3. 8.3. Decidability Results for CFL
4. 8.4. SubFamilies of CFL
5. 8.5. Parikh Mapping and Parikh’s Theorem
6. 8.6. Self-embedding Property
7. 8.7. Homomorphic Characterization
8. Problems and Solutions
9. Exercises
13. 9. Turing Machines
1. 9.1. Turing Machine as an Acceptor
2. 9.2. Turing Machine as a Computing Device
3. 9.3. Techniques for Turing Machine Construction
4. Problems and Solutions
5. Exercises
14. 10. Variations of Turing Machines
1. 10.1. Generalized Versions
2. 10.2. Restricted Turing Machines
3. 10.3. Turing Machines as Enumerators
4. 10.4. Equivalence Between Turing Machines and Type 0 Languages
5. 10.5. Linear-Bounded Automata
6. 10.6. Gödel Numbering
7. Problems and Solutions
8. Exercises
15. 11. Universal Turing Machine and Decidability
1. 11.1. Encoding and Enumeration of Turing Machines
2. 11.2. Recursive and Recursively Enumerable Sets
3. 11.3. Universal Turing Machine
4. 11.4. Problems, Instances, and Languages
5. 11.5. Rice’s Theorem
6. 11.6. Reduction of Problems to Show Undecidability
7. 11.7. Post’s Correspondence Problem
8. 11.8. Computable Functions
9. Problems and Solutions
10. Exercises
16. 12. Time and Space Complexity
1. 12.1. The RAM Model
2. 12.2. Time and Tape Complexity of Turing Machines
3. Problems and Solutions
4. Exercises
17. 13. Recent Trends and Applications
1. 13.1. Regulated Re-writing
1. Matrix Grammar
2. 13.2. Marcus Contextual Grammars
1. 13.2.1. Definitions and Examples
2. 13.2.2. Generative Capacity
3. 13.2.3. Closure and Decidability Properties of Contextual Languages
3. 13.3. Lindenmayer Systems
4. 13.4. Grammar Systems and Distributed Automata
1. Grammar Systems
2. 13.4.1. CD Grammar Systems
3. 13.4.2. PC Grammar Systems
4. 13.4.3. Distributed Automata
5. Distributed Nondeterministic FSA
6. Power of Acceptance of Different Modes
7. Distributed Nondeterministic Pushdown Automata
8. Acceptance Power of NPDA
9. Acceptance by Empty Store
10. Equivalence
11. Distributed k-turn PDA
18. 14. New Models of Computation
1. 14.1. DNA Computing
2. 14.2. Membrane Computing
19. Multiple Choice Questions (Set I)
20. Multiple Choice Questions (Set II)
21. Bibliography
22. Illustrations