equivalent machines
Let ${M}_{1}=({S}_{1},\mathrm{\Sigma},\mathrm{\Delta},{\sigma}_{1},{\lambda}_{1})$ and ${M}_{2}=({S}_{2},\mathrm{\Sigma},\mathrm{\Delta},{\sigma}_{2},{\lambda}_{2})$ be two Mealy machines.
Definition. A state ${s}_{1}$ of ${M}_{1}$ is said to be equivalent^{} to a state ${s}_{2}$ of ${M}_{2}$ iff
$${\lambda}_{1}({s}_{1},u)={\lambda}_{2}({s}_{2},u)\text{for all nonempty input words}u\text{over}\mathrm{\Sigma}.$$ 
We write $\approx $ for the equivalence.
In the same way, $\approx $ can be defined on two Moore machines. However, where as $u$ is restricted to be nonempty in the Mealy case, input words in Moore case are arbitrary, that is: ${s}_{1}\approx {s}_{2}$ iff
$${\beta}_{1}({s}_{1},u)={\beta}_{2}({s}_{2},u)\text{for all input words}u\text{over}\mathrm{\Sigma}.$$ 
Here, ${\beta}_{i}$ is the modifications of the original output function ${\lambda}_{i}$.
Suppose now that $M={M}_{1}={M}_{2}$. Then $\approx $ is an equivalence relation on the state alphabet $S$ of $M$. Given $M$, form a new machine ${M}^{\prime}=({S}^{\prime},\mathrm{\Sigma},\mathrm{\Delta},{\sigma}^{\prime},{\lambda}^{\prime})$ such that

1.
${S}^{\prime}:=S/\approx =\{[s]\mid s\in S\}$ is the set of equivalence classes^{} of $\approx $ on $S$,

2.
${\sigma}^{\prime}([s],a)=[\sigma (s,a)]$,

3.
${\lambda}^{\prime}([s],a)=\lambda (s,a)$.
It is easy to verify that ${M}^{\prime}$ is indeed a welldefined machine. Furthermore, if $M$ is Moore, so is ${M}^{\prime}$.
Call a machine (Mealy or Moore) reduced if ${s}_{1}\approx {s}_{2}$ implies ${s}_{1}={s}_{2}$. Then the machine ${M}^{\prime}$ constructed from $M$ above is a reduced machine.
Suppose ${M}_{1}$ and ${M}_{2}$ are both Mealy machines such that they have the same input and output alphabets.
Definition. ${M}_{1}$ is said to be equivalent to ${M}_{2}$ if every state of ${M}_{1}$ is equivalent to a state of ${M}_{2}$, and vice versa. When ${M}_{1}$ is equivalent to ${M}_{2}$, we write ${M}_{1}\approx {M}_{2}$.
Equivalence between two Moore machines is similarly defined. It is clear that $\approx $ is an equivalence relation on the class of Mealy machines (or Moore machines) over the same input and output alphabets.
In addition^{}, it is also possible to define “equivalence” between machines of different types. However, in the literature, the word “similar” is used instead of “equivalent”:
Definition. Let ${M}_{1}$ be a Mealy machine and ${M}_{2}$ a Moore machine. ${M}_{1}$ is said to be similar to ${M}_{2}$ if every state ${s}_{1}$ of ${M}_{1}$, there is a state ${s}_{2}$ of ${M}_{2}$ such that
$$\lambda ({s}_{1},u)=\beta ({s}_{2},u)\text{for all nonempty input words}u\text{over}\mathrm{\Sigma}.$$ 
The definition of a Moore machine similar to a Mealy machine is analogous. Note that in the definition of similarity, input words are restricted to nonempty words only.
Two machines of different types are similar if one is similar to another, and vice versa. We write ${M}_{1}\sim {M}_{2}$ if ${M}_{1}$ and ${M}_{2}$ are similar.
The concept^{} of similarity may be broadened to machines of the same type. In the Mealy case, similarity is the same as equivalence. In the Moore case, the two notions are different. Equivalence is more restrictive in that the empty word^{} is required in the definition. Two Moore machines may be similar without being equivalent. In fact, we have the following facts:
Proposition 1.
Two Mealy machines similar to a Moore machine are equivalent. There exist two inequivalent Moore machines similar to a Mealy machine.
Title  equivalent machines 
Canonical name  EquivalentMachines 
Date of creation  20130322 19:02:39 
Last modified on  20130322 19:02:39 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 68Q45 
Related topic  MealyMachine 
Related topic  MooreMachine 
Defines  equivalent 
Defines  similar 
Defines  reduced machine 