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

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

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

Дефиниција и нотација

Дат је скуп

$V_0=\{ϵ\}$

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

$V_{i+1}=\{wv:w\in V_i\text{, }v\in V\}$ где $i\ge 0.$

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

Дефиниција Клинијеве звезде над $V$ је $V^{*}=\bigcup _{i=0}^{\mathrm{\infty }}{V}_i=\left\{ϵ\right\}\cup V_1\cup V_2\cup V_3\cup \dots$

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

У неким истраживањима формалних језика, користи се варијације операције Клинијеве звезде, операција Клинијев плус. Клинијев плус искључује $V_0$ из горње уније. Другим речима, Клинијев плус над $V$ је $V^{+}=\bigcup _{i=1}^{\mathrm{\infty }}{V}_i=V_1\cup V_2\cup V_3\cup \dots$

Примери

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

-{ {"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}-, такву да важи

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

Види још

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