Clausura de Kleene

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 | modifica el codi]

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


Exemples[modifica | modifica el codi]

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",...}