A common task arising in many contexts is rewriting parts of a given input string to another form. Subparts of the input that match specific conditions are replaced by other output parts. In this way, the complete input string is translated to a new output form. Due to the importance of text rewriting, many programming languages offer matching/rewriting operations for subexpressions of strings, also called replace rules. When using strictly regular relations and functions for representing replace rules, a cascade of replace rules can be composed into a single transducer. If the transducer is functional, an equivalent bimachine or (in some cases) a subsequential transducer can be built, thus achieving theoretically and practically optimal text processing speed. In this chapter we introduce basic constructions for building text rewriting transducers and bimachines from replace rules and provide implementations. A first simple version in general leads to an ambiguous form of text rewriting with several outputs. A second more sophisticated construction solves conflicts using the leftmost-longest match strategy and leads to functional devices.

An important generalization of classical finite-state automata are multi-tape automata, which are used for recognizing relations of a particular type. The so-called regular relations (also refered to as ‘rational relations’) offer a natural way to formalize all kinds of translations and transformations, which makes multi-tape automata interesting for many practical applications and explains the general interest in this kind of device. A natural subclass are monoidal finite-state transducers, which can be defined as two-tape automata where the first tape reads strings. In this chapter we present the most important properties of monoidal multi-tape automata in general and monoidal finite-state transducers in particular. We show that the class of relations recognized by n-tape automata is closed under a number of useful relational operations like composition, Cartesian product, projection, inverse etc. We further present a procedure for deciding the functionality of classical finite-state transducers.

In this chapter we present C(M) implementations of the main automata constructions. Our aim is to provide full descriptions of the implementations that are clear and easy to follow. In some cases the simplicity of the implementation is achieved at the expense of some inefficiency.