We will now introduce finite state transducer s (or FSTs); another finite state machine that allows to produce output recording the structure of the input.