Select Page

Moore and Mealy machines are two types of finite state machines with outputs. Although they have different ways of associating outputs with states and transitions, they are equivalent in terms of computational power. This means that for any Moore machine, there exists a Mealy machine that recognizes the same language (and vice versa).

To show the equivalence between Moore and Mealy machines, we need to demonstrate two things:

  1. Conversion from Moore to Mealy: Given a Moore machine, we can construct an equivalent Mealy machine.
  2. Conversion from Mealy to Moore: Given a Mealy machine, we can construct an equivalent Moore machine.

Conversion from Moore to Mealy:

Given a Moore machine (Q, Σ, Δ, q0, λ, ρ), we can construct an equivalent Mealy machine (Q, Σ, Δ’, q0, λ’, δ), where:

  • The states Q, input alphabet Σ, and initial state q0 remain the same.
  • The output function of the Moore machine, λ: Q → Λ, becomes the output function of the Mealy machine, λ’: Q × Σ → Λ, defined as λ'(q, σ) = λ(q).
  • The transition function Δ: Q × Σ → Q of the Moore machine becomes the transition function Δ’: Q × Σ → Q of the Mealy machine.
  • We define the output of each transition in the Mealy machine using the Mealy output function δ: Q × Σ → Λ as follows: δ(q, σ) = λ'(Δ'(q, σ), σ).

Conversion from Mealy to Moore:

Given a Mealy machine (Q, Σ, Δ, q0, λ, δ), we can construct an equivalent Moore machine (Q, Σ, Δ’, q0, λ’, ρ), where:

  • The states Q, input alphabet Σ, and initial state q0 remain the same.
  • The output function of the Mealy machine, λ: Q × Σ → Λ, becomes the output function of the Moore machine, λ’: Q → Λ, defined as λ'(q) = λ(q0, σ) for any input symbol σ (since outputs in a Mealy machine depend on both the state and input symbol, but in a Moore machine, they only depend on the state).
  • The transition function Δ: Q × Σ → Q of the Mealy machine becomes the transition function Δ’: Q × Σ → Q of the Moore machine.
  • The output function ρ of the Moore machine is defined based on λ and Δ’: ρ(q) = λ'(q).

By demonstrating these conversions, we establish the equivalence between Moore and Mealy machines. This equivalence allows us to choose either representation based on convenience or specific requirements without affecting the computational power of the machine.