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:
- Automata Theory and Formal Languages
- Recursive Definition of a Language
- Finite Representation of Language