## You are here

Homeequivalent machines

## Primary tabs

# equivalent machines

Let $M_{1}=(S_{1},\Sigma,\Delta,\sigma_{1},\lambda_{1})$ and $M_{2}=(S_{2},\Sigma,\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)\mbox{ for all non-empty input words% }u\mbox{ over }\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 non-empty 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)\mbox{ for all input words }u\mbox{ over% }\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}},\Sigma,\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 well-defined 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)\mbox{ for all non-empty input words }u\mbox{ % over }\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 non-empty 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.

## Mathematics Subject Classification

03D05*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections