Salomaa / Sneddon / Stark Theory of Automata

1. Auflage 2014
ISBN: 978-1-4831-5439-8
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 276 Seiten, Web PDF

Reihe: International Series in Pure and Applied Mathematics

Theory of Automata deals with mathematical aspects of the theory of automata theory, with emphasis on the finite deterministic automaton as the basic model. All other models, such as finite non-deterministic and probabilistic automata as well as pushdown and linear bounded automata, are treated as generalizations of this basic model. The formalism chosen to describe finite deterministic automata is that of regular expressions. A detailed exposition regarding this formalism is presented by considering the algebra of regular expressions. This volume is comprised of four chapters and begins with a discussion on finite deterministic automata, paying particular attention to regular and finite languages; analysis and synthesis theorems; equivalence relations induced by languages; sequential machines; sequential functions and relations; definite languages and non-initial automata; and two-way automata. The next chapter describes finite non-deterministic and probabilistic automata and covers theorems concerning stochastic languages; non-regular stochastic languages; and probabilistic sequential machines. The book then introduces the reader to the algebra of regular expressions before concluding with a chapter on formal languages and generalized automata. Theoretical exercises are included, along with ''problems'' at the end of some sections. This monograph will be a useful resource for beginning graduate or advanced undergraduates of mathematics.

Autoren/Hrsg.

Salomaa, Arto

Sneddon, I. N.

Stark, M.

Kahane, J. P.

Inhaltsverzeichnis

1;Front Cover;1
2;Theory of Automata;4
3;Copyright Page;5
4;Dedication;6
5;Table of Contents;8
6;Preface;10
7;Acknowledgements;12
8;Note to the Reader;13
9;CHAPTER I. FINITE DETERMINISTIC AUTOMATA;14
9.1;1. Regular languages;14
9.2;2. Analysis and synthesis theorems;19
9.3;3. Characteristic equations;30
9.4;4. Equivalence relations induced by languages;40
9.5;5. Sequential machines;44
9.6;6. Experiments and minimization;53
9.7;7. Sequential functions and relations;61
9.8;8. Definite languages and non-initial automata;66
9.9;9. Finite languages;75
9.10;10. Two-way automata;80
10;CHAPTER II. FINITE NON-DETERMINISTIC AND PROBABILISTIC AUTOMATA;84
10.1;1. Non-deterministic automata;84
10.2;2. Probabilistic automata and cut-point representation;86
10.3;3. Theorems concerning stochastic languages;91
10.4;4. Non-regular stochastic languages;101
10.5;5. Probabilistic sequential machines;108
10.6;6. Realizability of functions;119
11;CHAPTER III. ALGEBRA OF REGULAR EXPRESSIONS;127
11.1;1. Star height;127
11.2;2. Solution of equations;133
11.3;3. The sets Sr and Vr. Languages over a one-letter alphabet;140
11.4;4. Languages containing the empty word;144
11.5;5. Commutative languages;151
11.6;6. Non-existence of a finite basis for the sets dr;155
11.7;7. Two complete axiom systems;159
11.8;8. Operators preserving regularity;173
12;CHAPTER IV. FORMAL LANGUAGES AND GENERALIZED AUTOMATA;177
12.1;1. Hierarchy of languages;177
12.2;2. Type 3 languages;186
12.3;3. Context-free languages;190
12.4;4. Inclusion relations;203
12.5;5. Pushdown automata;205
12.6;6. Context-sensitive languages and linear bounded automata;213
12.7;7. Type 0 languages and Turing machines;228
12.8;8. Infinite-state machines;233
12.9;9. Abstract pushdown automata;237
12.10;10. Regular canonical systems;248
13;Historical and Bibliographical Remarks;256
14;References;260
15;Symbol Index;266
16;Author Index;268
17;Subject Index;270