The Theory of
Automata
In this chapter we begin with the study of automaton. We deal with transition
systems which are more general than finite automata. We define the
acceptability of strings by finite automata and prove that nondeterministic finite
automata have the same capability as the deterministic automata as far as
acceptability is concerned. Besides. we discuss the equivalence of Mealy and
Moore models. Finally, in the last section. we give an algorithm to construct a
minimum state automaton equivalent to a given finite automaton.
3.1 DEFINITION OF AN AUTOMATON
We shall give the most general definition of an automaton and later modify
it to computer applications. An automaton is defined as a system where
energy, materials and information are transformed. transmitted and used for
performing some functions without direct participation of man. Examples are
automatic machine tools, automatic packing machines, and automatic photo
printing machines.
In computer science the term 'automaton' means 'discrete automaton' and
is defined in a more abstract way as shown in Fig. 3.1.
/1
'j
Automaton
°1
/2
°2
-----~
/p
01,02' ... , On
Oq
Fig. 3.1 Model of a discrete automaton.
71