Next: Composition Up: Operations on transducers Previous: Operations on transducers

Identity

The identity relation for a given language L is . For a given pfsr , the identity relation is given by the pfst . Note that it would be wrong to define . Suppose is true only of . The pair then would be true of the pairs of symbols , whereas identity requires that we only allow the pairs . Another example to stress the point: the expression identity(?) (copy') is quite different from ?:? (garbage-in garbage-out'). It is therefore necessary to introduce an identity marker for each of the transitions. The identity of a pfsr is given by where .

The operations domain, range and inverse are straightforward. For a given pfst , we have:

• domain(R(M)) is given by the pfsr where .

• range(R(M)) is given by the pfsr where .

• inverse(R(M)) is given by the pfst where .

Noord G.J.M. van
2001-06-22