An Introduction to Formal Languages and Automata, 7th Edition

A.4 MOORE AND MEALY MACHINE EQUIVALENCE

The examples in the previous section show the difference between Moore and Mealy machines, but they also suggest that if a problem can be solved by a machine of one type, it can also be solved by one of the other type. In this sense, the two types of transducers are possibly equivalent.

DEFINITION A.3

Two finite-state transducers M and N are said to be equivalent if they implement the same function, that is, if they have the same domain and if

$$F_M(w)=F_N(w),$$

for all w in their common domain.

DEFINITION A.4

Let C₁ and C₂ be two classes of finite-state transducers. We say that C₁ and C₂ are equivalent if for every fst M in one class there exists an equivalent fst N in the other class and vice versa.