

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 21
Reading
Material
Introduction
to Computer Theory
Chapter
8
Summary
Example
of Moore machine, Mealy
machine, Examples, complementing machine,
Incrementing machine.
Example
To
identify the relation
between the input strings
and the corresponding output strings in
the following Moore
machine,
a
a
b
a
b
q0/0
q2/0
q1/0
q3/1
a
b
b
if the
string bbbabaabbaa is run, the output
string will be 000010000010, as shown
below
Input
b
b
b
a
b
a
a
b
b
a
a
State
q0
q1
q2
q2
q3
q1
q0
q0
q1
q2
q3
q0
output
0
0
0
0
1
0
0
0
0
0
1
0
It can be
observed from the given
Moore machine that q3 is the only state
which prints out the character 1
which
shows
that the moment the
state q3
is entered,
the machine will print
out 1. To enter the state
q3, starting from
q0
the
string must contain bba. It can
also be observed that to enter
the state q3 once more the string must
contain
another
substirng bba. In general the
input string will visit the
state q3
as many
times as the number of
substring
bba
occurs in the input string. Thus
the number of 1's in an output string
will be same as the number
of
substring
bba occurs in the corresponding
input string.
Mealy
machine
A Mealy
machine consists of the
following
A finite
set of states q0, q1, q2, ... where q0 is the initial
state.
An
alphabet of letters Σ =
{a,b,c,...} from which the
input strings are
formed.
An
alphabet G={x,y,z,...}
of output characters from which output
strings are
generated.
A
pictorial representation with
states and directed edges labeled by an
input letter along with an
output
character.
The directed edges also show
how to go from one state to
another corresponding to every
possible
input
letter.
(It is
not possible to give transition
table in this case.)
Note
It is to be
noted that since, similar to
Moore machine, in Mealy
machine no state is designated to be a
final state,
so there
is no question of accepting any language
by Mealy machine. However in
some cases the
relation
between
an input string and the corresponding
output string may be identified by the
Mealy machine.
Moreover,
the
state to be initial is not important as if
the machine is used
b/1
q2
q1
several
times and is restarted after
some time, the
machine
will be
started from the state
where it was left
b/1
a/0
a/0
a/1
off.
Following are the
examples
b/0
q3
q0
a/1
Example
b/1
Consider
the Mealy machine shown
aside, having the states
q0, q1, q2, q3 , where q0 is the start state
and
62
Theory of
Automata
(CS402)
Σ =
{a,b},
G={0,1}
Running
the string abbabbba over the
above machine, the corresponding output
string will be 11011010, which
can be
determined by the following table as
well
Input
a
b
b
a
b
b
b
a
States
q1
q0
q1
q2
q3
q3
q0
q3
q0
output
0
1
1
1
1
0
1
0
It may be
noted that in Mealy machine,
the length of output string is equal to that of
input string.
Example
Consider
the following Mealy machine
having the states q0, q1, q2 , where
q0 is the start
state and
Σ =
{a,b},
b/0
G={0,1}
q2
a/1
q1
b/1
a/0
a/0
b/0
q0
It is observed
that in the above Mealy
machine, if in the output string the nth
character is 1, it shows that
the nth
letter in
the input string is the
second in the pair of double
letter.
For
babaababba as input string the
machine will print
0000100010.
Example
Consider
the following Mealy machine
having the only state
q0 as the start
state and
Σ =
{0,1},
0/1,
1/0
G=
{0,1}
q0
If 0011010 is
run on this machine then
the corresponding output string will be
1100101.
This
machine is called Complementing
machine.
Constructing
the incrementing
machine
In the
previous example of complementing
machine, it has been observed
that the input string and
the
corresponding output
string are 1's complement of
each other. There is a question whether
the Mealy machine
can be
constructed, so that the output string is
increased, in magnitude, by 1 than the
corresponding input string?
The
answer is yes.
This
machine is called the incrementing
machine. Following is how to
construct the incrementing
machine.
Before
the incrementing machine is constructed,
consider how 1 is added to a
binary number.
Since, if
two numbers are added,
the addition is performed
from right to left, so while
increasing the binary
number by 1,
the string (binary number)
must be read by the corresponding
Mealy machine from right to
left,
and
hence the output string (binary
number) will also be
generated from right to
left.
Consider
the following additions
a)
100101110
b)
1001100111
+1
+1
100101111
1001101000
It may be
observed from the above
that
If the
right most bit of binary
number, to be incremented, is 0, the output
binary number can be obtained by
converting
the right most bit to 1
and remaining bits
unchanged.
If the
right most bit of binary
number is 1 then the output can be
obtained, converting that 1
along with all
its
concatenated
1's to 0's, then converting
the next 0 to 1 and
remaining bits
unchanged.
The
observations (a) and (b) help to
construct the following
Incrementing (Mealy)
machine.
The
Mealy machine have the
states q0, q1, q2 , where q0 is the start state
and
63
Theory of
Automata
(CS402)
Σ =
{0,1},
G={0,1}
0/0,1/1
0/1
q2
q1
1/0
0/1
1/0
q0
It may be
observed that, in the incrementing
machine, if 0 is read at initial
state q0, that 0
is converted to 1 and a
no change
state q1 (no carry
state) is entered where all
0's and all 1's remain
unchanged. If 1 is read at
initial
state,
that 1 is converted to 0 and
the state q2(owe
carry state) is
entered, where all 1's
are converted to 0's
and
at that
state if 0 is read that 0 is converted to
1 and the machine goes to no
change state.
If the
strings 100101110 and 1001100111 are
run over this machine,
the corresponding output strings will
be
100101111
and 1001101000 respectively.
Note
It is to be
noted that if the string 111111 is
run over the incrementing
machine, the machine will
print out
000000,
which is not increased in magnitude by 1.
Such a situation is called an overflow
situation, as the length
of output string
will be same as that of
input string.
It may
also be noted that there
exists another incrementing machine
with two states.
64
Table of Contents:

