Mealey

A Mealey machine is a finite-state machine whose output is determined by its current state and current input. In other words, the output is a function of the state and the input. This contrasts with a Moore machine, where the output is a function of only the current state.

Key Characteristics:

• Output Depends on State and Input: The defining characteristic. For a given state and input, a Mealey machine produces a specific output.
• Transition Function: Like other finite-state machines, Mealey machines have a transition function that determines the next state based on the current state and the input.
• Output Function: Mealey machines have an output function that determines the output based on the current state and the input.
• State Diagram Representation: They are commonly represented visually using state diagrams, where arcs (representing transitions) are labeled with both the input that triggers the transition and the corresponding output produced (e.g., "0/1" means input 0 generates output 1 and causes the transition).
• Often Fewer States Than Moore Machines: For some problems, a Mealey machine can achieve the same functionality as a Moore machine with fewer states, due to the direct relationship between input and output.

Formal Definition:

A Mealey machine can be formally defined as a 6-tuple: (S, I, O, T, s₀, F), where:

• S is a finite set of states.
• I is a finite set of input symbols (the input alphabet).
• O is a finite set of output symbols (the output alphabet).
• T is the transition function, mapping a state and an input symbol to the next state (T: S x I → S).
• s₀ is the initial state (s₀ ∈ S).
• F is the output function, mapping a state and an input symbol to an output symbol (F: S x I → O).

Applications:

Mealey machines are used in various applications, including:

• Digital Logic Design: Designing sequential circuits.
• Formal Language Theory: Recognizing patterns in strings of symbols.
• Cryptography: Building encryption and decryption systems.
• Control Systems: Implementing controllers based on state and input.
• Parsing: Implementing parsers in compilers.