Difference Between Mealy And Moore Machine

SHARE

In computer science and engineering, finite state machines (FSMs) serve as essential tools for modeling and analyzing systems with discrete behaviors. Among the diverse range of FSMs, the Mealy machine and Moore machine stand as two major variants, each exhibiting various characteristics and applications.

While both machines share the common foundation of a finite set of states and state transitions, their respective methodologies for producing outputs based on inputs set them apart.

What Is Mealy Machine?

A Mealy machine is a type of finite state machine (FSM) that is used to model systems with discrete inputs and outputs. It is named after George H. Mealy, who introduced the concept in 1955. In other words, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs.

Mealy machines are used in digital circuit design, software verification, and protocol design, sequence recognition, control systems and error detection. They provide a powerful and flexible way to model systems with discrete behaviors and are an essential concept in the study of automata theory and formal languages.

A Mealy machine consists of five components:

  1. States: The Mealy machine has a finite set of states, represented by circles in graphical representations. Each state represents a particular condition or configuration of the system.
  2. Input Symbols: These are the possible inputs that the Mealy machine can receive. For example, in a simple Mealy machine that recognizes binary input, the input symbols could be {0, 1}.
  3. Output Symbols: These are the possible outputs that the Mealy machine can produce based on its current state and the input received. Output symbols are associated with transitions between states and are not associated with states themselves.
  4. State Transition Function: This function defines the next state of the Mealy machine based on the current state and the input symbol received. It is typically represented as a transition table or a directed graph.
  5. Output Function: This function determines the output produced by the Mealy machine based on the current state and the input symbol received. Unlike Moore machines (another type of FSM), the Mealy machine produces output based on the transitions and not just on the current state.

The transition and output functions can be represented in tabular form, where rows correspond to states, columns correspond to input symbols, and the entries represent the next state and output for each combination of state and input.

Mealy machines are known for their efficiency and compactness, especially when the outputs depend directly on the inputs. This is because the output is produced in response to each input, making it possible to create a more concise representation compared to Moore machines.

Graphical representation is commonly used to illustrate Mealy machines, where nodes represent states and directed edges represent transitions between states, labeled with the corresponding input/output symbols.

The behavior of a Mealy machine is determined by its initial state, the sequence of inputs provided to it, and the corresponding output produced as it transitions between states. By analyzing the state transition and output functions, one can predict the behavior of the machine for different input sequences.

Mealy machine can be described by a 6 tuple (Q, δ, Ʃ, O, X, q0 ) where:

  • Q is a finite set of states.
  • Ʃ is a finite set of symbols referred to as the input alphabets.
  • δ is the input transition function where δ:Q x Ʃ ―>Q
  • O is a finite set of symbols referred to as output alphabet.
  • X is the output transition function where X:Q x Ʃ―>O
  • q0 is the initial state from where any input is processed (q0 ϵQ)

What You Need To Know About Mealy Machine

  • Mealy machine changes its output based on its current input and present state.
  • Mealy machine will have same or fewer states than Moore machine.
  • Output is placed on transition.
  • The value of the output function is a function of the transitions and the changes, when the input logic on the present state is done.
  • Mealy machines react faster to inputs. They generally react in the same clock cycle.
  • Asynchronous output generation through the state changes synchronous to the clock.
  • Generally requires fewer states for synthesis.
  • Requires less hardware to design.
  • A counter is not a Mealy machine.
  • Not necessarily easy to design.

Also Read: Difference Between Pushdown Automata And Finite Automata

What Is Moore Machine?

A Moore machine is a type of finite-state machine (FSM) named after the computer scientist Edward F. Moore. It is a theoretical model used in computer science and engineering to describe and analyze systems with discrete inputs and outputs.

In other words, a Moore machine is a finite-state machine whose output values are determined only by its current state.

A Moore machine consists of five components:

  1. States: The machine operates in a finite set of states. Each state represents a particular condition or situation in the system.
  2. Inputs: The machine receives input symbols from a defined alphabet. These inputs determine the transitions between states.
  3. Outputs: Each state in the machine is associated with an output symbol. Whenever the machine enters a particular state, it produces the corresponding output symbol.
  4. Transition Function: The transition function defines the behavior of the machine. It maps a current state and an input symbol to the next state. In other words, it determines the state transitions based on the current state and input.
  5. Output Function: The output function maps the current state to the corresponding output symbol. Unlike Mealy machines (another type of finite-state machine), the output in a Moore machine depends only on the current state and not on the input.

The operation of a Moore machine can be summarized in a state transition table or represented graphically with a state transition diagram. In the state transition table, each row corresponds to a state, and each column corresponds to an input symbol. The intersection of a row and a column indicates the next state. Additionally, each state is associated with its corresponding output symbol.

Moore machines are used in various applications, such as digital systems, control systems, pattern recognition, and sequential circuit design. They are particularly useful in situations where the output depends primarily on the system’s internal state and not solely on the input sequence.

A Moore machine can be described as by a 6 tuple (Q, δ, Ʃ, O, X, q0 ) where:

  • Q is a finite set of states.
  • Ʃ is a finite set of symbols referred to as the input alphabets.
  • δ is the input transition function where δ:Q x Ʃ ―>Q
  • O is a finite set of symbols referred to as output alphabet.
  • X is the output transition function where X:Q x Ʃ―>O
  • q0 is the initial state from where any input is processed (q0 ϵQ)

What You Need To Know About Moore Machine

  • Output of Moore machine only depends on its current state and not on the current input.
  • Generally, it has more states than Mealy machine.
  • Output is placed on transition.
  • The value of the output function is a function of the current state and the changes at the clock edges, whenever state changes occur.
  • In Moore machines, more logic is required to decode the output resulting in more circuit delays. They generally react one clock cycle later.
  • Both output and state change synchronous to the clock edge.
  • Generally requires more states for synthesis.
  • More hardware is required to design.
  • A counter is a Moore machine.
  • Easy to design.

Also Read: Difference Between Finite Automata And Turing Machine

Difference Between Mealy And Moore Machine  In Tabular Form

BASIS OF COMPARISON MEALY MACHINE MOORE MACHINE
Description Mealy machine changes its output based on its current input and present state.   Output of Moore machine only depends on its current state and not on the current input.  
States Mealy machine will have same or fewer states than Moore machine.   It has more states than Mealy machine.  
Output Output is placed on transition.   Output is placed on transition.  
Value Of Output Function The value of the output function is a function of the transitions and the changes, when the input logic on the present state is done.   The value of the output function is a function of the current state and the changes at the clock edges, whenever state changes occur.  
Reaction To Inputs Mealy machines react faster to inputs. They generally react in the same clock cycle.   More logic is required to decode the output resulting in more circuit delays. They generally react one clock cycle later.
Output And State Asynchronous output generation through the state changes synchronous to the clock.   Both output and state change synchronous to the clock edge.  
States Requirement Generally requires fewer states for synthesis.   Generally requires more states for synthesis.  
Hardware Requirement Requires less hardware to design.   More hardware is required to design.  
Counter A counter is not a Mealy machine.   A counter is a Moore machine.  
Design Not necessarily easy to design.   Easy to design.