Închidere Kleene

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Î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[modificare | modificare sursă]

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[modificare | modificare sursă]

Î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) \exist \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[modificare | modificare sursă]