Î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 , ⋅ ) {\displaystyle (M,\cdot )} , adică o mulțime M și o operație ' ⋅ {\displaystyle \cdot } ' pe elemente din M cu proprietățile

  • (închidere) ∀ a , b ∈ M , a ⋅ b ∈ M {\displaystyle \forall a,b\in M,a\cdot b\in M}
  • (asociativitate) ∀ a , b , c ∈ M , ( a ⋅ b ) ⋅ c = a ⋅ ( b ⋅ c ) {\displaystyle \forall a,b,c\in M,(a\cdot b)\cdot c=a\cdot (b\cdot c)}
  • (identitate) ∃ ε ∈ M , ∀ a ∈ M , a ⋅ ε = ε ⋅ a = a {\displaystyle \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 " ⋅ {\displaystyle \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