Home / Browse / Theory of Computation
Theory of Computation
Theory of Computation
ISBN 9789393665829
 Publication Date

PAPERBACK

EBOOK (EPUB)

EBOOK (PDF)

Description

Table of contents

Biographical note

User Reviews

This book offers a thorough introduction to the concepts of Theory of Computation and is designed as per the latest Anna University Syllabus Regulations 2017. This book is also meant for students of various other related disciplines for both UG and PG courses.

  • Cover
  • Title Page
  • Copyright Page
  • Dedication
  • Book Organization
  • Contents
  • UNIT I Finite Automata
  • CHAPTER 1 Finite State Systems
    • 1.1 Introduction
    • 1.2 Basic Mathematical Notation and Techniques
      • 1.2.1 Deductive Proof
      • 1.2.2 Reduction to Definitions
    • 1.3 Other Theorem Forms
      • 1.3.1 If - Then Forms
      • 1.3.2 If - And Only - If Statements
      • 1.3.3 Theorem Not to be If -Then Statements
    • 1.4 Additional Forms of Proof
      • 1.4.1 Proving Equivalence about Sets
      • 1.4.2 Proofs by Contrapositive
      • 1.4.3 Proofs by Contradiction
      • 1.4.4 Proof by Counter Examples
    • 1.5 Inductive Proof
      • 1.5.1 Inductive on Integers
      • 1.5.2 Structural Inductions
      • 1.5.3 Mutual Inductions
    • 1.6 Basic Concepts of Automata Theory
      • 1.6.1 Alphabets
      • 1.6.2 String
      • 1.6.3 Operations on Strings
      • 1.6.4 Properties of Strings
      • 1.6.5 Languages
      • 1.6.6 Sets
      • 1.6.7 Relations
      • 1.6.8 Function
    • 1.7 Finite State Systems - Finite Automata
      • 1.7.1 Need for Automata Theory
      • 1.7.2 Limitation of Finite Automata
      • 1.7.3 Basic Definition - Finite Automaton
    • 1.8 Deterministic Finite Automata - DFA
      • 1.8.1 Transition Diagram - DFA
      • 1.8.2 Transition Table - DFA
      • 1.8.3 Transition Function ‘ δ ’ - DFA
      • 1.8.4 Extended Transition Function ‘ δ ’– DFA
      • 1.8.5 Languages of DFA
      • 1.8.6 Problems of DFA
    • 1.9 Non-Deterministic Finite Automata (NDFA OR NFA)
      • 1.9.1 Transition Diagram – NFA
      • 1.9.2 Transition Table – NFA
      • 1.9.3 Transition Function ‘ δ ’ – NFA
      • 1.9.4 Extended Transition Function ‘ δ ’ – NFA
      • 1.9.5 Languages of NFA
      • 1.9.6 Problems of NFA
    • 1.10 Finite Automaton with ∈ Moves (Nfa – ∈)
      • 1.10.1 Definition of NFA with ∈ Transition
      • 1.10.2 ∈ – Closure: Definition
      • 1.10.3 Transition Diagram – NFA ∈
      • 1.10.4 Transition Table – NFA ∈
      • 1.10.5 Transition Function – NFA ∈
      • 1.10.6 Languages of NFA ∈
      • 1.10.7 Problems on NFA with ∈
    • 1.11 Equivalence of NFA and DFA
    • 1.12 Equivalence of NDFA’ s with and without ∈ – Moves
    • 1.13 Problems for Conversion of NFA to DFA
    • 1.14 Problems for Conversion of NFA with ∈ to NFA without ∈
    • 1.15 Problems for Conversion of NFA with ∈ to DFA Directly
  • Chapter 2 Regular Languages and Expressions
    • 2.1 Regular Expression
      • 2.1.1 Definition of Regular Expression
      • 2.1.2 Operators of Regular Expression
      • 2.1.3 Algebraic Properties of Regular Expression
      • 2.1.4 Regular Language
      • 2.1.5 Precedence of Regular Expression Operators
      • 2.1.6 Problems on Regular Expression
    • 2.2 Equivalence of Finite Automaton and Regular Expression
    • 2.3 Conversion of Regular Expression to Finite Automata
      • 2.3.1 Problems of Regular Expression to Finite Automata
    • 2.4 Conversion of Finite Automata to Regular Expression
      • 2.4.1 Formula Method for FA to Regular Expression – R ij ( k )
      • 2.4.2 State Elimination Method for Conversion of FA to RE
      • 2.4.3 Formula for Conversion of Finite Automata to Regular Expression
      • 2.4.4 Minimization Rules for Regular Expression
      • 2.4.5 Identities for Regular Expression
    • 2.5 Problem for Converting FA to RE using Formula Method
    • 2.6 Problem for Converting FA to RE using State Elimination Technique
    • 2.7 Equivalence and Minimization of Regular Expression and Automata
      • 2.7.1 Testing the Equivalences of States Myhill Nerode Theorem
      • 2.7.2 Equivalent States
      • 2.7.3 Distinguishable States
      • 2.7.4 Table Filling Algorithm
      • 2.7.5 Testing Equivalence of Regular Languages
    • 2.8 Minimization of DFA
      • 2.8.1 Property of Equivalent States
      • 2.8.2 Algorithm for Minimizing a DFA
    • 2.9 Problems on Minimization of DFA
    • 2.10 Problems on Equivalence of Regular Languages
    • 2.11 Pumping Lemma for Regular Sets
      • 2.11.1 Pumping Lemma
      • 2.11.2 Theorem for Pumping Lemma for Regular Languages
      • 2.11.3 Applications of Pumping Lemma
    • 2.12 Problems based on Pumping Lemma
  • Unit II Grammars
  • Chapter 3 Context Free Grammar
    • 3.1 Grammar Introduction
    • 3.2 Types of Grammar
      • 3.2.1 Type 0 Grammar
      • 3.2.2 Type 1 Grammar
      • 3.2.3 Type 2 Grammar
      • 3.2.4 Type 3 Grammar
    • 3.3 Context Free Grammars and Languages
      • 3.3.1 CFG Language
      • 3.3.2 Context Free Grammar for Palindrome
      • 3.3.3 Generating CFG
    • 3.4 Derivations and Languages
      • 3.4.1 Recursive Inference
      • 3.4.2 Derivation
      • 3.4.3 Left Most Derivations
      • 3.4.4 Right Most Derivations
      • 3.4.5 Derivation Problems
      • 3.4.6 Recursive Inference Problems
      • 3.4.7 Sentential Forms
      • 3.4.8 Past Trees or Derivation Trees
      • 3.4.9 Derivtion Tree Construction
      • 3.4.10 Derivation Tree Problems
    • 3.5 Ambiguity in Grammars and Languages
      • 3.5.1 Ambiguity Problems
      • 3.5.2 Removing Ambiguity from Grammar
      • 3.5.3 Removing Ambiguity Problems
      • 3.5.4 Properties of Unambiguous Grammar
      • 3.5.5 Inherent Ambiguous Grammar
      • 3.5.6 Unambiguous Grammar Problems
      • 3.5.7 Applications of CFG
      • 3.5.8 Yield of the Parse Tree
    • 3.6 Relationship between Derivation and Derivation Tree
      • 3.6.1 Recursive Inference to Parse Trees
      • 3.6.2 From Parse Tree to Derivation
      • 3.6.3 From Derivations to Recursive Inference
    • 3.7 Solved Problems of Context Free Grammar
  • Chapter 4 Simplication of Context Free Grammar
    • 4.1 Normal Forms of CFG
      • 4.1.1 Normal Forms of CFG
    • 4.2 Simplication for Chomsky Normal Form
    • 4.3 Elimination of Useless Symbols
      • 4.3.1 Example for Eliminating the Useless Symbols
      • 4.3.2 Theorem for Useless Symbols
      • 4.3.3 Finding the Generating Symbols
      • 4.3.4 Finding Reachable Symbols
    • 4.4 Elimination of Null ∈ Productions
      • 4.4.1 Nullable Symbol
      • 4.4.2 Finding Nullable Symbols
      • 4.4.3 Example for Eliminating ∈ – Production
      • 4.4 .4 Theorem for Eliminating ∈ Production
    • 4.5 Elimination of Unit Productions
      • 4.5.1 Finding Unit Productions
      • 4.5.2 Theorem for Eliminating Unit Productions
      • 4.5.3 Example for Eliminating Unit Productions
    • 4.6 Chomsky Normal Form (CNF)
      • 4.6.1 Process of Converting Grammar into CNF
      • 4.6.2 Theorem for Chomsky Normal Form
      • 4.6.3 Problems Related to Chomsky Normal Form
    • 4.7 Greibach Normal Form (GNF)
      • 4.7.1 Process of Converting CFG to GNF
      • 4.7.2 Problems Related to Greibach Normal Form
  • UNIT III Pushdown Automata
  • Chapter 5 PDA and CFG
    • 5.1 Pushdown Automata
    • 5.2 Definition of Pushdown Automata
      • 5.2.1 Process of Pushdown Automata
      • 5.2.2 Transition Function of Pushdown Automata
      • 5.2.3 Graphical Representation of PDA
    • 5.3 Moves of PDA
      • 5.3.1 Move by Consuming an Input Symbol
      • 5.3.2 Move by Epsilon Transition
    • 5.4 Instantaneous Description of PDA
      • 5.4.1 Problems on Transition Diagram of PDA
    • 5.5 Languages of Pushdown Automata
      • 5.5.1 Acceptance by Final State
      • 5.5.2 Acceptance by Empty Stack
      • 5.5.3 Converting a Language Accepted by Empty Stack to Final State
      • 5.5.4 Converting a Language Accepted by Reaching a Final State to Empty Stack
    • 5.6 Construction of Pushdown Automata
    • 5.7 Deterministic Pushdown Automata
      • 5.7.1 Languages of Deterministic Pushdown Automata
      • 5.7.2 Context Free Languages and DPDA
      • 5.7.3 Problems of Deterministic Pushdown Automata
  • Chapter 6 Pumping Lemma for Context Free Language
    • 6.1 Equivalence of PDA and CFG
      • 6.1.1 Converting Context Free Grammar to PDA
      • 6.1.2 Rules for Converting CFG to PDA
      • 6.1.3 Converting Pushdown Automata to CFG
    • 6.2 Problems for Converting CFG to PDA
    • 6.3 Problems for Converting PDA to CFG
    • 6.4 Pumping Lemma for Context Free Language (CFL)
      • 6.4.1 Application of Pumping Lemma for CFL
      • 6.4.2 Theorem for Pumping Lemma of CFL
      • 6.4.3 Steps for Pumping Lemma for CFL
    • 6.5 Problems based on Pumping Lemma for CFL
  • UniT IV Turing Machines
  • Chapter 7 Construction of Turing Machine
    • 7.1 Definition of Turing Machine
    • 7.2 Model of Turing Machine
      • 7.2.1 Working of Turing Machine
      • 7.2.2 Formal Definition of a Turing Machine
      • 7.2.3 Transition Function Turing Machine
      • 7.2.4 Processing of Move in a Turing Machine
      • 7.2.5 Instantaneous Description of a Turing Machine
      • 7.2.6 Language of a Turing Machine
      • 7.2.7 Halting of Turing Machine
      • 7.2.8 Transition Diagram of a Turing Machine
      • 7.2.9 Example for Turing Machine Transition Diagram
    • 7.3 Computable Languages and Functions
    • 7.4 Problems about Turing Machines for Computable Languages
    • 7.5 Techniques for Turing Machine Construction
    • 7.6 Storage in Finite Control
      • 7.6.1 Problems for Storage in Finite Control
    • 7.7 Multiple Tracks or Multi Head Turing Machines
      • 7.7.1 Example for Designing Turing Machine with Multiple Tracks
    • 7.8 Multi Tape Turing Machines
    • 7.9 Checking Off Symbols
      • 7.9.1 Problems for Checking Off Symbols
    • 7.10 Subroutines
      • 7.10.1 Problems on Subroutine
    • 7.11 Non-deterministic Turing Machines
  • CHAPTER 8 Problems about Turing Machine
    • 8.1 Halting Problem
    • 8.2 Partial Solvency
      • 8.2.1 Problems on Partial Solvents
    • 8.3 Problems about Turing Machines
      • 8.3.1 Decidable Problems
      • 8.3.2 Undecidable Languages
      • 8.3.3 Enumerating the Binary Strings
      • 8.3.4 Codes for Turing Machines
      • 8.3.5 Undecidable Problems about Turing Machines
      • 8.3.6 Unsolvable Problems of Turing Machine
      • 8.3.7 Unsolvable Decision Problems of Turing Machine
    • 8.4 Chomskian Hierarchy of Languages
      • 8.4.1 Recursive or Unrestricted Language
      • 8.4.2 Context Sensitive Language
      • 8.4.3 Context Free Language
      • 8.4.4 Regular Language
      • 8.4.5 Linear Bounded Automata
  • UNIT V Unsolvable Problems and Computable Functions
  • CHAPTER 9 Recursive Functions
    • 9.1 Unsolvable Problems and Computable Functions
      • 9.1.1 Unsolvable Problem of a Non-recursive Language
      • 9.1.2 Unsolvable Problem of Reduction
      • 9.1.3 Unsolvable Problem in Rice’s Theorem
      • 9.1.4 Post Correspondence Problem
      • 9.1.5 Unsolvable Problems of Context Free Grammars
    • 9.2 Computable Functions
    • 9.3 Primitive Recursive Functions
      • 9.3.1 Primitive Recursive Operation
      • 9.3.2 Definition – Primitive Recursive Function
      • 9.3.3 Initial Functions
      • 9.3.4 Composition Function
      • 9.3.5 Primitive Recursive Derivation
      • 9.3.6 Addition and Multiplication Function
      • 9.3.7 Statement of Primitive Recursive Function
      • 9.3.8 Predecessor Function - Primitive Recursive Function
      • 9.3.9 Proper Subtraction - Primitive Recursive Function
      • 9.3.10 Theorem for Primitive Recursive Function
    • 9.4 Recursive and Recursively Enumerable Languages
      • 9.4.1 Recursive Language
      • 9.4.2 Recursively Enumerable (RE) Language
      • 9.4.3 Relationship between Recursive, RE and Non-RE Languages
      • 9.4.4 Languages that is Not Recursively Enumerable
      • 9.4.5 Diagonalization Language
      • 9.4.6 Diagonalization
      • 9.4.7 Diagonalization Language ‘LD’ is Not Recursively Enumerable
      • 9.4.8 Undecidable Problem that is Recursively Enumerable (RE)
      • 9.4.9 Properties of Recursive and Recursively Enumerable Languages
      • 9.4.10 Enumerating a Language
      • 9.4.11 Countable and Uncountable Sets
    • 9.5 Universal Turing Machine
      • 9.5.1 Operation of Universal Turing Machine
      • 9.5.2 Undecidability of the Universal Language
  • Chapter 10 Measuring and Classifying Complexity
    • 10.1 Measuring and Classifying Complexity
      • 10.1.1 Growth Rates of Polynomial and Exponential Functions
      • 10.1.2 Comparing Growth Rate
      • 10.1.3 Facts of Functions
    • 10.2 Time and Space Complexity of a Turing Machine
      • 10.2.1 Time Complexity
      • 10.2.2 Space Complexity
      • 10.2.3 Time and Space Complexity of Non-deterministic Turing Machine
      • 10.2.4 Time Complexity of Non-deterministic Turing Machine
      • 10.2.5 Space Complexity of Non-deterministic Turing Machine
    • 10.3 Complexity Classes
      • 10.3.1 Step Counting Function
      • 10.3.2 Corollary of Step Counting Function
    • 10.4 Tractable and Intractable Problems
      • 10.4.1 Tractable and Possibly Intractable Problems
      • 10.4.2 CNF Satisfiability Problem
      • 10.4.3 Primality Problem
    • 10.5 P and NP Completeness
      • 10.5.1 The Classes P and NP
      • 10.5.2 Problems Solvable in Polynomial Time
      • 10.5.3 Class P Problem - Krushal’s Algorithm
      • 10.5.4 Implementation of Krushal’s Algorithm using Turing Machine
      • 10.5.5 Example Problem for MSWT using Krushal’s Algorithm
      • 10.5.6 Construction of Turing Machine for Krushal’s Algorithm
      • 10.5.7 CLASS NP Problem - Non-deterministic Polynomial Tree
      • 10.5.8 CLASS NP Problem - Traveling Salesman Problem
    • 10.6 Polynomial Time Reductions
      • 10.6.1 Definition - Polynomial Time Reductions
      • 10.6.2 Reductions
      • 10.6.3 Properties of Polynomial Time Reduction10.6.4 CNF - SAT Reducible with CNF - SAT Problem
      • 10.6.5 Cook’s Theorem
    • 10.7 NP - Completeness
  • Anna University Question Papers
    • CS2303 Theory of Computation November / December 2014
    • CS2303 Theory of Computation May / June 2014
    • CS2303 Theory of Computation November / December 2013
    • CS2303 Theory of Computation May / June 2013
    • CS2303 Theory of Computation November / December 2012
    • CS2303 Theory of Computation May / June 2012
    • CS2303 Theory of Computation November / December 2011
    • CS2303 Theory of Computation May / June 2011
    • CS2303 Theory of Computation November / December 2014
    • CS2303 Theory of Computation November / December 2013

Dr. M. Shyamala Devi has more than 13 years of teaching experience and her research interests include theoretical computer science, distributed system and cloud computing. A prolific author, she has written engineering books on subjects namely Theory of Computation, Principles of Compiler Design, Data Structures and Algorithm Analysis, Graphics and Multimedia, Fundamentals of Computer Programming, Digital Computer Fundamentals and Visual Programming, Compiler Design, Cryptography and Network Security, Grid and Cloud Computing. She has presented and published numerous research articles in reputed International journals. She is an Active Life member of CSI, ISTE, ICST, IAEST, IAENG, SAISE and IACSIT. She has been invited as a Chief Guest for the Seminars, Resource Person for FDP and Guest Lectures in various Engineering colleges in Tamil Nadu.

Comments should not be blank
Rating
r
radha
Reviewed on
is this good for beginners
Description

This book offers a thorough introduction to the concepts of Theory of Computation and is designed as per the latest Anna University Syllabus Regulations 2017. This book is also meant for students of various other related disciplines for both UG and PG courses.

Table of contents
  • Cover
  • Title Page
  • Copyright Page
  • Dedication
  • Book Organization
  • Contents
  • UNIT I Finite Automata
  • CHAPTER 1 Finite State Systems
    • 1.1 Introduction
    • 1.2 Basic Mathematical Notation and Techniques
      • 1.2.1 Deductive Proof
      • 1.2.2 Reduction to Definitions
    • 1.3 Other Theorem Forms
      • 1.3.1 If - Then Forms
      • 1.3.2 If - And Only - If Statements
      • 1.3.3 Theorem Not to be If -Then Statements
    • 1.4 Additional Forms of Proof
      • 1.4.1 Proving Equivalence about Sets
      • 1.4.2 Proofs by Contrapositive
      • 1.4.3 Proofs by Contradiction
      • 1.4.4 Proof by Counter Examples
    • 1.5 Inductive Proof
      • 1.5.1 Inductive on Integers
      • 1.5.2 Structural Inductions
      • 1.5.3 Mutual Inductions
    • 1.6 Basic Concepts of Automata Theory
      • 1.6.1 Alphabets
      • 1.6.2 String
      • 1.6.3 Operations on Strings
      • 1.6.4 Properties of Strings
      • 1.6.5 Languages
      • 1.6.6 Sets
      • 1.6.7 Relations
      • 1.6.8 Function
    • 1.7 Finite State Systems - Finite Automata
      • 1.7.1 Need for Automata Theory
      • 1.7.2 Limitation of Finite Automata
      • 1.7.3 Basic Definition - Finite Automaton
    • 1.8 Deterministic Finite Automata - DFA
      • 1.8.1 Transition Diagram - DFA
      • 1.8.2 Transition Table - DFA
      • 1.8.3 Transition Function ‘ δ ’ - DFA
      • 1.8.4 Extended Transition Function ‘ δ ’– DFA
      • 1.8.5 Languages of DFA
      • 1.8.6 Problems of DFA
    • 1.9 Non-Deterministic Finite Automata (NDFA OR NFA)
      • 1.9.1 Transition Diagram – NFA
      • 1.9.2 Transition Table – NFA
      • 1.9.3 Transition Function ‘ δ ’ – NFA
      • 1.9.4 Extended Transition Function ‘ δ ’ – NFA
      • 1.9.5 Languages of NFA
      • 1.9.6 Problems of NFA
    • 1.10 Finite Automaton with ∈ Moves (Nfa – ∈)
      • 1.10.1 Definition of NFA with ∈ Transition
      • 1.10.2 ∈ – Closure: Definition
      • 1.10.3 Transition Diagram – NFA ∈
      • 1.10.4 Transition Table – NFA ∈
      • 1.10.5 Transition Function – NFA ∈
      • 1.10.6 Languages of NFA ∈
      • 1.10.7 Problems on NFA with ∈
    • 1.11 Equivalence of NFA and DFA
    • 1.12 Equivalence of NDFA’ s with and without ∈ – Moves
    • 1.13 Problems for Conversion of NFA to DFA
    • 1.14 Problems for Conversion of NFA with ∈ to NFA without ∈
    • 1.15 Problems for Conversion of NFA with ∈ to DFA Directly
  • Chapter 2 Regular Languages and Expressions
    • 2.1 Regular Expression
      • 2.1.1 Definition of Regular Expression
      • 2.1.2 Operators of Regular Expression
      • 2.1.3 Algebraic Properties of Regular Expression
      • 2.1.4 Regular Language
      • 2.1.5 Precedence of Regular Expression Operators
      • 2.1.6 Problems on Regular Expression
    • 2.2 Equivalence of Finite Automaton and Regular Expression
    • 2.3 Conversion of Regular Expression to Finite Automata
      • 2.3.1 Problems of Regular Expression to Finite Automata
    • 2.4 Conversion of Finite Automata to Regular Expression
      • 2.4.1 Formula Method for FA to Regular Expression – R ij ( k )
      • 2.4.2 State Elimination Method for Conversion of FA to RE
      • 2.4.3 Formula for Conversion of Finite Automata to Regular Expression
      • 2.4.4 Minimization Rules for Regular Expression
      • 2.4.5 Identities for Regular Expression
    • 2.5 Problem for Converting FA to RE using Formula Method
    • 2.6 Problem for Converting FA to RE using State Elimination Technique
    • 2.7 Equivalence and Minimization of Regular Expression and Automata
      • 2.7.1 Testing the Equivalences of States Myhill Nerode Theorem
      • 2.7.2 Equivalent States
      • 2.7.3 Distinguishable States
      • 2.7.4 Table Filling Algorithm
      • 2.7.5 Testing Equivalence of Regular Languages
    • 2.8 Minimization of DFA
      • 2.8.1 Property of Equivalent States
      • 2.8.2 Algorithm for Minimizing a DFA
    • 2.9 Problems on Minimization of DFA
    • 2.10 Problems on Equivalence of Regular Languages
    • 2.11 Pumping Lemma for Regular Sets
      • 2.11.1 Pumping Lemma
      • 2.11.2 Theorem for Pumping Lemma for Regular Languages
      • 2.11.3 Applications of Pumping Lemma
    • 2.12 Problems based on Pumping Lemma
  • Unit II Grammars
  • Chapter 3 Context Free Grammar
    • 3.1 Grammar Introduction
    • 3.2 Types of Grammar
      • 3.2.1 Type 0 Grammar
      • 3.2.2 Type 1 Grammar
      • 3.2.3 Type 2 Grammar
      • 3.2.4 Type 3 Grammar
    • 3.3 Context Free Grammars and Languages
      • 3.3.1 CFG Language
      • 3.3.2 Context Free Grammar for Palindrome
      • 3.3.3 Generating CFG
    • 3.4 Derivations and Languages
      • 3.4.1 Recursive Inference
      • 3.4.2 Derivation
      • 3.4.3 Left Most Derivations
      • 3.4.4 Right Most Derivations
      • 3.4.5 Derivation Problems
      • 3.4.6 Recursive Inference Problems
      • 3.4.7 Sentential Forms
      • 3.4.8 Past Trees or Derivation Trees
      • 3.4.9 Derivtion Tree Construction
      • 3.4.10 Derivation Tree Problems
    • 3.5 Ambiguity in Grammars and Languages
      • 3.5.1 Ambiguity Problems
      • 3.5.2 Removing Ambiguity from Grammar
      • 3.5.3 Removing Ambiguity Problems
      • 3.5.4 Properties of Unambiguous Grammar
      • 3.5.5 Inherent Ambiguous Grammar
      • 3.5.6 Unambiguous Grammar Problems
      • 3.5.7 Applications of CFG
      • 3.5.8 Yield of the Parse Tree
    • 3.6 Relationship between Derivation and Derivation Tree
      • 3.6.1 Recursive Inference to Parse Trees
      • 3.6.2 From Parse Tree to Derivation
      • 3.6.3 From Derivations to Recursive Inference
    • 3.7 Solved Problems of Context Free Grammar
  • Chapter 4 Simplication of Context Free Grammar
    • 4.1 Normal Forms of CFG
      • 4.1.1 Normal Forms of CFG
    • 4.2 Simplication for Chomsky Normal Form
    • 4.3 Elimination of Useless Symbols
      • 4.3.1 Example for Eliminating the Useless Symbols
      • 4.3.2 Theorem for Useless Symbols
      • 4.3.3 Finding the Generating Symbols
      • 4.3.4 Finding Reachable Symbols
    • 4.4 Elimination of Null ∈ Productions
      • 4.4.1 Nullable Symbol
      • 4.4.2 Finding Nullable Symbols
      • 4.4.3 Example for Eliminating ∈ – Production
      • 4.4 .4 Theorem for Eliminating ∈ Production
    • 4.5 Elimination of Unit Productions
      • 4.5.1 Finding Unit Productions
      • 4.5.2 Theorem for Eliminating Unit Productions
      • 4.5.3 Example for Eliminating Unit Productions
    • 4.6 Chomsky Normal Form (CNF)
      • 4.6.1 Process of Converting Grammar into CNF
      • 4.6.2 Theorem for Chomsky Normal Form
      • 4.6.3 Problems Related to Chomsky Normal Form
    • 4.7 Greibach Normal Form (GNF)
      • 4.7.1 Process of Converting CFG to GNF
      • 4.7.2 Problems Related to Greibach Normal Form
  • UNIT III Pushdown Automata
  • Chapter 5 PDA and CFG
    • 5.1 Pushdown Automata
    • 5.2 Definition of Pushdown Automata
      • 5.2.1 Process of Pushdown Automata
      • 5.2.2 Transition Function of Pushdown Automata
      • 5.2.3 Graphical Representation of PDA
    • 5.3 Moves of PDA
      • 5.3.1 Move by Consuming an Input Symbol
      • 5.3.2 Move by Epsilon Transition
    • 5.4 Instantaneous Description of PDA
      • 5.4.1 Problems on Transition Diagram of PDA
    • 5.5 Languages of Pushdown Automata
      • 5.5.1 Acceptance by Final State
      • 5.5.2 Acceptance by Empty Stack
      • 5.5.3 Converting a Language Accepted by Empty Stack to Final State
      • 5.5.4 Converting a Language Accepted by Reaching a Final State to Empty Stack
    • 5.6 Construction of Pushdown Automata
    • 5.7 Deterministic Pushdown Automata
      • 5.7.1 Languages of Deterministic Pushdown Automata
      • 5.7.2 Context Free Languages and DPDA
      • 5.7.3 Problems of Deterministic Pushdown Automata
  • Chapter 6 Pumping Lemma for Context Free Language
    • 6.1 Equivalence of PDA and CFG
      • 6.1.1 Converting Context Free Grammar to PDA
      • 6.1.2 Rules for Converting CFG to PDA
      • 6.1.3 Converting Pushdown Automata to CFG
    • 6.2 Problems for Converting CFG to PDA
    • 6.3 Problems for Converting PDA to CFG
    • 6.4 Pumping Lemma for Context Free Language (CFL)
      • 6.4.1 Application of Pumping Lemma for CFL
      • 6.4.2 Theorem for Pumping Lemma of CFL
      • 6.4.3 Steps for Pumping Lemma for CFL
    • 6.5 Problems based on Pumping Lemma for CFL
  • UniT IV Turing Machines
  • Chapter 7 Construction of Turing Machine
    • 7.1 Definition of Turing Machine
    • 7.2 Model of Turing Machine
      • 7.2.1 Working of Turing Machine
      • 7.2.2 Formal Definition of a Turing Machine
      • 7.2.3 Transition Function Turing Machine
      • 7.2.4 Processing of Move in a Turing Machine
      • 7.2.5 Instantaneous Description of a Turing Machine
      • 7.2.6 Language of a Turing Machine
      • 7.2.7 Halting of Turing Machine
      • 7.2.8 Transition Diagram of a Turing Machine
      • 7.2.9 Example for Turing Machine Transition Diagram
    • 7.3 Computable Languages and Functions
    • 7.4 Problems about Turing Machines for Computable Languages
    • 7.5 Techniques for Turing Machine Construction
    • 7.6 Storage in Finite Control
      • 7.6.1 Problems for Storage in Finite Control
    • 7.7 Multiple Tracks or Multi Head Turing Machines
      • 7.7.1 Example for Designing Turing Machine with Multiple Tracks
    • 7.8 Multi Tape Turing Machines
    • 7.9 Checking Off Symbols
      • 7.9.1 Problems for Checking Off Symbols
    • 7.10 Subroutines
      • 7.10.1 Problems on Subroutine
    • 7.11 Non-deterministic Turing Machines
  • CHAPTER 8 Problems about Turing Machine
    • 8.1 Halting Problem
    • 8.2 Partial Solvency
      • 8.2.1 Problems on Partial Solvents
    • 8.3 Problems about Turing Machines
      • 8.3.1 Decidable Problems
      • 8.3.2 Undecidable Languages
      • 8.3.3 Enumerating the Binary Strings
      • 8.3.4 Codes for Turing Machines
      • 8.3.5 Undecidable Problems about Turing Machines
      • 8.3.6 Unsolvable Problems of Turing Machine
      • 8.3.7 Unsolvable Decision Problems of Turing Machine
    • 8.4 Chomskian Hierarchy of Languages
      • 8.4.1 Recursive or Unrestricted Language
      • 8.4.2 Context Sensitive Language
      • 8.4.3 Context Free Language
      • 8.4.4 Regular Language
      • 8.4.5 Linear Bounded Automata
  • UNIT V Unsolvable Problems and Computable Functions
  • CHAPTER 9 Recursive Functions
    • 9.1 Unsolvable Problems and Computable Functions
      • 9.1.1 Unsolvable Problem of a Non-recursive Language
      • 9.1.2 Unsolvable Problem of Reduction
      • 9.1.3 Unsolvable Problem in Rice’s Theorem
      • 9.1.4 Post Correspondence Problem
      • 9.1.5 Unsolvable Problems of Context Free Grammars
    • 9.2 Computable Functions
    • 9.3 Primitive Recursive Functions
      • 9.3.1 Primitive Recursive Operation
      • 9.3.2 Definition – Primitive Recursive Function
      • 9.3.3 Initial Functions
      • 9.3.4 Composition Function
      • 9.3.5 Primitive Recursive Derivation
      • 9.3.6 Addition and Multiplication Function
      • 9.3.7 Statement of Primitive Recursive Function
      • 9.3.8 Predecessor Function - Primitive Recursive Function
      • 9.3.9 Proper Subtraction - Primitive Recursive Function
      • 9.3.10 Theorem for Primitive Recursive Function
    • 9.4 Recursive and Recursively Enumerable Languages
      • 9.4.1 Recursive Language
      • 9.4.2 Recursively Enumerable (RE) Language
      • 9.4.3 Relationship between Recursive, RE and Non-RE Languages
      • 9.4.4 Languages that is Not Recursively Enumerable
      • 9.4.5 Diagonalization Language
      • 9.4.6 Diagonalization
      • 9.4.7 Diagonalization Language ‘LD’ is Not Recursively Enumerable
      • 9.4.8 Undecidable Problem that is Recursively Enumerable (RE)
      • 9.4.9 Properties of Recursive and Recursively Enumerable Languages
      • 9.4.10 Enumerating a Language
      • 9.4.11 Countable and Uncountable Sets
    • 9.5 Universal Turing Machine
      • 9.5.1 Operation of Universal Turing Machine
      • 9.5.2 Undecidability of the Universal Language
  • Chapter 10 Measuring and Classifying Complexity
    • 10.1 Measuring and Classifying Complexity
      • 10.1.1 Growth Rates of Polynomial and Exponential Functions
      • 10.1.2 Comparing Growth Rate
      • 10.1.3 Facts of Functions
    • 10.2 Time and Space Complexity of a Turing Machine
      • 10.2.1 Time Complexity
      • 10.2.2 Space Complexity
      • 10.2.3 Time and Space Complexity of Non-deterministic Turing Machine
      • 10.2.4 Time Complexity of Non-deterministic Turing Machine
      • 10.2.5 Space Complexity of Non-deterministic Turing Machine
    • 10.3 Complexity Classes
      • 10.3.1 Step Counting Function
      • 10.3.2 Corollary of Step Counting Function
    • 10.4 Tractable and Intractable Problems
      • 10.4.1 Tractable and Possibly Intractable Problems
      • 10.4.2 CNF Satisfiability Problem
      • 10.4.3 Primality Problem
    • 10.5 P and NP Completeness
      • 10.5.1 The Classes P and NP
      • 10.5.2 Problems Solvable in Polynomial Time
      • 10.5.3 Class P Problem - Krushal’s Algorithm
      • 10.5.4 Implementation of Krushal’s Algorithm using Turing Machine
      • 10.5.5 Example Problem for MSWT using Krushal’s Algorithm
      • 10.5.6 Construction of Turing Machine for Krushal’s Algorithm
      • 10.5.7 CLASS NP Problem - Non-deterministic Polynomial Tree
      • 10.5.8 CLASS NP Problem - Traveling Salesman Problem
    • 10.6 Polynomial Time Reductions
      • 10.6.1 Definition - Polynomial Time Reductions
      • 10.6.2 Reductions
      • 10.6.3 Properties of Polynomial Time Reduction10.6.4 CNF - SAT Reducible with CNF - SAT Problem
      • 10.6.5 Cook’s Theorem
    • 10.7 NP - Completeness
  • Anna University Question Papers
    • CS2303 Theory of Computation November / December 2014
    • CS2303 Theory of Computation May / June 2014
    • CS2303 Theory of Computation November / December 2013
    • CS2303 Theory of Computation May / June 2013
    • CS2303 Theory of Computation November / December 2012
    • CS2303 Theory of Computation May / June 2012
    • CS2303 Theory of Computation November / December 2011
    • CS2303 Theory of Computation May / June 2011
    • CS2303 Theory of Computation November / December 2014
    • CS2303 Theory of Computation November / December 2013
Biographical note

Dr. M. Shyamala Devi has more than 13 years of teaching experience and her research interests include theoretical computer science, distributed system and cloud computing. A prolific author, she has written engineering books on subjects namely Theory of Computation, Principles of Compiler Design, Data Structures and Algorithm Analysis, Graphics and Multimedia, Fundamentals of Computer Programming, Digital Computer Fundamentals and Visual Programming, Compiler Design, Cryptography and Network Security, Grid and Cloud Computing. She has presented and published numerous research articles in reputed International journals. She is an Active Life member of CSI, ISTE, ICST, IAEST, IAENG, SAISE and IACSIT. She has been invited as a Chief Guest for the Seminars, Resource Person for FDP and Guest Lectures in various Engineering colleges in Tamil Nadu.

User Reviews
Comments should not be blank
Rating
r
radha
Reviewed on
is this good for beginners