ZeePedia

Closure of an FA

<< Concatenation of FAs
Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 14
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), Examples of Kleene's theorem part III(method 2:concatenation FAs) continued,
Kleene's theorem part III (method 3:closure of an FA), examples of Kleene's theorem part III(method 3:Closure
of an FA) continued
Example
Let r1 = ((a+b)(a+b))* and the corresponding FA1 be
a,b
x2
x1±
a,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 r1r2 can be determined as
New States after reading
Old States
a
b
z1-(x1,y1)
(x2,y2) z2
(x2,y2) z2
z2+(x2,y2)
(x1,y1) z1
(x1,y1) z1
Hence the required FA will be as follows
a,b
y1-
y2+
a,b
Method3: (Closure of an FA)
Building an FA corresponding to r*, using the FA corresponding to r.
It is to be noted that if the given FA already accepts the language expressed by the closure of certain RE, then
the given FA is the required FA. However the method, in other cases, can be developed considering the
following examples
Closure of an FA, is same as concatenation of an FA with itself, except that the initial state of the required FA
is a final state as well. Here the initial state of given FA, corresponds to the initial state of required FA and a
non final state of the required FA as well.
Example
Let r = (a+b)*b and the corresponding FA be
b
a
b
x1-
x2+
a
41
img
Theory of Automata
(CS402)
then the FA corresponding to r* may be determined as under
b
b
a
a
b
b
x1-
x1-
x2+
x2+
a
a
New States after reading
Old States
a
b
Final z1 ±x1
x1z2
(x2,x1)z3
Non-final z2x1
x1z2
(x2,x1)z3
z3+(x2,x1)
x1z2
(x2,x1)z3
The corresponding transition diagram may be as under
z1±
a
b
b
a
z3+
z2
a
b
Example
Let r = (a+b)*aa(a+b)* and the corresponding FA be
a,b
b
a
a
y3+
y2
y1-
b
then the FA corresponding to r* may be determined as under
New States after reading
Old States
a
b
Final z1±y1
y2z3
y1z2
Non-Final z2y1
y2z3
y1z2
z3y2
(y3,y1)z4
y1z2
z4+(y3,y1)
(y3 ,y1,y2)z5
(y3,y1)z4
z5+(y3,y1,y2)
(y3,y1 ,y2)z5
(y3,y1)z4
The corresponding transition diagram may be
a
b
a
a
a
z3
z1±
z5+
z4+
b
a
b
b
z2
z
b
42
img
Theory of Automata
(CS402)
Example
Consider the following FA, accepting the language of strings with b as second letter
a,b
b
y2
y3+
y1-
a,b
a
y4
a,b
then the FA corresponding to r* may be determined as under
New States after reading
Old States
a
b
z1±y1
y2z2
y2z2
z2y2
y4z3
(y3,y1)z4
z3y4
y4z3
y4z3
z4+(y3,y1)
(y3 ,y1 ,y2)z5
(y3 ,y1 ,y2)z5
z5+(y3,y1,y2)
(y3,y1 ,y2 ,y4)z6
(y3,y1,y2)z5
z6(y1,y1 ,y2 ,y4)
(y1,y1 ,y2 ,y4)z6
(y1,y1 ,y2 ,y4)z6
a,b
The corresponding transition diagram may be
a
z2
z3
z1±
a,b
b
a,b
z4+
z5+
b
a
a,b
z6+
43