Kleeneov operator

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

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čenja pojedinih automata.

  1. Ako je V skup nizova znakova, tada je V* definisan 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.
  2. 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 | uredi izvor]

V^* = \bigcup_{k\ge 0} V^k = \left \{\varepsilon \right\} \cup V \cup V^2 \cup V^3 \cup \ldots

  • k-ta potencija skupa V je skraćeni zapis Kartezijevog proizvoda skupa V sa samim sobom, k-1 puta - npr. V^3 = V \times V \times V.
  • 1 označava neutralni element \left\{\varepsilon \right\}, skup koji sadrži samo prazni niz.
  • 0 označava prazni skup \varnothing.

Primjeri[uredi | uredi izvor]

Primjer Kleeneovog operatora primjenjenog na skupu nizova znakova:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Primjer Kleeneovog operatora primjenjenog na skupu karaktera:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

Uopšteno[uredi | uredi izvor]

Kleeneov operator je često poopšten na bilo koji monoid (M, \circ), tj. skup M i binarni operator \circ na M za koje vrijedi

  • (Zatvorenost) \forall a,b \in M:~ a \circ b \in M
  • (Asocijativnost) \forall a,b,c \in M:~ (a \circ b) \circ c = a \circ (b \circ c)
  • (Neutralni element) \exists \epsilon \in M:~ \forall a \in M:~ a \circ \epsilon = a = \epsilon \circ a

Ako je V podskup skupa M, tada je V* definisan kao najmanji nadskup skupa V koji sadrži ε (prazni niz) i pritom je zatvoren nad operatorom. V* je tad monoid kojeg zovemo monoid generiran od V. Ovo je poopštenje predhodno diskutiranog Kleeneovog operatora jer skup svih nizova znakova nad nekim skupom znakova oblikuje monoid (sa nadovezivanjem nizova znakova kao operacijom).