În logica matematică și în informatică, închiderea Kleene (în ) 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 .
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.
Închiderea Kleene a unui alfabet Dat fiind un alfabet , se definesc
(mulțimea formată doar din șirul vid),
și se definește recursiv mulțimea
pentru fiecare
unde cu se notează șirul obținut prin adăugarea caracterului după . Aici, se poate înțelege ca fiind mulțimea tuturor șirurilor de lungime exact , cu caractere din .
Definiția închiderii Kleene a lui este
Închiderea Kleene a unui limbaj Dacă se dă un limbaj (orice mulțime finită sau infinită de șiruri), se definește
(limbajul format doar din șirul vid),
și se definește recursiv mulțimea
pentru fiecare
unde cu se notează șirul obținut prin concatenarea lui cu . Aici, poate fi înțeles ca mulțimea tuturor șirurilor ce pot fi obținute prin concatenarea a exact șiruri din , repetițiile fiind permise.
Definiția închiderii Kleene a lui este
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", ...}
Proprietăți
Dacă este orice mulțime finită sau numărabil inifinită de caractere, atunci este o mulțime numărabil infinită. Ca urmare, orice limbaj formal peste un alfabet finit sau numărabil infinit este numărabil, deoarece este o submulțime a mulțimii numărabil infinite . , ceea ce înseamnă că operatul închidere Kleene este un operator unar , întrucât oricare ar fi . , dacă este mulțimea vidă ∅. Pentru versiunea operatorului închidere Kleene pe limbaje, când este fie mulțimea vidă ∅ fie mulțimea formată doar din șirul vid, .
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.
Note
Vezi și Lema de pompare
Categorie:Limbaje formale și automate