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

У математичкој логици и рачунарству, Клинијево затворење (или Клинијева звезда) је унарна операција, на скуповима ниски или на скуповима симбола или карактера. Примена Клинијевог затворења на скуп 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 \ge 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$

Види још

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