Clausura de Kleene

En lògica matemàtica i en informàtica, la clausura de Kleene (també anomenada estel Kleene) és una operació unària que s'aplica sobre un conjunt de cadenes de caràcters o un conjunt de símbols o caràcters (alfabet), i representa el conjunt de les cadenes que es poden formar prenent qualsevol nombre de cadenes del conjunt inicial, possiblement amb repeticions, i concatenant-les entre si.

L'aplicació de la clausura de Kleene a un conjunt V es denota com a V*. És molt usada en expressions regulars i va ser introduïda en aquest context per Stephen Kleene (1909-1994) per caracteritzar un cert autòmat.

Definició i notacióModifica

Donat

 

es defineix recursivamente

  on  

Si   és un llenguatge formal, aleshores la  -ésima potència de   és l'abreviatura de la concatenació de   amb si mateix   vegades. Això és,   pot entendre's com el conjunt de tots els strings de longitud  , format a partir dels símbols en  .


La definició de clausura Kleene en   és  

És a dir, és la recopilació de tots els possibles strings de longitud finita generats a partir dels símbols en  .

En alguns estudis de llenguatge formal, usen Kleene plus que és una variació de l'operació clausura de Kleene. Kleene plus omet el terme   en la unió. En altres paraules, Kleene plus en   és  

ExemplesModifica

Exemple de clausura de Kleene aplicada a un caràcter:

{"a"}* = {ε, "a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa",...}

Exemple de clausura de Kleene aplicada a un conjunt de cadenes:

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

Exemple de clausura de Kleene aplicada a un conjunt de caràcters:

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