Mathematical Foundation of Computer Science

DHARM

242 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

9.7.1 Equivalent Machine Construction

(From Moore machine-to-Melay Machine)

Let Mo be a Moore machine i.e.,
Mo = (Qo, Σo, ∆o, δo, λo, r 0 )
then an equivalent Melay machine Me can be constructed from Mo i.e.,

Me = (Qe, Σe, ∆e, δe, λe, r 0 )
(where all symbols as there usual meaning)
Now we can establish the correspondence between the tuples of both the machines, i.e.
l Both machines operate on same set of states so Qo = Qe (let it be Q),
l Both machines operate on same set of input symbols so Σo = Σe (let it be Σ),
l Both machines operate on same set of output symbols so ∆o = ∆e (let it be ∆),
l Both machines start on same starting state {r 0 }.
l Transitions between states over input alphabets must be same in both machines so
δ = δe (let it be δ).
l The relation between the output function λe (Melay) to λo (Moore) will be defined as,
λe(r, a) = λo(δ(r, a)) [for ∀ r ∈ Q and ∀ a ∈ Σ]
Alternatively, the return of output function λe from any state over the input symbol is
same to the value of output function λe at the state obtain from the transition of that state over
that input symbol.
For example consider again a Moore machine shown in Fig. 9.34, i.e.,

r 0

1

1

0

0

0

r 1 r 2

1

0 12
Mo
where the set of states Q = {r 0 , r 1 , r 2 }, state {r 0 } is the starting state, set of input symbols Σ = {0, 1},
set of output symbols ∆ = {0, 1, 2}, transition function δ’s are defined as,
δ(r 0 , 0) = r 0 ; δ(r 0 , 1) = r 1 ;
δ(r 1 , 0) = r 2 ; δ(r 1 , 1) = r 0 ;
δ(r 2 , 0) = r 1 ; δ(r 2 , 1) = r 2 ;
and output function λ are defined as,
λ(r 0 ) = 0; λ(r 1 ) = 1; and λ(r 2 ) = 2;
(from the transition diagram shown)
Now determine the output function for Melay machine (λe) from the known output func-
tion for Moore machine (λo) i.e.,
λe(r 0 , 0) = λo(δ(r 0 , 0)) = λo(r 0 ) = 0 ; λe(r 0 , 1) = λo(δ(r 0 , 1)) = λo(r 1 ) = 1 ;
λe(r 1 , 0) = λo(δ(r 1 , 0)) = λo(r 2 ) = 2 ; λe(r 1 , 1) = λo(δ(r 1 , 1)) = λo(r 0 ) = 0 ;
λe(r 2 , 0) = λo(δ(r 2 , 0)) = λo(r 1 ) = 1 ; λe(r 2 , 1) = λo(δ(r 2 , 1)) = λo(r 2 ) = 2 ;