Theory of Computer Science
Publisher: Prentice-Hall of India Pvt.Ltd
Published: August 30, 2004
Format: Paperback
Number of pages: 316
ISBN-13: 9788120312715
Subjects: General Theory of Computing
Table of contents: title: Preface
pagenum: V; title: Preface to the First Edition
pagenum: vii; title: Notations
pagenum: ix; label: 1
title: Mathematical Preliminaries
pagenum: 1; label: 1.1
title: Sets, Relations and Functions
pagenum: 1; label: 1.2
title: Graphs and Trees
pagenum: 10; label: 1.3
title: Strings and Their Properties
pagenum: 18; label: 1.4
title: Principle of Induction
pagenum: 20; title: Exercises
pagenum: 23; label: 2
title: The Theory of Automata
pagenum: 26; label: 2.1
title: Definition of an Automaton
pagenum: 26; label: 2.2
title: Description of a Finite Automaton
pagenum: 28; label: 2.3
title: Transition Systems
pagenum: 29; label: 2.4
title: Properties of Transition Functions
pagenum: 30; label: 2.5
title: Acceptability of a String by a Finite Automaton
pagenum: 31; label: 2.6
title: Nondeterministic Finite State Machines
pagenum: 32; label: 2.7
title: The Equivalence of DFA and NDFA
pagenum: 34; label: 2.8
title: Mealy and Moore Models
pagenum: 38; label: 2.9
title: Minimisation of Finite Automata
pagenum: 44; title: Exercises
pagenum: 50; label: 3
title: Formal Languages
pagenum: 53; label: 3.1
title: Basic Definitions and Examples
pagenum: 53; label: 3.2
title: Chomsky Classification of Languages
pagenum: 64; label: 3.3
title: Languages and Their Relation
pagenum: 66; label: 3.4
title: Recursive and Recursively Enumerable Sets
pagenum: 67; label: 3.5
title: Operations on Languages
pagenum: 70; label: 3.6
title: Languages and Automata
pagenum: 72; title: Exercises
pagenum: 72; label: 4
title: Regular Sets and Regular Grammars
pagenum: 75; label: 4.1
title: Regular Expressions
pagenum: 75; label: 4.2
title: Finite Automata and Regular Expressions
pagenum: 79; label: 4.3
title: Pumping Lemma for Regular Sets
pagenum: 100; label: 4.4
title: Application of Pumping Lemma
pagenum: 101; label: 4.5
title: Closure Properties of Regular Sets
pagenum: 103; label: 4.6
title: Regular Sets and Regular Grammars
pagenum: 105; title: Exercises
pagenum: 108; label: 5
title: Context-free Languages
pagenum: 111; label: 5.1
title: Context-free Languages and Derivation Trees
pagenum: 111; label: 5.2
title: Ambiguity in Context-free Grammars
pagenum: 118; label: 5.3
title: Simplification of Context-free Grammars
pagenum: 120; label: 5.4
title: Normal Forms for Context-free Grammars
pagenum: 131; label: 5.5
title: Pumping Lemma for Context-free Languages
pagenum: 142; label: 5.6
title: Decision Algorithms for Context-free Languages
pagenum: 146; title: Exercises
pagenum: 147; label: 6
title: Pushdown Automata
pagenum: 150; label: 6.1
title: Basic Definitions
pagenum: 150; label: 6.2
title: Acceptance by PDA
pagenum: 156; label: 6.3
title: Pushdown Automata and Context-free Languages
pagenum: 163; label: 6.4
title: Parsing and Pushdown Automata
pagenum: 174; title: Exercises
pagenum: 183; label: 7
title: Turing Machines and Linear Bounded Automata
pagenum: 185; label: 7.1
title: Turing Machine Model
pagenum: 185; label: 7.2
title: Representation of Turing Machines
pagenum: 186; label: 7.3
title: Language Acceptability by Turing Machines
pagenum: 190; label: 7.4
title: Design of Turing Machines
pagenum: 191; label: 7.5
title: Universal Turing Machines and Other Modifications
pagenum: 194; label: 7.6
title: The Model of Linear Bounded Automaton
pagenum: 195; label: 7.7
title: Turing Machines and Type 0 Grammars
pagenum: 197; label: 7.8
title: Linear Bounded Automata and Languages
pagenum: 199; label: 7.9
title: Halting Problem of Turing Machines
pagenum: 201; label: 7.10
title: NP-Completeness
pagenum: 205; title: Exercises
pagenum: 208; label: 8
title: LR(k) Grammars
pagenum: 210; label: 8.1
title: LR(k) Grammars
pagenum: 210; label: 8.2
title: Properties of LR(k) Grammars
pagenum: 213; label: 8.3
title: Closure Properties of Languages
pagenum: 214; title: Exercises
pagenum: 215; label: 9
title: Computability
pagenum: 217; label: 9.1
title: Introduction and Basic Concepts
pagenum: 217; label: 9.2
title: Primitive Recursive Functions
pagenum: 217; label: 9.3
title: Recursive Functions
pagenum: 224; label: 9.4
title: Partial Recursive Functions and Turing Machines
pagenum: 226; title: Exercises
pagenum: 234; label: 10
title: Propositions and Predicates
pagenum: 236; label: 10.1
title: Propositions (Or Statements)
pagenum: 236; label: 10.2
title: Normal Forms of Well-formed Formulas
pagenum: 244; label: 10.3
title: Rules of Inference for Propositional Calculus (Statement Calculus)
pagenum: 248; label: 10.4
title: Predicate Calculus
pagenum: 252; label: 10.5
title: Rules of Inference for Predicate Calculus
pagenum: 255; title: Exercises
pagenum: 257; title: Solutions (or Hints) to Selected Exercises
pagenum: 260; title: Further Reading
pagenum: 299; title: Index
pagenum: 301