WikiSysop: Bot: Automatski unos stranica

2021-08-20T00:55:40Z

Bot: Automatski unos stranica

Nova stranica

U [[matematička logika|matematičkoj logici]] i [[računarstvo|računarstvu]], '''Kleeneov operator''' ([[engleski jezik|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 [[regularni izraz|regularnim izrazima]], što je uostalom i kontekst u kojem je uveden od strane [[Stephen Kleene|Stephena Kleenea]] prilikom opisivanja značajki pojedinih [[konačni automat|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 ==

<math>V^* = \bigcup_{k\ge 0} V^k = \left \{\varepsilon \right\} \cup V \cup V^2 \cup V^3 \cup \ldots</math>
* <math>k</math>-ta potencija skupa <math>V</math> je skraćeni zapis Kartezijevog produkta skupa <math>V</math> sa samim sobom, <math>k-1</math> puta - npr. <math>V^3 = V \times V \times V</math>.

* 1 označava neutralni element <math>\left\{\varepsilon \right\}</math>, skup koji sadrži samo prazni niz.
* 0 označava prazni skup <math>\varnothing</math>.

== Primjeri ==

Primjer 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 ==

Kleeneov operator je često poopćen na bilo koji monoid (''M'', <math>\circ</math>), tj. skup ''M'' i binarni operator <math>\circ</math> na ''M'' za koje vrijedi
* (Zatvorenost) <math>\forall a,b \in M:~ a \circ b \in M</math>
* (Asocijativnost) <math>\forall a,b,c \in M:~ (a \circ b) \circ c = a \circ (b \circ c)</math>
* (Neutralni element) <math>\exists \epsilon \in M:~ \forall a \in M:~ a \circ \epsilon = a = \epsilon \circ a</math>
Ako je ''V'' podskup skupa ''M'', tada je ''V''* definiran 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ćenje prethodno diskutiranog Kleeneovog operatora jer skup svih nizova znakova nad nekim skupom znakova oblikuje monoid (sa nadovezivanjem nizova znakova kao operacijom).
[[Kategorija:Formalni jezici]]

Kleeneov operator - Povijest promjena

WikiSysop: Bot: Automatski unos stranica