Mealy Machine

A finite state transducer where output depends on the current state and the input symbol. Output is produced on transitions, not on states. A 6-tuple.

$M = (Q, \Sigma, \Delta, q_0, \delta, \lambda)$ where:

• $Q$ is a finite set of states
• $\Sigma$ is the input alphabet
• $\Delta$ is the output alphabet
• $q_0 \in Q$ is the initial state
• $\delta : Q \times \Sigma \rightarrow Q$ is the transition function
• $\lambda : Q \times \Sigma \rightarrow \Delta$ is the output function

Example

A Mealy machine that outputs $1$ when the number of $a$s seen so far is even, and $0$ otherwise:

• States: $\{q_0, q_1\}$, where $q_0$ = even count, $q_1$ = odd count
• On input $a$ in $q_0$: move to $q_1$, output $0$
• On input $a$ in $q_1$: move to $q_0$, output $1$

Input aaa produces output 010.

Mealy vs Moore Machine

Both are finite state transducers. The difference is where output is generated.

Every Moore machine has an equivalent Mealy machine and vice versa. The Mealy-to-Moore conversion typically increases state count.