Clausura de Kleene

De Wikipedia, la enciclopedia libre
(Redirigido desde «Estrella Kleene»)
Saltar a: navegación, búsqueda

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ón[editar]

Dado

 V_0=\{\lambda\}\,

se define recursivamente

 V_{i+1}=\{wv : w\in V_i \mbox{ and }  v \in V\}\, donde i \ge 0\,.

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

La definición de Kleene estrella en V es  V^*=\bigcup_{i \in \N} V_i = \left \{\lambda \right\} \cup V_1 \cup V_2 \cup V_3 \cup \ldots.

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

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 V_0 en la unión. En otras palabras, Kleene plus en V es  V^+=\bigcup_{i \in \N^{\star}} V_i = V_1 \cup V_2 \cup V_3 \cup \ldots.

Ejemplos[editar]

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

Referencias[editar]