Theory of Automata - 1st Edition - ISBN: 9780080133768, 9781483154398

Theory of Automata, Volume 100

1st Edition

Editors: I. N. Sneddon M. Stark J. P. Kahane
Authors: Arto Salomaa
eBook ISBN: 9781483154398
Imprint: Pergamon
Published Date: 1st January 1969
Page Count: 276
Tax/VAT will be calculated at check-out Price includes VAT (GST)
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
43.99
30.79
30.79
30.79
30.79
30.79
35.19
35.19
72.95
51.06
51.06
51.06
51.06
51.06
58.36
58.36
54.95
38.47
38.47
38.47
38.47
38.47
43.96
43.96
Unavailable
Price includes VAT (GST)
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents


Preface

Acknowledgments

Note to the Reader

Chapter I. Finite Deterministic Automata

§ 1. Regular Languages

§ 2. Analysis And Synthesis Theorems

§ 3. Characteristic Equations

§ 4. Equivalence Relations Induced by Languages

§ 5. Sequential Machines

§ 6. Experiments and Minimization

§ 7. Sequential Functions and Relations

§ 8. Definite Languages and Non-Initial Automata

§ 9. Finite Languages

§10. Two-Way Automata

Chapter II. Finite Nonn-Determinintic and Probabilistic Automata

§ 1. Non-Deterministic Automata

§ 2. Probabilistic Automata and Cut-Point Representation

§ 3. Theorems Concerning Stochastic Languages

§ 4. Non-Regular Stochastic Languages

§ 5. Probabilistic Sequential Machines

§ 6. Realizability of Functions

Chapter III. Algebra of Regular Expressions

§ 1. Star Height

§ 2. Solution of Equations

§ 3. The Sets Sr and (Vr. Languages Over a One-Letter Alphabet

§ 4. Languages Containing the Empty Word

§ 5. Commutative Languages

§ 6. Non-Existence of a Finite Basis for the Sets <°G,

§ 7. Two Complete Axiom Systems

§ 8. Operators Preserving Regularity

Chapter IV. Formal Languages and Generalized Automata

§ 1. Hierarchy of Languages

§ 2. Type 3 Languages

§ 3. Context-Free Languages

§ 4. Inclusion Relations

§ 5. Pushdown Automata

§ 6. Context-Sensitive Languages and Linear Bounded Automata

§ 7. Type 0 Languages and Turing Machines

§ 8. Infinite-State Machines

§ 9. Abstract Pushdown Automata

§ 10. Regular Canonical Systems

Historical And Bibliographical Remarks

References

Symbol Index

Author Index

Subject Index

Description

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.


Details

No. of pages:
276
Language:
English
Copyright:
© Pergamon 1969
Published:
Imprint:
Pergamon
eBook ISBN:
9781483154398

About the Editors

I. N. Sneddon Editor

M. Stark Editor

J. P. Kahane Editor

About the Authors

Arto Salomaa Author