Mathematical Foundation of Computer Science

DHARM

244 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

l Start state of Moore machine is defined as [r 0 , b], where r 0 is the starting state of

Melay machine and b is any arbitrary symbol ∈ ∆.

l The return of output function λo when operated on the state like [r, a] ∈ Qo, will be

the output symbol that exist as the second element of the pair i.e.,

λo([r, a]) = a

l Transition function δo relates to δe like as,

δo([r, a], b) = [δe(r, b), λe(r, b)] = [p, d]

where, δe(r, b) = p (∈ Qe) and λe(r, b) = d ∈ ∆.

Example 9.12. Now we discuss some simple conversions from Melay machine to Moore machine.
(i) Consider a snapshot of Melay machine is shown in Fig. 9.39 (a) then its equivalent Moore
machine will be shown in Fig. 9.39 (b). (In the Moore machine second symbol of the state is the
output produced by the machine at that state)

r

a/1 b/1

c/1

[]r, 1

a b

c

Þ

(a) Melay Machine (b) Moore Machine

Fig. 9.39

(ii) since, output symbols are {0, 1} so the states of Moore machines are [r, 0] and [r, 1] and

there equivalence are shown in Fig. 9.40.

r Þ

a/0 b/0

b/1

b/1

a/1 []r, 0

a b

b/1 a/1

[]r, 1

b

b/1

a/1

(a) Melay machine (b) Moore machine

Fig. 9.40

Example 9.13. Construct the Moore machine from the Melay machine Me shown in Fig. 9.41

C 0

1/1

0/1

1/0

0/0

0/0 1/1

C 1 C 2

Me

Fig. 9.41

Sol. The given Melay machine Me can be defined as,

Me = ({C 0 , C 1 , C 2 }, {0, 1}, {0, 1}, δe, λe, C 0 ) and

Where the output function (λe) is shown in table I.