Kleene hvězda

Kleene hvězda (nebo Kleene uzavření) je operace používaná v pravidelných výrazech a operuje jeden na souborech řetězců nebo na souborech symbolů nebo charakterech. Aplikace Kleene hvězdy k souboru V je psán jak V*.

Jestliže V je soubor řetězců pak V* je definován jako nejmenší superset V to obsahuje a epsilon; (prázdný řetězec) a je zavřen pod řetězcovou zřetězovací operací. Tento soubor může také být popisován jako soubor řetězců, které mohou být vyrobeny concatenating nulou nebo více řetězců od V.
Jestliže V je soubor symbolů nebo charakterů pak V* je soubor všech řetězce přes symboly v V, včetně prázdného řetězce.

Příklad Kleene hvězdy platil o souboru řetězců:

{“ab”, “c #lquote} * = {a epsilon;, “ab”, “c”, “abab”, “abc”, “taxi”, “cc”, “ababab”, “ababc”, “abcab”, “abcc”, “cabab”, “cabc”, “ccab”, “ccc”,...}

Příklad Kleene hvězdy platil o souboru charakterů:

{' ', ' b ', ' c '} * = {a epsilon;, “#rquote, “b”, “c”, “aa”, “ab”, “ac”, “ba”, “bb”, “bc”,...}

Kleene hvězda je často celková pro nějaký monoid (M,.), to je, soubor M a binární operace '. ' na M takový to

(uzavření) pro všechny a b v M, . b v M
(associativity) pro všechny , b a c v M, ( . b). c = . (b . c)
(identita) tam je e v M takový to pro všechny , . e = e . =

Jestliže V je podmnožina M, pak V* je definován jak nejmenší superset V to obsahuje a epsilon; (prázdný řetězec) a je zavřen pod operací. V* je pak sám monoid, a je volán monoid vytvořený V. Toto je zevšeobecňování Kleene hvězdy diskutovalo nahoře od té doby, co soubor všech řetězců přes nějaký soubor symbolů tvoří monoid (s zřetězením řetězce jako binární operace).

Kleene hvězda je jmenována po Stephen Kleene (1909-1994) kdo představil to když popisuje jisté automaty (viz pravidelný výraz).

Viz též: