Kleene Closure

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

                Σ^* = Σ⁰ ∪ Σ¹ ∪ Σ²……….

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