Unidad 1 cerradura de kleene y los productos

Clausura de KleeneEn lógica matemática y en ciencias de la computación, la clausura de Kleene (también llamada estrella Kleene o cierre estrella) es unaoperació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




se define recursivamente

donde




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, Vipuede 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



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érminoV0 en la unión. En otras palabras, Kleene plus en V es





CERRADURA POSITIVA A+:



Se define de la siguiente manera A+ = U∞n=1 An es decir, indica que el carácter al que sigue el signo deberá aparecer al menos una vez.

Ejemplos

• Sea el lenguaje L={a}, L*={ε,a,aa,aaa,aaaa,...}.
• Sea un B={0,1} lenguaje formal, B*={ε,0,1,00,01,10,11,000,001,010,011,...}.
• Sea la expresión regular e1* el AF equivalente toma la forma: donde T(e1) es el AFND-V resultante de las expresión e1