iv J;J Contents
2. MATHEMATICAL PRELIMINARIES
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
36-70
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