IV - THE RICHNESS OF TRANSDUCERS

Summary

In this chapter we undertake the study of relations realised by finite automata. It will be followed in the next chapter by the particularly fruitful special case of functional relations, or functions, which are also realised by finite automata. To this end, we shall be led to use several of the notions and results worked out in the previous two chapters, about automata over the direct products of free monoids (which are not free monoids) and about automata over free monoids but with weights in semirings of suitable coefficients.

This chapter also reproduces, in brief, the structure of the preceding three chapters. In the first section we shall begin by taking a ‘set’ point of view of the free monoid: automata relate words to words. We will thus construct a theory which has its roots in the origins of automata theory, and which has been more or less elaborated in many works.1 Its main aim has been the classification of families of non-rational languages, principally of sub-families of algebraic languages, by means of relations between words thus defined. This aspect will not be tackled here, and we shall stick to the study of the properties of these relations for their own sake.

In the second and third sections we shall continue this study in the general context of weighted automata and series. We shall first consider the problems inherent in the definition of (additive) maps which relate series to series, then study those which are recognised by finite automata. The subject is less often presented in this form.