mealymachines

Mealymachines, often referred to as Mealy machines, are a class of finite-state machines used in automata theory and digital design. They produce output based on both the current state and the input symbol, meaning the same state can yield different outputs depending on the input received. This makes Mealymachines particularly responsive to input changes during operation.

A Mealy machine is formally defined as a 6-tuple (S, S0, Σ, Λ, δ, λ), where S is a finite set of states, S0 is the initial state, Σ is the input alphabet, Λ is the output alphabet, δ: S×Σ → S is the state transition function, and λ: S×Σ → Λ is the output function. At each step, the next state is determined by δ, and the output is determined by λ, using the current state and the current input.

Compared with Moore machines, where outputs depend only on the state, Mealy machines can realize the same behaviors with fewer states in many cases. However, their outputs can change in response to input changes during a transition, which can require careful synchronization in hardware implementations to avoid glitches. Mealy machines are commonly used to implement sequential logic, encoders, decoders, and pattern detectors, where immediate reaction to an input is advantageous.

A typical simple example is a sequence detector that outputs a 1 when the last two inputs form the pattern 01. Such a detector can be built with two states: S0 (no relevant prefix) and S1 (last input was 0). From S0, input 0 moves to S1 with output 0, and input 1 stays in S0 with output 0. From S1, input 0 stays in S1 with output 0, and input 1 moves to S0 with output 1.