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

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

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

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

уреди

Дат је скуп

 

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

  где  

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

Дефиниција Клинијеве звезде над   је  

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

У неким истраживањима формалних језика, користи се варијације операције Клинијеве звезде, операција Клинијев плус. Клинијев плус искључује   из горње уније. Другим речима, Клинијев плус над   је  

Примери

уреди

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

{"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,  ), то јест, скуп M и бинарну операцију   над M, такву да важи

  • (затворење)  
  • (асоцијативност)  
  • (неутрал)  

Види још

уреди