Inclusion
As already illustrated, the notion of equivalence is the key for comparison of the external behavior of complete automata, and ultimately for the minimization of a given complete automaton. However, if incompleteness is considered, it is not significant t
- PDF / 3,750,007 Bytes
- 58 Pages / 481.89 x 691.654 pts Page_size
- 2 Downloads / 198 Views
AN D
L E C TU RE S
-
No.
88
FADRIZIO LUCCIO UNIVERSITY
OF
PISA
AN INTRODUCTION TO THE THEORY OF AUTOMATA
COl'RSE HELD AT THE DEPARTMENT
FOR AUTOMATION AND INFORMATION JULY 1971
UDINE 1971
SPRINGER-VERLAG WIEN GMBH
ISBN 978-3-211-81082-8 ISBN 978-3-7091-2816-9 (eBook) DOI 10.1007/978-3-7091-2816-9
Copyright 1971 by Springer-Verlag Wien Originally published by Springer Vienna in 1971
P R E F A C E In the short extension of five lecture?~ we try to summarize some of the basic notions of Automata Theory. Our concern throughout these notes has been the use of an understandabZe form of presentation~ without loss of rigor. Frequent examples are discussed~ and some simple exercises have been inserted in the mainly as tests for comprehension. Since the field of automata has grown up to a considerable size~ some topics have been purposedZy ignored: among them~ Turing machines constitute the most spectacular omission. In fact~ such machines are illustrated in a companion set of lectures, while emphasis is given here to the System Theory approach to automata~ along the lines indicated by KaZman~ Falb and Arbib in [5] . It must be noted~ however~ that Automata Theory has been deeply influenced by parallel studies on sequential networks, since the pioneering
text~
work of Huffman and Moore on the theoretical bases of data processors. Several aspects of our models will be seen in this light~ according to the classical textbook by Ginsburg [3]. Then~ to demonstrate the flexibility of automata~ a number of examples will be taken
4
Preface
from different fieZds of appZication. At the end of these Zectures, the student wiZZ just ga~n a gZance on the vast worZd of automata. A rich Ziterature - in particuZar, the superb Zast effort of Arbib [1] - is then at his disposaZ, to heZp him entering the fieZd. I wish to conclude warmly thanking CISM for its invitation to deliver these Zectures, in a unique atmosphere of international cooperation on high scientific standing. F.
Udine, JuZy 1971
L.
5
1. Introductio n: Automata and Systems. In the process of evolution that the science con-
tinuously follows, two facts are relevant to the study that we are going to undertake: namely i.
the icreasing power of an abstract mathematica l model, the automaton, as to cover a variety of different entities;
and, on a higher level, ii. the massive growth of System Theory as a unifying discipline, to encompass a number of topics falling in the classical range of "Mathematics for Engineers". Since i. and ii. are recent facts, the confluence of Automata Theory into System Theory is a very recent but perfectly legitirnate result.
In the consequent perspective , the automaton is seen as a system of special nature, evolving in discrete times through discrete points of the state space. Such a vantage position has been strongly assumed by Kalman, Falb and Arbib [5], and will be adopted here for a general observation of the automaton behavior. As a result, such notions as controllab ility and observabili ty on one side, equivalence a
Data Loading...
