Клинијево затворење

У математичкој логици и рачунарству, Клинијево затворење (или Клинијева звезда) је унарна операција, на скуповима ниски или на скуповима симбола или карактера. Примена Клинијевог затворења на скуп V се записује као V*. Овај оператор је у широкој употреби у регуларним изразима, што је и контекст у коме га је увео Стивен Клини да карактерише одређене аутомате.

Ако је V скуп ниски, онда се V* дефинише као најмањи надскуп од V, који садржи ε (празну ниску) и затворен је у односу на конкатенацију ниски. Овај скуп се такође може описати као скуп ниски које се могу добити дописивањем нула или више ниски из V.
Ако је V скуп симбола или карактера, онда је V* скуп свих ниски над симболима V, укључујући и празну ниску.

Дефиниција и нотација[уреди | уреди извор]

Дат је скуп

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

рекурзивно дефинишемо скуп

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

где

i\geq 0\,.

Ако је $V$ формални језик, онда $i$ -ти степен скупа $V$ представља конкатенацију скупа $V$ са самим собом $i$ пута. То јест, $V_{i}$ се може разумети као скуп свих ниски дужине $i$ , добијених од симбола из $V$ .

Дефиниција Клинијеве звезде над $V$ је $V^{*}=\bigcup _{i=0}^{\infty }V_{i}=\left\{\epsilon \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots$

То јест, то је колекција свих могућих ниски коначне дужине, генерисаних од симбола из $V$ .

У неким истраживањима формалних језика, користи се варијације операције Клинијеве звезде, операција Клинијев плус. Клинијев плус искључује $V_{0}$ из горње уније. Другим речима, Клинијев плус над $V$ је $V^{+}=\bigcup _{i=1}^{\infty }V_{i}=V_{1}\cup V_{2}\cup V_{3}\cup \ldots$