84 !;' Theory of computer Science
TABLE 3.7 State Table of M i for Example 3.8
State/I
a
-_..._ - - _ . _ - - - - - -
b
[qo, Cli]
[qc. q1 q2]
[qJ Clil
[qol
[qo q,. q2l
[qo. q,]
[qQ. q-,. Q2. q3]
[qo. q,. q3]
[qo. qi. q3]
[qo. q1 Cl2]
[qo. Q,. q2]
[qc•. qi. q2. q3]
[qc. q, Cl2 q3]
[qo. qi. q2.{f31
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' - - -
3.8 MEALY AND MOORE MODELS
3.8.1 FINITE AUTOMATA WITH OUTPUTS
The finite automata \vhich we considered in the earlier sections have binary
output i.e. either they accept the string or they do not accept the string. This
acceptability \vas decided on the basis of reachahility of the final state by the
initial state. Now. we remove this restriction and consider the mode1 where the
outputs can be chosen from some other alphabet. The value of the output
function Z(t) in the most general case is a function of the present state q(t) and
the present input xU), i.e.
Z(n :::;
where Ie is called the output function. This generalized model is usua!Jy called
the !'v!ca!l' machine. If the output function Z(t) depends only on the present state
and is independent of the cunent input. the output function may be written as
Z(t) :::;
This restricted model is called the j'vJoore machine. It is more convenient to use
Moore machine in automata theory. We now give the most general definitIons
of these machines.
Definition 3.8 A Moore machine is a six-tuple (Q. L, ~. 8, I,. (]ol. where
(il Q is a finite set of states:
I is the input alphabet:
(i ii) ~ is the output alphabet:
8 is the transition function I x Q into Q:
I, is the output function mapping Q into ~; and
(]o is the initial state.
Definition 3.9 /'I. Ivlealy machine is a six-tuple (Q, I, ~, 8. )e, qo). "vhere
all the symbols except Ie have the same meaning as in the Moore machine. A.
is the output function mapping I x Q into ,1,
For example. Table 3.8 desclibes a Moore machme. The initial state iJo is
marked with an arrow. The table defines 8 ane! A...