Contents > Abstract Machines > State Machine

Transducer

A transducer is a device that translates an input string into an output string. One example is a cipher, a machine that performs encryption or decryption.

The following transducer implementation is identical to the classifier, except for the transition function, Tt, which modifies both the register and the ith character of the string, as opposed to just the register.

for i ← 0 to L−1
  ai‥aN+i ← Tt(ai‥aN+i)
  for j ← N−1 down to 0
    [ai+j+1,ai+j] ← [ai+j,ai+j+1]

As the program slides the register over the string, it transforms each input character into an output character: