Kleeneov operator
U matematičkoj logici i računarstvu, Kleeneov operator (engl. Kleene star ili Kleene closure) je unarni operator, bilo nad skupom nizova znakova (stringova), bilo nad skupom znakova (simbola) ili karaktera. Primjena Kleeneovog operatora nad skupom V se zapisuje kao V*. Često je korišten u regularnim izrazima, što je uostalom i kontekst u kojem je uveden od strane Stephena Kleenea prilikom opisivanja značajki pojedinih automata.
- Ako je V skup nizova znakova, tada je V* definiran kao najmanji nadskup skupa V koji sadrži
ε (prazni niz) i zatvoren je nad operacijom nadovezivanja (konkatenacije). Ovaj skup također može biti opisan kao skup svih nizova znakova koji mogu biti načinjeni nadovezivanjem nijednog ili više nizova znakova iz V. - Ako je V skup znakova i karaktera, tada je V* skup svih nizova znakova nad znakovima u V, uključujući prazni niz.
Zapis i definicija preko formalizma teorije skupova
uredi
- -ta potencija skupa je skraćeni zapis Kartezijevog produkta skupa sa samim sobom, puta - npr. .
- 1 označava neutralni element , skup koji sadrži samo prazni niz.
- 0 označava prazni skup .
Primjeri
urediPrimjer Kleeneovog operatora primijenjenog na skupu nizova znakova:
- {"ab", "c"}* = {
ε , "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}
Primjer Kleeneovog operatora primijenjenog na skupu karaktera:
- {'a', 'b', 'c'}* = {
ε , "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}
Poopćenje
urediKleeneov operator je često poopćen na bilo koji monoid (M, ), tj. skup M i binarni operator na M za koje vrijedi
- (Zatvorenost)
- (Asocijativnost)
- (Neutralni element)
Ako je V podskup skupa M, tada je V* definiran kao najmanji nadskup skupa V koji sadrži