Clausura de Kleene

En lógica matemática y en ciencias de la computación, la clausura de Kleene (también llamada estrella de 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

Dado

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

se define recursivamente

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

Si ${\displaystyle V}$ es un lenguaje formal, entonces la ${\displaystyle i}$-ésima potencia de ${\displaystyle V}$ es la abreviatura de la concatenación de ${\displaystyle V}$ consigo mismo ${\displaystyle i}$ veces. Esto es, ${\displaystyle V_{i}}$ puede entenderse como el conjunto de todas las cadenas de longitud ${\displaystyle i}$, formado a partir de los símbolos en ${\displaystyle V}$.

La definición de Kleene estrella en ${\displaystyle V}$ es ${\displaystyle V^{*}=\bigcup _{i\in \mathbb {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 ${\displaystyle 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 ${\displaystyle V_{0}}$ en la unión. En otras palabras, Kleene plus en ${\displaystyle V}$ es ${\displaystyle V^{+}=\bigcup _{i\in \mathbb {N} ^{\star }}V_{i}=V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

Ejemplos

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

${\displaystyle \{a\}^{*}=\{\lambda ,a,aa,aaa,aaaa,aaaaa,aaaaaa,\dots \}}$

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

${\displaystyle \{ab,c\}^{*}=\{\lambda ,ab,c,abab,abc,cab,cc,ababab,ababc,abcab,abcc,cabab,cabc,ccab,ccc,\dots \}}$

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

${\displaystyle \{a,b,c\}^{*}=\{\lambda ,a,b,c,aa,ab,ac,ba,bb,bc,\dots \}}$

Referencias

• John E. Hopcroft y Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 1a edición. Addison-Wesley Publishing Company, 1979.