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

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

1. Ако је V скуп ниски, онда се V* дефинише као најмањи надскуп од V, који садржи ε (празну ниску) и затворен је у односу на конкатенацију ниски. Овај скуп се такође може описати као скуп ниски које се могу добити дописивањем нула или више ниски из V.
2. Ако је 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$

Примери

Пример Клинијевог затворења скупа ниски:

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

Пример Клинијевог затворења скупа карактера:

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

Уопштење

Клинијева звезда се често генерализује за било који моноид (M, $\circ$), то јест, скуп M и бинарну операцију $\circ$ над M, такву да важи

• (затворење) $\forall a,b\in M:~a\circ b\in M$
• (асоцијативност) $\forall a,b,c\in M:~(a\circ b)\circ c=a\circ (b\circ c)$
• (неутрал) $\exists e\in M:~\forall a\in M:~a\circ e=e\circ a=a$

Види још

• Клинијева алгебра
• Проширена Бакус-Наурова форма
• Регуларни изрази