

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 12
Reading
Material
Chapter
7
Introduction
to Computer Theory
Summary
Examples
of writing REs to the corresponding
TGs, RE corresponding to TG accepting
EVENEVEN language,
Kleene's
theorem part III (method 1:union of FAs),
examples of FAs corresponding to simple
REs, example of
Kleene's
theorem part III (method 1) continued
Example
Consider
the following TG
To have
single initial and single final
state the above TG can be
reduced to the
following
To obtain single
transition edge between 1 and 3; 2
and 4, the above can be
reduced to the
following
To
eliminate states 1,2,3 and
4, the above TG can be
reduced to the following
TG
OR
34
Theory of
Automata
(CS402)
To
connect the initial state
with the final state by
single transition edge, the above TG
can be reduced to the
following
Hence
the required RE is (b+aa)b*+(a+bb)a*
Example
Consider
the following TG, accepting
EVENEVEN language
1±
It is to be
noted that since the
initial state of this TG is
final as well and there is
no other final state, so to obtain
a TG with
single initial and single final
state, an additional initial
and a final state are
introduced as shown in the
following
TG
To
eliminate state 2, the above
TG may be reduced to the
following
To have
single loop at state 1, the
above TG may be reduced to
the following
To
eliminate state 1, the above
TG may be reduced to the
following
Hence
the required RE is (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
Kleene's
Theorem Part III
Statement:
If the
language can be expressed by a RE
then there exists an FA
accepting the
language.
35
Theory of
Automata
(CS402)
As the
regular expression is obtained applying
addition, concatenation and closure on
the letters of an
alphabet
and
the Null string, so while
building the RE, sometimes,
the corresponding FA may be built
easily, as shown in
the
following examples
Example
Consider
the language, defined over Σ
= {a,b}, consisting of
only b, then
this language may be
accepted by the
following
FA
which
shows that this FA helps in
building an FA accepting only
one letter
Example
Consider
the language, defined over Σ
= {a,b}, consisting of
only Y, then
this language may be
accepted by the
following
FA
As, if
r1 and r2 are regular expressions
then their sum,
concatenation and closure
are also regular
expressions, so
an FA can
be built for any regular
expression if the methods
can be developed for
building the FAs
corresponding to
the sum, concatenation and
closure of the regular
expressions along with their
FAs. These
three
methods are explained in the
following discussion
Method1
(Union of two FAs): Using
the FAs corresponding to r1 and r2
an FA can be
built, corresponding to
r1+ r2. This method
can be developed considering the
following examples
Example
Let
r1 = (a+b)*b defines L1
and
the FA1 be
and
r2 = (a+b )*aa(a+b
)* defines L2 and
FA2 be
Let
FA3 be an FA corresponding to r1+ r2, then the
initial state of FA3 must
correspond to the initial
state of FA1
or the
initial state of FA2.
Since
the language corresponding to r1+ r2 is the union of
corresponding languages L1 and
L2, consists of
the
strings
belonging to L1or L2 or both, therefore a final
state of FA3
must
correspond to a final state of
FA1 or FA2
or
both.
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
is supposed to be
the initial state. Since
z1 corresponds to
the states x1 or y1,
so there
will be two transitions
separately for each letter
read at z1. It
will give two possibilities of
states either z1
or
different from z1.
This process may be
expressed in the following transition
table for all possible
states of
FA3.
36
Theory of
Automata
(CS402)
New
States after reading
Old
States
a
b
z1∫(x1,y1)
(x1,y2) ∫z2
(x2,y1) ∫ z3
z2 ∫(x1,y2)
(x1,y3) ∫z4
(x2,y1) ∫ z3
z3+ ∫(x2,y1)
(x1,y2) ∫ z2
(x2,y1) ∫ z3
z4+ ∫(x1,y3)
(x1,y3) ∫ z4
(x2,y3) ∫ z5
z5+ ∫(x2,y3)
(x1,y3) ∫ z4
(x2,y3) ∫ z5
RE corresponding to
the above FA may be r1+r2 = (a+b)*b + (a+b )*aa(a+b )*.
Note: Further
examples are discussed in
the next lecture.
37
Table of Contents:

