Transducer
structure
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.
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
type ('a,'b) transducer = ('a * 'b) Fm.machine
translate tr l
accept tr l
make {trans, start, final}
show tr
Atom (a, b)
Plus l
Times l
Star tr
Fm, ppTransducer
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