http://engineeringbooks.net
,THEORY OF COMPUTER SCIENCE
Automata, Languages and Computation
THIRD EDITION
K.l.P. MISHRA
Formerly Professor
Department of Electrical and Electronics Engineering
and Principal/ Regional Engineering College
Tiruchirapal/i
N. CHANDRASEKARAN
Professor
Department of Mathematics
St. Joseph/s College
Tiruchirapalli
Prentice'Hall of India [P[?lmGJD@ LsOWJov8d]
New Delhi - 110 '001
2008
http://engineeringbooks.net
, Contents
Preface ix
Notations Xl
1. PROPOSITIONS AND PREDICATES 1-35
1.1 Propositions (or Statements) 1
1.1.1 Connectives (Propositional Connectives
or Logical Connectives) 2
1.1.2 Well-formed Formulas 6
1.1.3 Truth Table for a Well-formed Formula 7
1.1.4 Equivalence of Well-formed Formulas 9
1.1.5 Logical Identities 9
1.2 Normal Forms of Well-formed Formulas 11
1.2.1 Construction to Obtain a Disjunctive Normal
Form of a Given Formula II
1.2.2 Construction to Obtain the Principal
Disjunctive Normal Form of a Given Formula 12
1.3 Rules of Inference for Propositional Calculus
(Statement Calculus) 15
1.4 Predicate Calculus 19
1.4.1 Predicates 19
1.4.2 Well-formed Formulas of Predicate Calculus 21
1.5 Rules of Inference for Predicate Calculus 23
1.6 Supplementary Examples 26
Se(f-Test 31
Exercises 32
iii
http://engineeringbooks.net
, iv J;J Contents
2. MATHEMATICAL PRELIMINARIES 36-70
2.1 Sets, Relations and Functions 36
2.1.1 Sets and Subsets 36
2.1.2 Sets with One Binary Operation 37
2.1.3 Sets with Two Binary Operations 39
2.1.4 Relations 40
2.1.5 Closure of Relations 43
2.1.6 Functions 45
2.2 Graphs and Trees 47
2.2.1 Graphs 47
2.2.2 Trees 49
2.3 Strings and Their Properties 54
2.3.1 Operations on Strings 54
2.3.2 Terminal and Nonterrninal Symbols 56
2.4 Principle of Induction 57
2.4.1 Method of Proof by Induction 57
2.4.2 Modified Method of Induction 58
2.4.3 Simultaneous Induction 60
2.5 Proof by Contradiction 61
2.6 Supplementary Examples 62
Self-Test 66
Exercises 67
3. THE THEORY OF AUTOMATA 71-106
3.1 Definition of an Automaton 7]
3.2 Description of a Finite Automaton 73
3.3 Transition Systems 74
3.4 Propeliies of Transition Functions 75
3.5 Acceptability of a String by a Finite Automaton 77
3.6 Nondeterministic Finite State Machines 78
3.7 The Equivalence of DFA and NDFA 80
3.8 Mealy and Moore Models 84
3.8.1 Finite Automata with Outputs 84
3.8.2 Procedure for Transforming a Mealy Machine
into a Moore Machine 85
3.8.3 Procedure for Transforming a Moore Machine
into a Mealy Machine 87
3.9 Minimization of Finite Automata 91
3.9.1 Construction of Minimum Automaton 92
3.10 Supplementary Examples 97
Self-Test 103
Exercises ] 04
http://engineeringbooks.net
,THEORY OF COMPUTER SCIENCE
Automata, Languages and Computation
THIRD EDITION
K.l.P. MISHRA
Formerly Professor
Department of Electrical and Electronics Engineering
and Principal/ Regional Engineering College
Tiruchirapal/i
N. CHANDRASEKARAN
Professor
Department of Mathematics
St. Joseph/s College
Tiruchirapalli
Prentice'Hall of India [P[?lmGJD@ LsOWJov8d]
New Delhi - 110 '001
2008
http://engineeringbooks.net
, Contents
Preface ix
Notations Xl
1. PROPOSITIONS AND PREDICATES 1-35
1.1 Propositions (or Statements) 1
1.1.1 Connectives (Propositional Connectives
or Logical Connectives) 2
1.1.2 Well-formed Formulas 6
1.1.3 Truth Table for a Well-formed Formula 7
1.1.4 Equivalence of Well-formed Formulas 9
1.1.5 Logical Identities 9
1.2 Normal Forms of Well-formed Formulas 11
1.2.1 Construction to Obtain a Disjunctive Normal
Form of a Given Formula II
1.2.2 Construction to Obtain the Principal
Disjunctive Normal Form of a Given Formula 12
1.3 Rules of Inference for Propositional Calculus
(Statement Calculus) 15
1.4 Predicate Calculus 19
1.4.1 Predicates 19
1.4.2 Well-formed Formulas of Predicate Calculus 21
1.5 Rules of Inference for Predicate Calculus 23
1.6 Supplementary Examples 26
Se(f-Test 31
Exercises 32
iii
http://engineeringbooks.net
, iv J;J Contents
2. MATHEMATICAL PRELIMINARIES 36-70
2.1 Sets, Relations and Functions 36
2.1.1 Sets and Subsets 36
2.1.2 Sets with One Binary Operation 37
2.1.3 Sets with Two Binary Operations 39
2.1.4 Relations 40
2.1.5 Closure of Relations 43
2.1.6 Functions 45
2.2 Graphs and Trees 47
2.2.1 Graphs 47
2.2.2 Trees 49
2.3 Strings and Their Properties 54
2.3.1 Operations on Strings 54
2.3.2 Terminal and Nonterrninal Symbols 56
2.4 Principle of Induction 57
2.4.1 Method of Proof by Induction 57
2.4.2 Modified Method of Induction 58
2.4.3 Simultaneous Induction 60
2.5 Proof by Contradiction 61
2.6 Supplementary Examples 62
Self-Test 66
Exercises 67
3. THE THEORY OF AUTOMATA 71-106
3.1 Definition of an Automaton 7]
3.2 Description of a Finite Automaton 73
3.3 Transition Systems 74
3.4 Propeliies of Transition Functions 75
3.5 Acceptability of a String by a Finite Automaton 77
3.6 Nondeterministic Finite State Machines 78
3.7 The Equivalence of DFA and NDFA 80
3.8 Mealy and Moore Models 84
3.8.1 Finite Automata with Outputs 84
3.8.2 Procedure for Transforming a Mealy Machine
into a Moore Machine 85
3.8.3 Procedure for Transforming a Moore Machine
into a Mealy Machine 87
3.9 Minimization of Finite Automata 91
3.9.1 Construction of Minimum Automaton 92
3.10 Supplementary Examples 97
Self-Test 103
Exercises ] 04
http://engineeringbooks.net
