₹295
Authors: Shanthi D, Uma Maheswari N, Jeyanthi S
ISBN: 9789388005104
Copy Right Year: 2019
Pages: 464
Binding: Soft Cover
Publisher: Yes Dee Publishing
This book is designed for fundamental courses on automata theory and formal languages. It emphasizes on topics such as mathematical models, finite automata, context-free grammars, pushdown automata, Turing machine, undecidability, computational complexity, P and NP completeness.
• Explains all types of problem solving in formal languages and automata models.
• Presents clear graphical representation for DFA, NDFA, PDA and Turing machine.
| Weight | .5 kg |
|---|---|
| Dimensions | 23 × 16 × 2 cm |
Chapter 1 Finite Automata
1.1 Introduction
1.2 Basic Mathematical Notation and Techniques
1.2.1 Formal Proof
1.2.2 Deductive Proofs
1.2.3 If-then Statements
1.2.4 If and only-If Statement
1.2.5 Additional Forms of Proof
1.2.6 Inductive Proofs
1.2.7 Problems in Induction
1.3 Basic Definitions
1.4 Finite State Systems
1.5 Finite Automaton
1.6 Deterministic Finite Automata and Nondeterministic Finite Automata
1.6.1 Deterministic Finite Automata
1.6.2 Nondeterministic Finite Automata
1.7 Finite Automaton with ε-Moves
1.7.1 Nondeterministic Finite Automata with ε-Moves
1.8 Equivalence of NDFA and DFA
1.9 Equivalence of NDFAs with and without ε-Moves
Solved Problems 1.1
Solved Problems 1.2
Solved Problems 1.3
Solved Problems 1.4
Points to Remember
University Questions
Chapter 2 Regular Expression and Languages
2.1 Introduction
2.2 Regular Languages
2.3 Regular Expression
2.4 Equivalence of Finite Automaton and Regular Expressions
2.4.1 Conversion of Finite Automata (DFA) to Regular Expressions
Solved Examples 2.1
Solved Examples 2.2
2.4.2 Conversion of Regular Expressions to Finite Automata
Solved Examples 2.3
2.5 Pumping Lemma for Regular Sets
2.6 Problems based on Pumping Lemma
Solved Examples 2.4
2.7 Closure Properties of Regular Languages
2.8 Minimization of DFA
Solved Examples 2.5
Points to Remember
University Questions
Chapter 3 Context-Free Grammar and Languages
3.1 Introduction
3.2 Types of Grammar
3.3 Context-Free Grammars and Languages
3.3.1 Context-Free Grammar
3.4 Derivations and Languages
3.5 Ambiguity
3.5.1 Ambiguity in Grammars and Languages
3.5.2 Unambiguous Grammar
3.6 Relationship between Derivation and Derivation Trees
Solved Examples 3.1
Points to Remember
University Questions
Chapter 4 Pushdown Automata
4.1 Introduction
4.1.1 Definition of PDA
4.1.2 Graphical Notation for PDA
4.2 Moves
4.3 Instantaneous Descriptions of PDA
4.3.1 Three Important Principles about ID
Solved Examples 4.1
4.4 Language of a PDA
4.4.1 Conversion of Final State and Empty Stack
4.5 Equivalence of PDAs and CFGs
4.5.1 Solved Examples for Conversion of Context-Free Grammar to Pushdown
Automata
4.5.2 Solved Examples for Conversion of Pushdown Automata to Context-Free
Grammar
4.6 Types of PDA
4.6.1 Nondeterministic Pushdown Automata
4.6.2 Deterministic Pushdown Automata
Solved Examples 4.2
Points to Remember
University Questions
Chapter 5 Properties of Context-Free Languages
5.1 Introduction
5.2 Simplification of CFG
5.2.1 Elimination of Useless Symbols
5.2.2 Elimination of Unit Productions
5.2.3 Elimination of Null or Epsilon Productions
5.3 Normal Forms
5.3.1 Chomsky Normal Form
5.3.2 Greibach Normal Form
5.3.3 Problems Related to CNF and GNF
5.4 Pumping Lemma for CFL
5.4.1 Problems based on Pumping Lemma
Solved Examples 5.1
5.5 Closure Properties of CFL
Points to Remember
University Questions
Chapter 6 Turing Machines
6.1 Introduction
6.1.1 Model of a TM
6.1.2 Move of a Turing Machine
6.1.3 Notation for a Turing Machine
6.1.4 Instantaneous Descriptions for TM: (ID) [Configuration of a TM]
6.1.5 Language of a TM
6.1.6 Representations for TM
6.2 Computable Languages and Functions
Solved Examples 6.1
6.3 Techniques for Turing Machine Construction
6.3.1 Storage in the Finite Control or State
6.3.2 Checking off Symbols
6.3.3 Subroutines
6.3.4 Multiple Tracks
6.4 Multi-Head and Multi-Tape Turing Machines
6.5 Nondeterministic Turing Machine
6.6 The Halting Problem
6.7 Partial Solvability
6.8 Problems about Turing Machine
6.9 Chomskian Hierarchy of Languages
Points to Remember
University Questions
Chapter 7 Un decidability
7.1 Unsolvable Problems and Computable Functions
7.2 Primitive Recursive Functions
Solved Examples 7.1
7.3 Recursive and Recursively Enumerable Languages
7.3.1 A Language is not Recursively Enumerable
Solved Examples 7.2
7.3.2 An Un decidable Problem Recursively Enumerable
7.4 Universal Turing Machine (UTM)
7.4.1 Un decidable Problems about Turing Machines
7.4.2 Post Correspondence Problem (PCP)
Solved Examples 7.3
Solved Examples 7.4
Points to Remember
University Questions
Chapter 8 Measuring and Classifying Complexity
8.1 Tractable and Intractable Problems
8.2 P and NP Completeness
8.3 Polynomial Time Reductions
Points to Remember
University Questions
Appendix – University Question
D Shanthi is Professor and Head, Department of Computer Science and Engineering at PSNA College of Engineering and Technology, Dindigul, Tamil Nadu. She received her Ph.D. in Computer Science and Engineering from Birla Institute of Technology, Ranchi, India. She has 26 years of teaching experience which includes 16 years of research experience. She has published more than 60 papers in international conferences and journals and also published 10 books in computing and applications.
N Uma Maheswari is Professor, Department of Computer Science and Engineering at PSNA College of Engineering and Technology, Dindigul, Tamil Nadu. She received her Ph.D. in Information and Communication Engineering from Anna University, Chennai. She has 18 years of teaching experience which includes 13 years of research experience. She has published 30 papers in international journals, 2 papers in national journals, and presented 32 papers at international conferences and 15 papers at national conferences. She has co-authored a book on Compiler Design published by Yes Dee.
S Jeyanthi is Associate Professor, Department of Computer Science and Engineering at PSNA College of Engineering and Technology, Dindigul, Tamil Nadu. She received her Ph.D. in Information and Communication Engineering from Anna University, Chennai. She has totally 14 years of teaching experience which includes 7 years of research experience. She has published 15 papers in international journals, 12 papers in international conferences and 6 papers in national conferences. She has co-authored a book on Compiler Design published by Yes Dee.
Here's your new product tab.
Reviews
There are no reviews yet.