# Elements of Automata Theory

## Jacques Sakarovitch

Language: English

Pages: 782

ISBN: 0521844258

Format: PDF / Kindle (mobi) / ePub

Automata theory lies at the foundation of computer science, and is vital to a theoretical understanding of how computers work and what constitutes formal methods. This treatise gives a rigorous account of the topic and illuminates its real meaning by looking at the subject in a variety of ways. The first part of the book is organised around notions of rationality and recognisability. The second part deals with relations between words realised by finite automata, which not only exemplifies the automata theory but also illustrates the variety of its methods and its fields of application. Many exercises are included, ranging from those that test the reader, to those that are technical results, to those that extend ideas presented in the text. Solutions or answers to many of these are included in the book.

f 0 is: and the remainder of the number written f 1 is: 0 0 1 1 2 0 2 1 2 The machine starts computing in state 0. All of this is shown in Figure P.2 . 0 1 1 1 0 1 0 0 2 0 0 (a) The machine 11 1 11 1 0 1 2 0 (b) The computation of the remainder of 13 Figure P.2 : The divider by 3 which Pascal could have built, if he had thought of the foregoing. * Here we have an example of a non-trivial computation which can be performed with a ﬁxed quantity of memory, independent of the

algorithmically undecidable property or recursively undecidable property,27 due to Alan Turing, is certainly one of the most profound concepts discovered by mathematicians in the twentieth century. The proof that a given property (P ) is undecidable always consists of the reduction of this property to another, (Q), already known to be undecidable. We show that (Q) can be transformed eﬀectively into the property (P ). If this last has an algorithmic solution, we could deduce one for (Q), which is

ﬁnite) is inﬁnite is of the same nature as the question of its emptiness. In fact, L(A) is inﬁnite if and only if it contains arbitrarily long words and therefore cf. Def. 1.2, p. 53 70 CH. I . THE SIMPLEST POSSIBLE MACHINE. . . in particular of length greater than or equal to the number N = Q of states of A. A computation which accepts such a word f = a1 a2 · · · al can be written: a a al−1 a a l ql , q0 −−1→ q1 −−2→ q2 −−3→ · · · −−−−→ ql−1 −−→ (1.4) where q0 is in I and ql in T .

property that if it contains (p, 1A∗ , q) and (q, 1A∗ , r) , it also contains (p, 1A∗ , r) . In other words, S is the graph of the transitive closure of (the relation on Q whose graph is) S and can be eﬀectively constructed from S. 19 Nothing prevents us from further imagining an automaton whose transition labels are not words taken from A∗ but elements from any set that has a product operation (and also, implicitly, addition). We shall do this in the following chapters. 20 Most authors, who, as

Figure 2.10: The result of the state elimination method The ﬁrst phase involves constructing a normalised generalised automaton B by adding to A = Q, A, E, I, T two states i and t, distinct and not belonging to Q, a transition labelled 1A∗ from i to each initial state of A, and a transition labelled by 1A∗ from each ﬁnal state of A to t. The state i is the unique initial state of B, and t its unique ﬁnal state. Clearly, B is equivalent to A. Since A, and hence B, are ﬁnite, we can assume – even