Finite State Transducer

Finite State Transducer (FST)

Definition 1

A finite state transducer is a type of Finite State Machine that maps input String to output strings.

Formally, it is a 6-tuple $(Q,\Sigma ,\Delta ,\delta ,\lambda ,q_0)$:

1. $Q$: finite set of states
2. $\Sigma$: input alphabet
3. $\Delta$: output alphabet
4. $\delta :Q\times \Sigma \to Q$: state transition function
5. $\lambda$: output function
   • Mealy type: $Q\times \Sigma \to \Delta$
   • Moore type: $Q\to \Delta$
6. $q_0\in Q$: start state

Human Definition While a DFA/FSM only accepts or rejects inputs, an FST can actually translate them into outputs.

• Example: In digital circuits, FSMs control the “state”, while FSTs produce outputs like signals or encoded strings.
• In computer science, FSTs are used for compilers, NLP (morphological analyzers, phonological rules), and protocol design.

Example 1

Imagine a machine that takes a binary string and outputs the parity (even/odd count of 1’s so far).

• Input Alphabet: $\Sigma =\{0,1\}$
• Output alphabet: $\Delta =\{\text{Even},\text{Odd}\}$
• States: $Q=\{q_{even},q_{odd}\}$
• Transitions: On 1 → toggle state; on 0 → stay in same state
• Outputs: Each state is labeled with Even/Odd (Moore style)

So the string 1101 would produce: Even → Odd → Even → Odd → Even.