Introduction to the Theory of Finite Automata (eBook)

Front Cover 1
Introduction to the Theory of Finite Automata, Volume 38 4
Copyright Page 5
CONTENTS 10
Introduction 12
Chapter I. THE ELEMENTS OF LOGIC 23
1. General remarks 23
2. The elements of the algebra of logic 27
3. The minimisation of formulae in the algebra of logic 42
4. The expansion of functions in the algebra of logic 53
5. Elements of the logic of predicates 60
Chapter II. OPERATORS. LOGICAL NETS 75
1. General remarks 75
2. The determinacy of operators 79
3. Bounded-determinate operators (operators with finite weight) 85
4. Elements (elementary automata) and circuits 93
5. Logical nets 101
6. The realisability of bounded-determinate operators. Problems in the analysis and synthesis of automata 109
Chapter III. OPERATORS OF PHYSICAL ELEMENTS 115
1. Introductory remarks 115
2. Valve and transistorised elements 116
3. Flip-flops 137
4. Ferromagnetic elements 149
Chapter IV. ANALYSIS OF AUTOMATA 168
1. General remarks 168
2. Attainability 171
3. Distinguishability 175
4. Periodicity 180
5. Analysis of an automaton circuit 185
Chapter V. METHODS OF SPECIFYING OPERATORS 192
1. General remarks 192
2. Fragments of trees 197
3. Transition matrices 209
4. Some further study of the language of propositional logic 214
5. The language of the logic of predicates 222
6. The expressive power of a logical language 239
Chapter VI. PRACTICAL METHODS OF SYNTHESIZING AUTOMATA 244
1. General remarks 244
2. Synthesis of a single-output logical net 246
3. Synthesis of a multi-output logical net 275
4. Synthesis of a “rat in the maze” logical net 289
Chapter VII. ASYMPTOTIC ESTIMATION FOR THE COMPLEXITY OF LOGICAL NETS 299
1. Fundamental concepts. Formulation of the limiting theorem 299
2. Synthesis of a net to realise a function in the algebra of logic upper bounds for the complexity of a net
3. Operators which admit a simple realisation 316
4. Choice of a code 328
5. Synthesis of nets having a memory 334
Appendix 339
References 342
Subject Index 346