Question: Write Short Notes on Kleene Closure
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2014

ADD COMMENTlink
modified 3.0 years ago  • written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
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^+$ = {ε}.

ADD COMMENTlink
written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.