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,'btransducer = ('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,'btransducer = ('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.


See Also

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