Clausura de Kleene

En lógica matemática y en ciencias de la computación, la clausura de Kleene (también llamada estrella Kleene o cierre estrella) es una operación unaria que se aplica sobre un conjunto de cadenas de caracteres o un conjunto de símbolos o caracteres (alfabeto), y representa el conjunto de las cadenas que se pueden formar tomando cualquier número de cadenas del conjunto inicial, posiblemente con repeticiones, y concatenándolas entre sí.

La aplicación de la clausura de Kleene a un conjunto V se denota como V*. Es muy usada en expresiones regulares y fue introducida en este contexto por Stephen Kleene (1909-1994) para caracterizar un cierto autómata.

Definición y notaciónEditar

Dado

 

se define recursivamente

  donde  

Si   es un lenguaje formal, entonces la  -ésima potencia de   es la abreviatura de la concatenación de   consigo mismo   veces. Esto es,   puede entenderse como el conjunto de todos los strings de longitud  , formado a partir de los símbolos en  .

La definición de Kleene estrella en   es  

Es decir, es la recopilación de todas los posibles cadenas de longitud finita generados a partir de los símbolos en  .

En algunos estudios de Lenguaje formal, usan Kleene plus que es una variación de la operación Kleene estrella. Kleene plus omite el término   en la unión. En otras palabras, Kleene plus en   es  

EjemplosEditar

Ejemplo de clausura de Kleene aplicada a un carácter:

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

Ejemplo de clausura de Kleene aplicada a un conjunto de cadenas:

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

Ejemplo de clausura de Kleene aplicada a un conjunto de caracteres:

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

ReferenciasEditar