Mathematical Foundation of Computer Science

DHARM

234 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

This section introduces other forms of finite automatons, which operates on input string

and returned the output in some form of string, instead of decisions. This types of finite au-

tomatons are called as Finite Automatons with Output. So, the behavior of finite automatons

with output are captured by the nature of the output string it generates. Eventually, the sig-

nificance of final state is meaningless†. Fig 9.23 shows the abstract view of a finite automata

with output. Let automaton M be a finite automata with output, that operates on some input

string (∈ Σ*), where Σ is the set of input symbols and it returns the output string (∈ ∆), where

∆ is the set of output symbols.

M

Input

String

Output

String

Fig. 9.23

So, the automaton M behaves as a Transducer. Let us represented it by TM where,

TM : Σ* → ∆*

Assume x be a input string i.e., x ∈ Σ* then,

TM(x) = w {where w ∈ ∆*}

Let x be a input string and it can break into a sub string y and a symbol a, i.e.,

x = y. a

and similarly assume w is the output string i.e., w = y′. a′

where, TM(x) = TM( y. a) = w = y′. a′

Assume, automata M is in starting state r 0 , and after consuming input string y it reaches

to state rj with return string y′ as output and on next symbol a it reaches to state rj+1 with return

symbol a′ as output and it stops because whole string x is now consumed by M, no matter what

state rj+1 is. It may be any state including starting state r 0.

r 0 rj a rj+1

y¢ a¢

y

(output string/symbol)

Fig. 9.24

So, the concept of final state does’nt arises here. On which state automaton stops that is

depend upon the input string i.e., after reading the last symbol of the input string it will stop.

There are two types of Automatons exist under this category,

1. Melay Automaton (Machine)


2. Moore Automaton (Machine)

9.6.1 Melay Automaton...............................................................................................

In the Melay automaton output is given over the transition arc. Assume a portion of DFA M is
in Fig. 9.25, where M = ({A, B, C}, {a, b}, δ, A, Φ}, here set of final state is Φ because it is useless
to talk about the final state in case of Finite automan with output.

† Finite Automatons with output has no final state/s, because from the strating state automaton

generates the output in some form of symbols on each transitions betweeen the states. Automaton can

stop, any of the state (∈ Q) depending upon the nature of the input string.