Let and be two Mealy machines.
In the same way, can be defined on two Moore machines. However, where as is restricted to be non-empty in the Mealy case, input words in Moore case are arbitrary, that is: iff
Here, is the modifications of the original output function .
is the set of equivalence classes of on ,
It is easy to verify that is indeed a well-defined machine. Furthermore, if is Moore, so is .
Call a machine (Mealy or Moore) reduced if implies . Then the machine constructed from above is a reduced machine.
Suppose and are both Mealy machines such that they have the same input and output alphabets.
Definition. is said to be equivalent to if every state of is equivalent to a state of , and vice versa. When is equivalent to , we write .
Equivalence between two Moore machines is similarly defined. It is clear that 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 be a Mealy machine and a Moore machine. is said to be similar to if every state of , there is a state of such that
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 if and 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:
Two Mealy machines similar to a Moore machine are equivalent. There exist two inequivalent Moore machines similar to a Mealy machine.
|Date of creation||2013-03-22 19:02:39|
|Last modified on||2013-03-22 19:02:39|
|Last modified by||CWoo (3771)|