Kleene Closure

Given an alphabet Σ the Kleene closure of Σ is a language given by

                Σ* = Σ0 ∪ Σ1 ∪ Σ2……….

For example,

1.         if Σ = {X}, then
            Σ* = {ε, x, xx, …..}
2.        if Σ = {0, 1}, then
          Σ* = {ε,0, 1, 00, 01, 10, 11, ……}

If L is language, then L* is the set of all finite strings formed by concatenating Words from L. Any word can be used any number of times including zero time. ε is a member of L*.

Example : If L = {aa,b} then

In this example, we should assume ‘aa’ is first character and ‘b’ is second character.

                 L* = {ε, b, aa, bb, bbb, baa, aab, aabb, bbaa, ……}

L* always contains an epsilon.

It may be noted that a always appears in pair.

If Kleene closure Σ = Ф (an empty language)

then                Σ* = {ε}

L+ is known as the positive closure of L. L+ is the set of all finite strings formed by concatenation words from L. Any word can be used one or more times.

Example : If L = {aa, b} then

                 L+ = {b, aa, bb, bbb, baa, aab, ……}

L+ always not contains an epsilon.

Question 1.

Let L be a language. It is clear from the definition that L+ ⊆ L*. Under what circumstances are they equal ?

Solution :

                 L* always contains an epsilon.

                 L+ always not contains an epsilon.

                 Thus, the only difference between L+ and L* is that L+ may or may not contain an epsilon but L* will always contain an epsilon. (epsilon mean empty )

If L itself contains an epsilon the there will be no difference between L+ and L* .

Recommended:

  1. Automata Theory and Formal Languages
  2. Recursive Definition of a Language
  3. Finite Representation of Language

Leave a Comment

Your email address will not be published. Required fields are marked *

x