

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 17
Reading
Material
Chapter
7
Introduction
to Computer Theory
Summary
converting
NFA to FA (method 3), example,
NFA and Kleene's theorem
method 1, examples, NFA
and
Kleene's
theorem method 2 , NFA corresponding to
union of FAs, example
Method 3:
As
discussed earlier that in an
NFA, there may be more than
one transition for a certain letter
and
there
may not be any transition for
certain letter, so starting from the
initial state corresponding to the
initial
state of
given NFA, the transition
table along with new
labels of states, of the corresponding
FA, can be built
introducing
an empty state for a letter
having no transition at certain state
and a state corresponding to
the
combination of
states, for a letter having more
than one transitions.
Following are the
examples
Example
Consider
the following NFA which
accepts the language of
strings containing
bb
a,b
a,b
b
b
x3+
x2
x1
Using
the method discussed
earlier, the transition table
corresponding to the required FA may be
constructed as
New
States after reading
Old
States
a
b
z1∫x1
x1∫z1
(x1,x2)∫z2
z2∫(x1,x2)
)∫x1∫z1
(x1 ,x2,x3) ∫z3
(x1 ,
z3+∫(x1,x2,x3)
(x1,x3)∫z4
(x1 ,x2,x3)∫z3
z4+∫ (x1,x3)
(x1,x3)∫z4
(x1 ,x2,x3)∫z3
The
corresponding transition diagram follows as
a
b
a
a
b
b
z3+
z1
z2
z4+
b
a
NFA
and Kleene's Theorem
It has
been discussed that, by
Kleene's theorem part III,
there exists an FA corresponding to a
given RE. If the
given RE
is as simple as r = aa+bbb or r = a(a+b)*, the corresponding FAs can
easily be constructed.
However,
for a
complicated RE, the RE can
be decomposed into simple REs
corresponding to which the FAs
can easily be
constructed
and hence, using the method,
constructing the FAs corresponding to
sum, concatenation and
closure
of FAs,
the required FA can also be
constructed. It is to be noted that
NFAs also help in proving
Kleene's
theorem
part III, as well. Two
methods are discussed in the
following.
NFA
and Kleene's Theorem
Method
1:
The
method is discussed considering the
following example.
Example
To
construct the FAs for
the languages L1 = {a}, L2 = {b}
and L3 = {Y}
Step 1:
Build NFA1, NFA2 and
NFA3 corresponding to L1, L2 and L3 ,
respectively as shown in the
following
diagram
50
Theory of
Automata
(CS402)
a
NFA1
ć
+
b
NFA2
ć
+
±
NFA3
Step
2:
As
discussed earlier for every
NFA there is an FA equivalent to
it, hence there must be
FAs for the
above
mentioned
NFAs as well. The corresponding
FAs can be considered as
follows
b
a
+
+
a,b
a,b
FA1
FA2
a
b
1
1
a,b
a,b
a,b
a,b
1
±
FA3
NFA
and Kleene's Theorem method
2
It may be
observed that if an NFA can be
built corresponding to union,
concatenation and closure of
FAs
corresponding to
the REs, then converting
the NFA, thus, obtained into
an equivalent FA, this FA
will
correspond
to the given RE.
Followings
are the procedures showing
how to obtain NFAs equivalent to
union, concatenation and
closure of
FAs
NFA
corresponding to Union of FAs
Method
Introduce
a new start state and
connect it with the states
originally connected with
the old start state
with the
same
transitions as the old start
state, then remove the
ve sign of old start
state. This creates
nondeterminism
and
hence results in an
NFA.
b
Example
a
x1
x2
NFA1
b
a
b
a
a
x4+
x3
b
a,b
a
b
y2+
y1
NFA2
51
Theory of
Automata
(CS402)
b
a
a
x1
x2

b
b
a
a
b
a
b
a
x4+
x3
b
a
a,
b
b
y1
y2+
NFA
equivalent to FA1«FA2
52
Table of Contents:

