Question: Write Short Notes on Kleene Closure
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014

 modified 3.3 years ago  • written 3.3 years ago by Pooja Joshi • 740
0

Let S be a set.

The Kleene closure of S, denoted S∗, is the set of all finite sequences in S.

Examples:

Example of Kleene star applied to set of strings:

{"ab","c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

Example of Kleene star applied to set of characters:

{"a", "b", "c"}* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

Example of Kleene star applied to the empty set:

∅* = {ε}.

Example of Kleene plus applied to the empty set:

∅+ = ∅∅* = { } = ∅,

where concatenation is an associative and non commutative product, sharing these properties with the Cartesian product of sets.

Example of Kleene plus and Kleene star applied to the singleton set containing the empty string:

If V = {ε}, then also $V_i$ = {ε} for each i, hence V* = $V^+$ = {ε}.