Mealy Automaton

automata-theory

Definition

Mealy Automaton

A Mealy automaton is a special case of a transducer that is defined by a tuple:

$$\mathcal{M}=(Q,\Sigma ,\Gamma ,\delta ,\gamma ,q_0)$$

where:

• $Q$ is the finite set of states
• $\Sigma$ is the input alphabet
• $\Gamma$ is the output alphabet
• $\delta :Q\times \Sigma \to Q$: is the transition function
• $\gamma :Q\times \Sigma \to \Gamma$: is the output function
• $q_0\in Q$ is the initial state

A Mealy automaton is a a deterministic automaton that doesn’t have empty word transitions, has an output function, a single initial state, and no explicit accepting states ($F=Q$).

Output Function

Extended Output Function

Extended Output Function

The extended output function ${\gamma }^{\ast }:Q\times {\Sigma }^{\ast }\to {\Gamma }^{\ast }$ is a function that takes a state $q\in Q$ and an input string $x\in {\Sigma }^{\ast }$ and returns the output $y\in {\Gamma }^{\ast }$.

Examples

Detector for $111$-Blocks

$$\begin{array}{rl}w& :00110111110101110\dots \\ [\mathcal{M}](w)& :00000001110000010\dots \end{array}$$

The mealy automaton $\mathcal{M}$ outputs $1$ if 3 consecutive $1$s are found in the input word, and $0$ otherwise: