Skip to main content
main-content

Über dieses Buch

Automata theory is the oldest among the disciplines constituting the subject matter of this Monograph Series: theoretical computer science. Indeed, automata theory and the closely related theory of formal languages form nowadays such a highly developed and diversified body of knowledge that even an exposition of "reasonably important" results is not possible within one volume. The purpose of this book is to develop the theory of automata and formal languages, starting from ideas based on linear algebra. By what was said above, it should be obvious that we do not intend to be encyclopedic. However, this book contains the basics of regular and context-free languages (including some new results), as well as a rather complete theory of pushdown automata and variations (e. g. counter automata). The wellknown AFL theory is extended to power series ("AFP theory"). Additional new results include, for instance, a grammatical characterization of the cones and the principal cones of context-free languages, as well as new decidability results.

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract
Automata theory is the oldest among the disciplines constituting the subject matter of this Monograph Series: theoretical computer science. Indeed, automata theory and the closely related theory of formal languages form nowadays such a highly developed and diversified body of knowledge that even an exposition of “reasonably important” results is not possible within one volume.
Werner Kuich, Arto Salomaa

Chapter I. Linear Algebra

Abstract
In this chapter we define the notions basic for the whole book. As already pointed out in the Introduction, a reader who is not interested in the formal details or proofs may just study the basic definitions in Chapter I and consult this chapter later whenever needed.
Werner Kuich, Arto Salomaa

Chapter II. Automata

Abstract
We are now ready to begin the development of automata theory. We start with the classical notion of a finite automaton. It will be generalized in essentially three directions. All of the basic definitions will be given in terms of matrices. This will bring about a uniform way of discussing automata theory. Also the interconnections of automata theory, referred to above, and systems of equations will be made explicit.
Werner Kuich, Arto Salomaa

Chapter III. Algebraic Systems

Abstract
The last chapter of this book discusses algebraic power series and their relation to context-free grammars and languages. The notion Aalg«∑*» was already defined above in connection with pushdown automata in Section 10. We now consider the series in this collection from a new angle, corresponding to defining equations. The defining equations are algebraic in the classical sense, i.e., polynomial equations. However, their rather specific form reflects the particular requirements for context-free grammars.
Werner Kuich, Arto Salomaa

Backmatter

Weitere Informationen