## The `Transducer` structure

#### Synopsis

```signature TRANSDUCER structure Transducer :> TRANSDUCER ```

This structure adds to finite finite machines with pair-labels a translation function. While the finite machines accept sequences of pairs, the transducer translates the sequence of first components of the pairs to the sequence of second components.

#### Interface

```type ('a,'b) transducer = ('a * 'b) Fm.machine val translate : (''a, ''b)                     transducer                   -> ''a list -> ''b list list val accept : (''a, ''b)                  transducer                -> (''a * ''b) list -> bool val make : {                trans : (int * (''a * ''b) * int) list,                start : int list,                final : int list              } -> (''a, ''b) transducer val show : (''a, ''b)                transducer              -> {                start : int list,                trans : (int * (''a * ''b) * int) list,                final : int list              } val Atom : ''a * ''b -> (''a, ''b) transducer val Plus : (''a, ''b)                transducer list              -> (''a, ''b) transducer val Times : (''a, ''b)                 transducer list               -> (''a, ''b) transducer val Star : (''a, ''b) transducer -> (''a, ''b) transducer ```

#### Description

```type ('a,'b) transducer = ('a * 'b) Fm.machine ```

`translate tr l `
returns a list of all translations of the input sequence l by transducer tr.

`accept tr l `
returns true if tr accepts the sequence l of input pairs, false otherwise.

`make {trans, start, final} `
creates a transducer from the lists trans of transitions, start of initial and final of final states.

`show tr `
prints the lists of initial states, final states and transitions of tr.

`Atom (a, b) `
returns a transducer which translates a to b.

`Plus l `
returns the transducer which translates an input sequence to all sequences to which it is translated by some of the transducers in l.

`Times l `
returns the transducer obtained from the sequential composition of the underlying finite automata of the transducers in l. (Note that this is not the composition of the translations.)

`Star tr `
returns the feed-back of transducer tr, which translates an input sequence to the concatenations of translations by tr of the subsequences that concatenate to the input.

Fm, ppTransducer

#### Discussion

Since the automaton need not be deterministic, a single input sequence may be translated to several output sequences.

Example:
```- val Tr = Transducer.make{start = [0], final = [2],
trans = [(0,(0,false),0),(0,(1,true), 1),
(1,(1,false),1),(1,(1,true), 1),
(1,(0,true), 1),(1,(0,false),2)]}
val Tr = - : (int,bool) transducer

- Transducer.translate Tr [0,1,1,1,0,0]
val it =
[[false,true,false,true,true,false],[false,true,false,false,true,false],
[false,true,true,true,true,false],[false,true,true,false,true,false]]
: bool list list
```