8 - Transducers

Summary

‘Inputs to the nature yield rewarding outputs.’

Introduction

In the previous chapters, an abstract model of a machine that accepts input values but doesn't produce any output values, was discussed. Some machines, however, produce output values after accepting input values. In the case of FSA (finite state automata), movements from state qi to qj depend on the input at qi and no output emerges. However, in the case of FSM, a move from a state qi to state qj results in an output. Consequently, a FSM possesses two special features: a finite set Γ of output symbols and an output function λ :Q × ∑ → Γ, where ∑ is the input alphabet. Thus, one major limitation of finite automata is that its output is limited to a binary signal: ‘accept’ or ‘don't accept’, to indicate the acceptance or rejection of an input string respectively. In order to make finite automata to have output capabilities, two classical machines are designed that transform input strings into output strings. They are

1. a. Moore machine and

2. b. Mealy machine.

A Moore machine is a FSM – M₀, named after Edward Moore, who introduced it in 1956.

A Mealy machine is a FSM – M_e, named after George H.Mealy, who introduced it in 1955.

These machines are basically DFAs, except that they associate an output symbol with each state or with each state transition. However, there are no final states, because there is no acceptance or rejection involved.