Mathematical Foundation of Computer Science

DHARM

236 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

which is again the partial mapping of a state (∈ Q) with an input symbol (∈ Σ) and return an

output symbol (∈ ∆).

q ab/ p

Fig. 9.27

For example, the transition diagram shown in Fig. 9.27 of Melay case,

λ(q, a) = b; [returns a output symbol]

and δ(q, a) = p; [returns a state]

Thus, the purpose of the output function (λ) is to map the input string to output string.

9.6.1.2 Representation

The representation of the Melay machine is similar to the DFA representation such that the
states are represented by the small circles and the directed edges indicating transitions between
the states. Each edge is labeled with a compound symbol I/O where the edge to travel is
determined by the input symbol I, while traveling with the edge the output symbol O is printed.
For example, Fig. 9.28 shows a Melay machine Me = ({q 0 , q 1 , q 2 , q 3 }, {a, b}, {0, 1}, δ, λ, q 0 ).

q 0

q 1

q 3

q 2

b/1

a/1

a/0

b/1

b/0

b/1

a/0

a/1

Fig. 9.28. (Me)

So, on input strings ‘abbab’ and ‘aaabb’ we obtain the output strings ‘01111’ and ‘01110’

respectively.

FACT

l In a Melay machine the length of the output string is same as the length of input

string, i.e., if machine Me generates the output string w on processing the input string

x then | w | = | x |.

l Due to the absence of final state in the machine the language of the Melay machine

doesn’t define by accepting or rejecting the input strings.

Example 9.8

q 0

0/1, 1/0

Fig. 9.29 Me.