Vés al contingut

Clausura de Kleene

De la Viquipèdia, l'enciclopèdia lliure

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

Exemples

[modifica]

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