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

Из Википедије, слободне енциклопедије

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

Види још[уреди]