Пређи на садржај

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

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

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

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