# 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.

Computer Networks: A Systems Approach (5th Edition) (The Morgan Kaufmann Series in Networking)

Principles of Digital Image Processing, Volume 2: Core Algorithms

Automata and Computability (Undergraduate Texts in Computer Science)

letters, sets by upper case letters, and functions and relations on sets by Greek letters. The number of elements, or cardinal, of a ﬁnite set E is written1 E . If E is inﬁnite, its cardinal, a generalisation of the number of elements, is still written E . Most of the inﬁnite sets which we will consider will be denumerable – that is to say that they can be enumerated, or, more precisely, put in bijection with N, the set of non-negative integers. These are in a sense the smallest possible inﬁnite

letter-to-letter transducers 6.3 Synchronous relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 609 Another family of rational relations – Determinisation and minimisation – Geography of Rat A∗ ×B ∗ II 7 Malcev–Neumann series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616 7.1 617 Order on the free group . . . . . . . . . . . . . . . . . . . . . . . . . . On ordered groups – Representation of the free group – A detour via ordered rings – Order on the free

1A∗ )(K3 \ 1A∗ ) = a+ b+ : a a b a a to which must be added the three automata b b b SEC. 2. RATIONAL LANGUAGES 91 a a b b a a b b ✷ to recognise the whole of K1 . We see already in this construction the reason for the assumptions made by the deﬁnition of normalised automata: if there were a transition from t and therefore – since we can assume that A is trim – a circuit including t labelled f , and similarly, if there were a circuit including j labelled g, we could in some

expressions on a ﬁxed alphabet, and the languages they denote, then rational expressions on a set of variables and the result of interpreting such an expression. 4.1.1 Rational expressions over an alphabet Let A be a given (non-empty) alphabet and let {0, 1, +, ·, ∗} be ﬁve function symbols. Naturally, the operations + and · are binary, ∗ is unary, and 0 and 1 are nullary (they represent constants). Deﬁnition 4.1 A rational expression over A is a formula obtained inductively from the letters of

equality: ⎪ ⎪ ⎪⎪ ⎪ ⎪ ⎪ ⎪E⎪ ⎪ (6.14) ⎪E⎪ ⎪= A∗⎪ We have, for example: ⎪ ⎪⎪ ⎪ ⎪ ⎪ A∗ =⎪ ⎪∅⎪ ⎪ and ⎪ ⎪ ⎪ ⎪ ∗ ∗ ∗ (a b) =⎪ ⎪(a A ∩ A b) \ (A a a A∗ ∪ A∗ b b A∗ ) ∪ {1A∗ }⎪ ⎪. ∗ We can then deﬁne the generalised star height of a generalised rational expression, parallel to the formulas of § 6.1.3, by induction on the complexity of expressions: if E = 0, E = 1 or E = a ∈ A, gsh[E] = 0 , (6.15) if E = E + E or E = E · E , gsh[E] = max(gsh[E ], gsh[E ]) , (6.16) if E = F∗ , gsh[E] = 1 + gsh[F]