Theory of Computation
Subject(s): Computer Science
ISBN 9789393665829
 Published Date
  Pages 580





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.

Title Page
Copyright Page
Book Organization
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

Highlights Notes

  • You don’t have any highlights!!

  • You don’t have any Notes!!