72 li\ Theory of Computer Science . _ - - - - - - - - - - - - - - -
The characteristics of automaton are now desClibed.
(i) Input. At each of the discrete instants of time t b t2, ...• t m the input
. values Ii' 1 2 ..... f p • each of which can take a finite number of fixed
values from the input alphabet ~, are applied to the input side of the
model shown in Fig. 3.l.
iii) Output. a" 0:;., ..., Oq are the outputs of the model, each of which.
can take a finite number of fixed values from an output O.
(iii) States. At any instant of time the automaton can be in onenf the
states ql' q:;., ..., qJl'
(iv) State relation. The next state of an automaton at any instant of time
is determined by the present state and the present input.
(v) Output relation. The output is related to either state only or to both
the input and the state. It should be noted that at any instant of time
the automaton is in some state. On 'reading' an input symbol, the
automaton moves to a next state which is given by the state relation.
Note: An automaton in which the output depends only on the input is called
an automaton without a memory. An automaton in which the output depends
on the states as well. is called automaton with a finite memory. An automaton
in which the output depends only on the states of the machine is called a
Moore machine. An automaton in. which the output depends on the state as
well as on the input at any instant of time is called a Mealy machine.
EXAMPLE 3.1
Consider the simple shift register shown in Fig. 3.2 as a finite-state machine
and study its operation.
. ID 0 11--,t1>II~ Q I. l i D 0 ,H,D --,Ol--s-eria-I
7:~~~
rU ~_ ootpol
I
I
I
.
i
Fig. 3.2 A 4-bit serial shift register using D flip-flops.
Solution
The shift register (Fig. 3.2) can have 2+ = 16 states (0000. 0001, .... 1111).
and one serial input and one serial output. The input alphabet is ~ = {O, I}.
and the output alphabet is 0 = {O. I}. This 4-bit selial shift register can be
further represented as in Fig. 3.3.
The characteristics of automaton are now desClibed.
(i) Input. At each of the discrete instants of time t b t2, ...• t m the input
. values Ii' 1 2 ..... f p • each of which can take a finite number of fixed
values from the input alphabet ~, are applied to the input side of the
model shown in Fig. 3.l.
iii) Output. a" 0:;., ..., Oq are the outputs of the model, each of which.
can take a finite number of fixed values from an output O.
(iii) States. At any instant of time the automaton can be in onenf the
states ql' q:;., ..., qJl'
(iv) State relation. The next state of an automaton at any instant of time
is determined by the present state and the present input.
(v) Output relation. The output is related to either state only or to both
the input and the state. It should be noted that at any instant of time
the automaton is in some state. On 'reading' an input symbol, the
automaton moves to a next state which is given by the state relation.
Note: An automaton in which the output depends only on the input is called
an automaton without a memory. An automaton in which the output depends
on the states as well. is called automaton with a finite memory. An automaton
in which the output depends only on the states of the machine is called a
Moore machine. An automaton in. which the output depends on the state as
well as on the input at any instant of time is called a Mealy machine.
EXAMPLE 3.1
Consider the simple shift register shown in Fig. 3.2 as a finite-state machine
and study its operation.
. ID 0 11--,t1>II~ Q I. l i D 0 ,H,D --,Ol--s-eria-I
7:~~~
rU ~_ ootpol
I
I
I
.
i
Fig. 3.2 A 4-bit serial shift register using D flip-flops.
Solution
The shift register (Fig. 3.2) can have 2+ = 16 states (0000. 0001, .... 1111).
and one serial input and one serial output. The input alphabet is ~ = {O, I}.
and the output alphabet is 0 = {O. I}. This 4-bit selial shift register can be
further represented as in Fig. 3.3.