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
x1∫z2
(x2,x1)∫ z3
Non-final z2∫x1
x1∫z2
(x2,x1)∫z3
z3+∫(x2,x1)
x1∫z2
(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
y2∫z3
y1∫ z2
Non-Final z2∫y1
y2∫z3
y1∫ z2
z3∫y2
(y3,y1)∫z4
y1∫ z2
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
y2∫z2
y2∫ z2
z2∫y2
y4∫z3
(y3,y1)∫ z4
z3∫y4
y4∫z3
y4∫z3
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
Table of Contents:
  1. What does automata mean, Introduction to languages
  2. Kleene Star Closure, Recursive definition of languages
  3. Regular Expression, Recursive definition of Regular Expression
  4. Equivalent Regular Expressions
  5. Finite Automaton
  6. Equivalent FAs
  7. FA corresponding to finite languages
  8. Examples of TGs: accepting all strings
  9. Generalized Transition Graphs
  10. Nondeterminism, Kleene’s Theorem
  11. Proof(Kleene’s Theorem Part II)
  12. Kleene’s Theorem Part III
  13. Concatenation of FAs
  14. Closure of an FA
  15. Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
  16. NFA with Null String
  17. NFA and Kleene’s Theorem
  18. NFA corresponding to Concatenation of FAs
  19. Distinguishable strings and Indistinguishable strings
  20. Finite Automaton with output, Moore machine
  21. Mealy machine
  22. Equivalent machines
  23. Mealy machines in terms of sequential circuit
  24. Regular languages, Complement of a language
  25. Nonregular languages
  26. Pumping Lemma
  27. Pumping Lemma version II
  28. Pseudo theorem
  29. Decidability
  30. finiteness of a language
  31. Context Free Grammar (CFG), CFG terminologies
  32. Trees
  33. Polish Notation (o-o-o)
  34. Total language tree, Regular Grammar
  35. Null Production
  36. Chomsky Normal Form (CNF)
  37. A new format for FAs
  38. Nondeterministic PDA
  39. PDA corresponding to CFG
  40. Conversion form of PDA
  41. Conversion Form, Joints of the machine
  42. Row language, Nonterminals
  43. Non-Context-Free language, Pumping lemma for CFLs
  44. Decidablity, Parsing Techniques
  45. Turing machine