Theory of Automata

by Arto Salomaa

In selecting material for this book the author had two principles in mind. In the first place, to consider 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 all treated as generalizations of this basic model. Secondly, the formalism chosen to describe finite deterministic automata is that of regular expressions. The book presents the mathematical foundations of the theory, rather than applications to switching circuits and programming, anf the contents are divided into four main chapter Finite deterministic automata; Finite non-deterministic and problematic automata; Algebra of regular expressions; Formal languages and generalized automata. No previous knowledge of the subject is required from the reader, but he should be familiar with the basic notions of set theory, algebra and probability. The book is a great source of reference for the research worker, but the fact that it develops the subject systematically, includes sections of exercises, and points at topics for further study, also make it a most valuable textbook for courses in the theory of automata. A further merit of the book is the considerable knowledge and experience of the author. It this respect it is valuable to note that he has published some twenty research papers on automata theory in leading journals.

263 pages, Hardcover

First published October 1, 1969

About the author

Arto Kustaa Salomaa was a Finnish mathematician and computer scientist. His research career, which spanned over 40 years, was focused on formal languages and automata theory.