Închidere Kleene

În logica matematică și în informatică, închiderea Kleene (engleză: Kleene star) este o operație unară pe mulțimi de șiruri de simboluri sau caractere. Aplicarea operației pe o mulțime V se scrie ca V*. Operatorul este folosit pe scară largă în expresiile regulate, context în care a fost introdus de Stephen Kleene pentru a caracteriza anumite automate.

• Dacă V este o mulțime de șiruri, V* este definit ca cel mai mic superset al lui V care conține ε (șirul vid) și este închis în raport cu operația de concatenare. Această mulțime poate fi descrisă ca mulțimea șirurilor ce pot fi realizate prin concatenarea a 0 sau mai multe șiruri din V.
• În particular, dacă V este formată doar din caractere, V* este mulțimea tuturor șirurilor peste simbolurile din V, incluzând șirul vid.

Exemple

Exemplu de închidere Kleene aplicată unei mulțimi de șiruri:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Exemplu de aplicare asupra unei mulțimi de caractere:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", ...}

Generalizare

Închiderea Kleene este adesea generalizat pentru orice monoid $(M,\cdot )$, adică o mulțime M și o operație '$\cdot$' pe elemente din M cu proprietățile

• (închidere) $\forall a,b\in M,a\cdot b\in M$
• (asociativitate) $\forall a,b,c\in M,(a\cdot b)\cdot c=a\cdot (b\cdot c)$
• (identitate) $\exists \varepsilon \in M,\forall a\in M,a\cdot \varepsilon =\varepsilon \cdot a=a$

Dacă V este o submulțime a lui M, atunci V* se definește ca cel mai mic superset al lui V care conține ε (șirul vid) și este închis sub operația "$\cdot$". Atunci V* însuși este un monoid, numit monoidul generat de V. Aceasta este o generalizare a închiderii Kleene deoarece mulțimea tuturor șirurilor peste o mulțime de simboluri formează un monoid cu operația de concatenare a șirurilor.

Alte legăruri

• Lema de pompare