0
Write Short Notes on Kleene Closure

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014

0
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^+$ = {ε}.

0
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more