Kleene Closure (*)  In TOC

Kleene Closure, also known as the Kleene Star and denoted by the symbol"*", is a fundamental concept in the Theory of Computation (TOC). The Kleene Closure of Σ, denoted by Σ*, represents the set of all possible strings (including the empty string) formed using symbols from an alphabet Σ.

Important: Σ* contains an infinite number of strings, but each string has a finite length.

The following diagram explains Mathematical Notation of Kleene Closure in detail 

Where:

• Σ^⁰ = {ε}

  • Set of strings of length 0 (only the empty string ε).

• Σ^¹ = { w ∈ Σ | |w| = 1 }

  • Set of all strings of length 1 using symbols from Σ.

• Σ^² = { w ∈ Σ | |w| = 2 }

  • Set of all strings of length 2 (e.g., if Σ = {a, b}, then Σ^² = {aa, ab, ba, bb}).

               ………………………………..

• Σ^ⁿ = { w ∈ Σ | |w| = n }

  • Set of all strings of length n, created by concatenating n symbols from Σ.

Let’s explain the above mathematical notation through various lengths of  input alphabets (Σ).

Kleene Closure Using Various Lengths of “Σ”

 The following are various examples of Kleene Closure over input values of input alphabets (Σ).

Example 01: Σ = {a, b}

Important: Σ* = Set of all infinite number of strings, each string has finite length (including length 0), over the alphabet {a,b}

Example 02: Σ = {a,b,c}

When the length of input symbols is Σ  = 3 because it holds “a,b,c”. The total number of strings of length “0” to"n” is given below

Kleene Closure Examples over Symbols of Σ

If Σ contains some alphabet symbols, then Σ* is the set of all strings (including the empty string ε) formed by joining symbols from Σ.

1. Kleene Closure of Empty Set

Even if the set has no strings, the closure includes the empty string ε because zero repetitions are allowed.

• Σ = ∅
• Σ^∗ = {ε}

2. Kleene Closure of Epsilon (ε)

It is a special case when we apply the Kleene closure, meaning we form zero or more concatenations of elements from Σ.

Since Σ = {ε}, any number of ε’s concatenated together is still ε. So,

• ε · ε = ε
• ε · ε · ε = ε
• and so on…

Finally, the result is

Σ* = {ε}

3. Single Character

Applying Kleene closure to a single character yields all strings composed of zero or more repetitions of that character.

• Σ = {a}
• Σ* ={a}* = {ε, a, aa, aaa, aaaa, ...}

4. Set of Characters

The Kleene closure of a set like {a, b} includes all strings of any length (including empty) formed from a and b.

• Σ ={a, b}
• Σ* ={a, b}* = {ε, a, b, aa, ab, ba, bb, aaa, aab, ...}

5. Single String

If a set contains a single string (e.g., "ab"), the closure includes all repetitions of that entire string.

• Σ ={ab}
• Σ* ={ab}* = {ε, ab, abab, ababab, ...}

6. Set of Strings

Kleene closure applied to a set of strings generates all possible concatenations (including empty) of strings from that set.

• Σ ={ab, cd}
• Σ* ={ab, cd}* = {ε, ab, cd, abcd, cdab, ababcd, ...}

Summary Table of Kleene Closure over Symbols of Σ

Kleene Closure (Σ*) with Regex-style Alphabet Examples

1. Σ = {0*1}

Explain: 0*1 means any number of 0’s followed by 1. So, Σ = {0*1}  = { “1”, “01”, “001”, “0001”, … }

Σ* = { ε, 1, 01, 001, 0001, 101, 01001, … }

2. Σ = {10*}

Explain: 10* means the symbol starts with 1 followed by any number of 0’s (including none). So, Σ = {10∗} = {“1”, “10”, “100”, “1000”, “10000”, … }

Σ^∗ = {ε, 1, 10, 100, 1000, 110, 1100, 10010, …}

3. Σ = {0*110*}

The pattern 0*110* means:

• 0* → any number of 0s (including none)

• 11 → exactly two 1s (must be consecutive)

• 0* → any number of 0s (including none)

So, Σ = {“11”, “011”, “0011”, “00011”, “110”, “1100”, “0110”, “00110”, “0001100”, …}

Σ^∗ = {ε, 11, 011, 110, 0011, 1100, 110110, 0110110, 0011011, …

4. Σ = {a*b*c*}

The pattern a*b*c* means:

• a* → zero or more as
• b* → zero or more bs
• c* → zero or more cs

So: Σ = {ε, a, b, c, ab, ac, bc, aab, abb, abc, aabbc, abcc, aaabbbccc, …}

Σ^∗ = {ε,a,b,c,ab,abc,aab,abbc,ababc,abcabc,…}

5. Σ = {a*, b*}

This defines a set of two different regular expressions:

• a*: all strings made of zero or more a’s

• b*: all strings made of zero or more b’s

So, Σ = {a*, b*} is a set containing two separate expressions. It does not mean the union of their languages

Answer is

• a* = {ε, a, aa, aaa, ...}
• b* = {ε, b, bb, bbb, ...}

6. Σ = {a* + b*}

The expression a* + b*defines one regular expression

• a*: all strings made of zero or more a’s

• b*: all strings made of zero or more b’s

{a* + b*} defines the following language

• {a* + b*} = {ε, a, aa, aaa, ..., b, bb, bbb, ... }

Kleene Closure with Restrictions

a. Even-length strings (Σ = {a, b})

L = { w ∈ Σ^∗ ∣ ∣w∣ is even}

 Examples:

b. Palindromes (Σ = {a, b})

L = {w ∈ Σ^∗ ∣ w = w^R} 

Palindromes of length 6:

Positive Closure in TOC

Positive Closure is similar to Kleene Closure except epsilon (ε). It also gives an infinite set of all possible strings of any length, excluding epsilon (ε)  over input values of sigma (Σ). Σ⁺ denotes it. The following is the mathematical notation of Positive Closure.

Σ⁺ = Σ^*– {ε}

The descriptive diagram of Positive Closure in Toc is given below

Examples of Positive Closure

All examples of positive Closure are similar to Kleene closure except epsilon (ε). The following are the various examples of Positive Closure over sigma (Σ) input values.

Example 01

Kleene Closure applied to  an empty set, the result is an empty set

∅⁺ = {}  

Example 02: Σ = {a}

Let Σ = {a}

Then,
Σ⁺ = {a}⁺ = {a, aa, aaa, aaaa, …………….}     // all combination of “a” with any length 

Example 3: Σ = {x, y, z}

Let Σ = {x, y, z}

Then,
Σ^⁺ = { x, y, z, xx, xy, yz, zx, xyz, yzx, … }

Example 4: Σ = {a⁺b}

The pattern a+b means:

• a+ → one or more a’s
• b → exactly one b

So, each symbol in Σ must follow this pattern where at least one a, followed by exactly one b.So,

{a⁺b} = { ab, aab, aaab, … }

Example 5: Σ = {a⁺b⁺}

The pattern a+b+ means

• a+ → one or more as (at least one)
• b+ → one or more bs (at least one)

So, each symbol in Σ must have at least one a, followed by at least one b.So,

{a⁺b⁺} = { ab, ababb, aabbab, aaabbbab, … }

Example 6: Σ = {a*b*c⁺}

This is a regular expression meaning:

• a* → zero or more as
• b* → zero or more bs
• c+ → one or more cs

{a*b*c⁺}  = { c, cc, ac, aac, bc, bbc, abc, aaabbbccc, … }

Example 7: Σ = {a⁺b*c⁺}

This pattern involves:

• a⁺ → one or more as
• b* → zero or more bs
• c⁺ → one or more cs

{a⁺b*c⁺} = {ac, aac, abc, aaabccc, abbccc, abbbbbc, aaabbbbbcc, …}

Example 8: Σ = {a⁺cdb*c⁺}

This is a more specific pattern:

• a+ → one or more as
• c → exactly one c
• d → exactly one d
• b* → zero or more bs
• c+ → one or more cs

{a⁺cdb*c⁺} = {acdc, aacdc, aaacdc, acdbc, acdbbc, aacdbbcc, aaacdbccc, …}

Difference Between Σ^* and Σ⁺

 Σ^* contains the epsilon (ε) string along with other N strings, but Σ⁺ is just like the Σ^* but does not hold the epsilon (ε) string.

We can say

Σ^* = Σ⁺ + Σ⁰ . Where Σ⁰ represent epsilon (ε)

So, Σ^* holds the identity(single) element called Absalon, but Σ⁺ does not have the identity element called epsilon (ε)

Tips about Positive and Kleene Closure in Toc

Σ^* is a Universal Set.

Cardinality: The number of elements in a set, basically |Σ ⁿ |,  is called cardinality. So, |Σ³| has eight cardinality.