ZeePedia

NFA and Kleene’s Theorem

<< NFA with Null String
NFA corresponding to Concatenation of FAs >>
img
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
x1z1
(x1,x2)z2
z2(x1,x2)
)x1z1
(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
img
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 non-determinism
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
img
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