Închidere Kleene
De la Wikipedia, enciclopedia liberă
Î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.
[modifică] 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", ...}
[modifică] Generalizare
Î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.
