- is defined as the smallest Superset of ''V'' that contains ε (the empty string) and is Closed under the String Concatenation Operation . This set can also be described as the set of strings that can be made by concatenating zero or more strings from ''V''.
- is the set of all strings over symbols in ''V'', including the empty string.
Example of Kleene star applied to set of strings:
- = {ε, "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", "aa", "ab", "ac", "ba", "bb", "bc", ...}
The Kleene star is often generalized for any Monoid (''M'', .), that is, a set ''M'' and binary operation '.' on ''M'' such that
- ( Closure ) for all ''a'' and ''b'' in ''M'', ''a'' . ''b'' in ''M''
- ( Associativity ) for all ''a'', ''b'' and ''c'' in ''M'', (''a'' . ''b'') . ''c'' = ''a'' . (''b'' . ''c'')
- ( Identity ) there is an ''ε'' in ''M'' such that for all ''a'', ''a'' . ''ε'' = ''ε'' . ''a'' = ''a''
- is defined as the smallest Superset of ''V'' that contains ε (the empty string) and is closed under the operation. ''V''--- is then itself a monoid, and is called the ''monoid generated by V''. This is a generalization of the Kleene star discussed above since the set of all strings over some set of symbols forms a monoid (with string concatenation as binary operation).
|
