Kleene star

De la Wikipedia, enciclopedia liberă

În logica matematică şi în informatică, Kleene star (sau închiderea Kleene) este o operaţie unară, fie pe mulţimi de şiruri de caractere fie pe mulţimi de simboluri sau caractere. Aplicarea operaţiei Kleene star 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.

  1. 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.
  2. Dacă V este o mulţime de simboluri sau caractere, V* este mulţimea tuturor şirurilor peste simbolurile din V, incluzând şirul vid.

[modifică] Exemple

Exemplu de Kleene star aplicat unei mulţimi de şiruri:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Exemplu de Kleene star aplicat unei mulţimi de caractere:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

[modifică] Generalizare

Kleene star este adesea generalizat pentru orice monoid (M, .), adică o mulţime M şi o operaţie '.' asupra lui M cu proprietăţile

  • (închidere) pentru orice a şi b din M, a . b e din M
  • (asociativitate) pentru orice a, b şi c din M, (a . b) . c = a . (b . c)
  • (identitate) există un ε din M astfel încât pentru orice a, a . ε = ε . 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 "." - V* este atunci el însuşi un monoid, numit monoidul generat de V. Aceasta este o generalizare a lui Kleene star deoarece mulţimea tuturor şirurilor peste o mulţime de simboluri formează un monoid cu operaţia de concatenare a şirurilor.

[modifică] Alte legăruri


Notă: Articolul este tradus şi adaptat după Kleene star (în limba engleză)