Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 235

B C

a, b

b

A

a

a

b

M

Fig. 9.25

Now if we put another symbol on each transition arc provided that it is associated with

the output information corresponding to that input symbol then the automaton M becomes M′

shown in Fig. 9.26.

B C

b a,b/0 /1

A

a/1

b/0

M¢

a/1

Fig. 9.26
where, we assume that output symbols are in set ∆ = {0, 1}. For example, if input string is
‘abba’ then automaton M′ generate an equivalent output string 1010 in the following manner,
l From starting state A, M′ reads the first symbol ‘a’ and return corresponding output
symbol 1 and reach to state B.
l Next input symbol is b, from state B, M′ reads symbol b and return corresponding
output symbol 0 and reach to state C.
l From state C, processed the remaining symbols a and b and return corresponding
symbols 0 and 1 respectively.
Hence, the input string ‘abba’ returns the string 1010 as output. Therefore, this type of
automaton M′ is known as Melay automaton & Melay Machine.

9.6.1.1 Definition

A Melay Machine is defined by following set of tuples,

1. A finite set of states Q,


2. A finite set of input symbols Σ,


3. A finite set of output symbols ∆,


4. Transition function δ,


5. Output function λ, and


6. A starting state q 0 , where q 0 ∈ Q
   So, a Melay automaton Me is defined using these 6 tuples as,
   Me = (Q, ΣΣΣΣΣ, ∆∆∆∆∆, δδδδδ, λλλλλ, q 0 )
   where the transition function δ is defined as,
   δ : Q × Σ → Q
   which is the partial mapping of a state (∈ Q) with an input symbol (∈ Σ) which returns a state
   (∈ Q). The output function λ is defined as,
   λ : Q × Σ → ∆