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.

1. 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.
2. 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

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$

Primeri

Primer Klinijevog zatvorenja skupa niski:

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

Primer Klinijevog zatvorenja skupa karaktera:

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

Uopštenje

Klinijeva zvezda se često generalizuje za bilo koji monoid (M, $\circ$), to jest, skup M i binarnu operaciju $\circ$ nad M, takvu da važi

• (zatvorenje) $\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)$
• (neutral) $\exists e\in M:~\forall a\in M:~a\circ e=e\circ a=a$

Vidi još

• Klinijeva algebra
• Proširena Bakus-Naurova forma
• Regularni izrazi