Klinijevo zatvorenje

U matematičkoj logici i računarstvu, Klinijevo zatvorenje (ili Klinijeva zvezda) je unarna operacija, na skupovima niski ili na skupovima simbola ili karaktera. Primena Klinijevog zatvorenja na skup V se zapisuje kao V*. Ovaj operator je u širokoj upotrebi u regularnim izrazima, što je i kontekst u kome ga je uveo Stiven Klini da karakteriše određene automate.

Ako je V skup niski, onda se V* definiše kao najmanji nadskup od V, koji sadrži ε (praznu nisku) i zatvoren je u odnosu na konkatenaciju niski. Ovaj skup se takođe može opisati kao skup niski koje se mogu dobiti dopisivanjem nula ili više niski iz V.
Ako je V skup simbola ili karaktera, onda je V* skup svih niski nad simbolima V, uključujući i praznu nisku.

Definicija i notacija[uredi | uredi izvor]

Dat je skup

V_{0}=\{\epsilon \}\,

rekurzivno definišemo skup

V_{i+1}=\{wv:w\in V_{i}{\mbox{, }}v\in V\}\,

gde

i\geq 0\,.

Ako je $V$ formalni jezik, onda $i$ -ti stepen skupa $V$ predstavlja konkatenaciju skupa $V$ sa samim sobom $i$ puta. To jest, $V_{i}$ se može razumeti kao skup svih niski dužine $i$ , dobijenih od simbola iz $V$ .

Definicija Klinijeve zvezde nad $V$ je $V^{*}=\bigcup _{i=0}^{\infty }V_{i}=\left\{\epsilon \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots$

To jest, to je kolekcija svih mogućih niski konačne dužine, generisanih od simbola iz $V$ .

U nekim istraživanjima formalnih jezika, koristi se varijacije operacije Klinijeve zvezde, operacija Klinijev plus. Klinijev plus isključuje $V_{0}$ iz gornje unije. Drugim rečima, Klinijev plus nad $V$ je $V^{+}=\bigcup _{i=1}^{\infty }V_{i}=V_{1}\cup V_{2}\cup V_{3}\cup \ldots$