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.
- 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.
- 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ă)