Î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 , adică o mulțime M și o operație '' pe elemente din M cu proprietățile

  • (închidere)
  • (asociativitate)
  • (identitate)

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 "". 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ă]