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ó

Donat

${\displaystyle V_{0}=\{\lambda \}\,}$

es defineix recursivamente

${\displaystyle V_{i+1}=\{wv:w\in V_{i}{\mbox{ and }}v\in V\}\,}$ on ${\displaystyle i\geq 0\,.}$

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

La definició de clausura Kleene en ${\displaystyle V}$ és ${\displaystyle V^{*}=\bigcup _{i\in \mathbb {N} }V_{i}=\left\{\lambda \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

És a dir, és la recopilació de tots els possibles strings de longitud finita generats a partir dels símbols en ${\displaystyle V}$.

En alguns estudis de llenguatge formal, usen Kleene plus que és una variació de l'operació clausura de Kleene. Kleene plus omet el terme ${\displaystyle V_{0}}$ en la unió. En altres paraules, Kleene plus en ${\displaystyle V}$ és ${\displaystyle V^{+}=\bigcup _{i\in \mathbb {N} ^{\star }}V_{i}=V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

Exemples

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