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 non-empty 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 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)\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 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)\text{ for all non-empty 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 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.

Title	equivalent machines
Canonical name	EquivalentMachines
Date of creation	2013-03-22 19:02:39
Last modified on	2013-03-22 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