Description
The aim of this book is to bring light to the computational phenomena. The traditional vehicle for studying computation in general is to introduce a model and then generalize. Chapter 1 deals with various mathematical preliminaries that include the concept of graphs, trees, sets, relations, strings, abstract languages and mathematical induction. It also incorporates regular languages, finite state automata, its types, proofs, theorems and lemma with sufficient number of solved problems with a syntactically simple language. Chapter 2 and 3 deals with formal grammar, hierarchy of grammars, context free grammar, pushdown automata and properties of context free languages. Chapter 4 illustrates about Turing machine and more emphasis on their role as a general model of computation. Chapter 5 focuses on undecidability and more stress has been placed on polynomial-time decidability, the sets P, NP and NP completeness including computable functions with adequate examples.
Table of Content
Chapter-1 FINITE AUTOMATA
1.1 Strings, Alphabets and Languages
1.1.1 Strings
1.1.2 Alphabets
1.1.3 Languages
1.2 Graphs and Trees
1.2.1 Graphs
1.2.2 Trees
1.3 Sets and Relations
1.3.1 Sets
1.3.2 Relations
1.4 Finite State Systems
1.5 Finite Automata (FA) or Finite State Automata (FSA)
1.5.1 Deterministic Finite Automata (DFA)
1.5.2 Non-deterministic Finite Automata (NFA)
1.6 Finite Automata with ε (Epsilon)Moves
1.7 Regular Expressions
1.7.1 Definition of Regular Expression (RE)
1.7.2 Applications of Regular Expression
1.8 Equivalence of NFA and DFA
1.9 Equivalence of NFA with and without Epsilon Moves
1.10 Equivalence of ε-NFA and DFA
1.11 Regular Expressions and Finite Automata
1.11.1 Conversion of RE to NFA- ε Transitions (Thompson’s Construction)
1.11.2 Conversion of ε-NFA to DFA
1.11.3 Conversion from DFA to RE
1.12 Equivalence and Minimization of DFA
1.13 Proving Languages not to be Regular
1.13.1 Regular Language
1.13.2 Pumping Lemma for Regular Language
1.13.3 Applications of the Pumping Lemma
1.13.4 Closure Properties of Regular Set
1.14 Problems based on Pumping Lemma
Chapter-2 GRAMMAR
2.1 Definition of Grammar
2.2 Types of Grammar
2.3 Context Free Grammars and Languages
2.3.1 Languages of CFG
2.3.2 Applications of CFG
2.4 Derivations of CFG
2.4.1 Types of Derivation
2.5 Derivation Trees /Parse Trees
2.5.1 Definition of Parse Tree
2.5.2 Sub-tree
2.5.3 Sentential Form
2.6 Ambiguity in Grammar and Languages
2.7 Relationship between Derivation Trees and Derivations
2.8 Simplification of CFG
2.8.1 Removing Useless Symbols
2.8.2 Eliminating Null (Empty) Production
2.8.3 Eliminating Unit Production
2.9 Normal Forms of CFG
2.9.1 Chomsky Normal Form(CNF)
2.9.2 Greibach Normal Form(GNF)
Chapter-3 PUSHDOWN AUTOMATA
3.1 Pushdown Automata (PDA)
3.2 Definition of PDA
3.3 Transition Function of PDA
3.4 Graphical Notation for PDA
3.5 Types of Language Acceptance by a PDA
3.6 Instantaneous Description (ID)of a PDA
3.7 Equivalence of Acceptance of PDA from Empty Stack to Final State
3.8 Equivalence of Acceptance of PDA from Final State to Empty Stack
3.9 Equivalence of PDA and CFG
3.9.1 Conversion from PDA to CFG
3.9.2 Conversion from CFG to PDA
3.10 Deterministic PDA
3.11 Pumping Lemma for Context Free Language
3.11.1 The Context Free Pumping Lemma
Chapter-4 TURING MACHINES
4.1 Turing Machines
4.1.1 Definition of Turing Machine
4.1.2 Instantaneous Description of a Turing Machine
4.1.3 Move in a Turing Machine
4.1.4 Language of a Turing Machine
4.1.5 Transition Diagram and Notations
4.2 Computable Languages and Functions
4.3 Programming Techniques for Turing Machine Construction
4.3.1 Storage in the Finite Control
4.3.2 Multiple Tracks
4.3.3 Sub-routines
4.4 Multihead Turing Machine
4.5 Multitape Turing Machine
4.6 Halting Problem
4.7 Partial Solvability
4.7.1 Properties of Partial Solvability
4.8 Chomskian Hierarchy of Languages
Chapter-5 UNSOLVABLE PROBLEMS AND COMPUTABLE FUNCTIONS
5.1 Recursive Language
5.2 Decidable and Undecidable Problems
5.3 A Language that is not Recursively Enumerable
5.3.1 Enumerating the Binary Strings
5.3.2 The Diagonalization Language
5.3.3 L_d is not Recursively Enumerable
5.4 An Undecidable Problem that is RE
5.4.1 Recursive Languages
5.4.2 Complement of Recursive and RE languages
5.4.3 The Universal Language
5.5 Post’s Correspondence Problems (PCP)
5.5.1 Modified PCP
5.6 Tractable and Intractable Problems
5.7 P and NP Problems
5.7.1 Problems Solvable in Polynomial Time (P)
5.7.2 Problems Solvable in Non-polynomial Time (NP)
5.8 Polynomial Time Reductions
Review Questions
About The Authors
Dr. B. Paramasivan is Professor and Head, Department of Computer Science and Engineering at National Engineering College, Kovilpatti, Tamil Nadu. He has published 37 papers in international and national conferences.
Dr. K. Mohaideen Pitchai is Associate Professor, Department of Computer Science and Engineering at National Engineering College, Kovilpatti, Tamil Nadu. He has published his works in 8 international/national journals and 8 international conferences and 3 national conferences.
Mr. S. Dheenathayalan is Assistant Professor, Department of Computer Science and Engineering at National Engineering College, Kovilpatti, Tamil Nadu.
New Product Tab
Here's your new product tab.
Reviews
There are no reviews yet.