Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 243

Hence, the state diagram of equivalent Melay machine is constructed and which is shown

below in Fig. 9.36, where transition arcs are labeled with compound symbols i.e., input and

corresponding output symbol.

r 0

1/1

1/0

0/2

0/1

0/0

r 1 r 2

0/2

Fig. 9.36 Me.
Note. We observe from the state diagram of Melay machine that all incoming arcs to a state must
be labeled the output symbol which is equivalent to that state itself. Conversely, the role of state for its
outgoing arcs is nothing in the output generation. For example, consider a snapshot of machine Me (Fig.
9.37) where state r 0 has two incoming arcs labeled with input symbol 0 and 1. So the output symbol would
corresponds to state r 0 only, which is 0, so both arcs are labeled with output symbol 0.

r 0

1/0

0/0

Fig. 9.37

Similarly, with state r 1 , incoming arcs labeled with input and there corresponding output symbol

are shown below.

1/1

0/1

r 1

Fig. 9.38

Similarly output for other states can be determined.

9.7.2 Melay Machine-to-Moore Machine....................................................................

Now we shall discuss the method how an equivalent Moore machine is constructed form a
given Melay machine. Assume, Me be a Melay machine which is defined by following set of
tuples,
Me = (Qe, Σ, ∆, δe, λe, r 0 )
then an equivalent Moore machine Mo can be constructed from Me where,
Mo = (Qo, Σ, ∆, δo, λo, [r 0 , b])
(where all tuples as there usual meaning)
Now we can establish the relation between corresponding tuples of both the machines,
i.e.,
l Both machines operate on same set of input symbols Σ and same set of output
symbols ∆.
l Qo = Qe × ∆, i.e., states of the Moore machine is represented by an pair whose first
element is the state (∈ Qe) and the second element is the output symbol (∈ ∆). For
example, state [r, a] ∈ Qo, where state r ∈ Qe and a ∈ ∆.