Transducers and composition

While finite state automata seem to suffice in order to describe phonotactic (and morphotactic) well-formedness, phonology (and morphology) actually describes a relation between input and output forms. When we process an output form, we do not (usually) just want to know whether it is well-formed, but rather what inputs it could have arisen from.

• slides

• lecture

Finite state automata decompose acceptability (a global property) into smaller steps determined by individual segments. We can build on this idea, by decomposing the map from whole inputs to whole outputs into the concatenations of translations of individual segments. Formally, this can be achieved by adding ‘outputs’ to the transitions of our finite state automata. An example transducer is showin in figure 1.

data NFT_List q sigma gamma =
  NFT_List
  [q] -- the set of initial states
  [(q,[gamma])] -- the outputs associated with the initial states
  [(q,Maybe sigma,[gamma],q)] -- the transition relation
  [q] -- the set of final states
  [(q,[gamma])] -- the outputs associated with the final states

This example transducer erases all of the input characters it encounters. However, upon beginning to transduce, it outputs x, and upon finishing it outputs a particular number of y characters, depending on which state it ends in. And so it outputs xy if its input causes it to end in state EE, it outputs xyy if it ends in state OE, xyyy if in EO, and xyyyy if in OO.