

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 13
Reading
Material
Chapter
7
Introduction
to Computer Theory
Summary
Examples
of Kleene's theorem part III (method 1)
continued, Kleene's theorem part III
(method 2:
Concatenation
of FAs), Example of Kleene's
theorem part III (method 2 : Concatenation of
FAs)
Note
It may be
noted that the example
discussed at the end of
previous lecture, FA1 contains two states
while FA2
contains
three states. Hence the
total number of possible combinations of states of
FA1 and FA2, in sequence,
will be
six. For each combination
the transitions for both a
and b can be determined, but using the
method in the
example,
number of states of FA3 was
reduced to five.
Example
Let
r1 = (a+b)*a and the corresponding FA1 be
a
b
a
x1
x2+
b
also
r2 = (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b)
and FA2 be
a,b
y1
y2+
a,b
FA corresponding to
r1+r2 can
be determined as
a
b
a,b
a
x1
y1
x2+
y2+
b
a,b
New
States after reading
Old
States
a
b
z1∫(x1,y1)
(x2,y2) ∫z2
(x1,y2) ∫ z3
z2+∫(x2,y2)
(x2,y1) ∫z4
(x1,y1) ∫ z1
z3+ ∫(x1,y2)
(x2,y1) ∫z4
(x1,y1) ∫ z1
z4+ ∫(x2,y1)
(x2,y2) ∫ z2
(x1,y2) ∫ z3
a
z2+
z1
b
a
a
b
b
a
z4+
z3+
b
Example
Let
r1 = ((a+b)(a+b))* and the corresponding FA1 be
a,b
x1±
x2
a,b
38
Theory of
Automata
(CS402)
also
r2 = (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b)
and FA2 be
a,b
y1
y2+
a,b
FA corresponding to
r1+r2 can
be determined as
New
States after reading
Old
States
a
b
z1±∫(x1,y1)
(x2,y2) ∫z2
(x2,y2) ∫ z2
(x1,y1) ∫z1
(x1,y1) ∫ z1
z2+∫(x2,y2)
Hence
the required FA will be as
follows
a,b
z1±
z2+
a,b
Method2
(Concatenation of two
FAs):
Using
the FAs corresponding to r1 and r2, an FA
can be built, corresponding to r1r2. This method
can be
developed
considering the following
examples
Example
Let
r1 = (a+b)*b defines L1
and
FA1 be
b
a
b
x1
x2+
a
*
*
and
r2 = (a+b ) aa (a+b ) defines L2 and FA2 be
a,b
b
a
a
y3+
y2
y1
b
Let
FA3 be an FA corresponding to r1r2, then the
initial state of FA3 must correspond to the
initial state of FA1
and
the final state of FA3 must correspond to the
final state of FA2.Since the language
corresponding to r1r2 is
the
concatenation of corresponding languages L1 and L2,
consists of the strings
obtained, concatenating
the
strings
of L1 to those of L2 , therefore the moment a
final state of first FA is entered, the
possibility of the
initial
state of second FA will be
included as well.
Since, in
general, FA3
will be
different from both FA1 and FA2, so
the labels of the states of
FA3 may be
supposed
to be z1,z2, z3, ..., where z1
stands
for the initial state.
Since z1
corresponds to
the states x1, so
there
will be
two transitions separately
for each letter read at z1. It will give two
possibilities of states which
correspond
to either z1 or different from
z1. This process
may be expressed in the
following transition table
for
all
possible states of FA3
b
a
b
x1
x2+
a
a,b
b
a
a
y3+
y2
y1
b
39
Theory of
Automata
(CS402)
New
States after reading
Old
States
a
b
x1∫z1
(x2,y1)∫ z2
z1∫x1
z2∫(x2,y1)
(x1,y2)∫z3
(x2,y1)∫ z2
z3∫(x1,y2)
(x1,y3)∫z4
(x2,y1)∫ z2
z4+∫(x1,y3)
(x1,y3)∫ z4
(x2,y1,y3)∫ z5
z5+∫(x2,y1,y3)
(x1,y2 ,y3)∫ z6
(x2,y1,y3)∫ z5
z6+∫(x1,y2,y3)
(x1,y3)∫ z4
(x2 ,y1,y3)∫ z5
Hence
the required FA will be as
follows
b
a
z3
z2
b
a
b
a
z4+
z1
a
a
b
b
z5+
z6+
b
a
Note:
Another example is discussed in
the next lecture.
40
Table of Contents:

