Clausura de Kleene

Clausura de Kleene Concepto: .

Clausura de Kleene. En Lingüística, Matemáticas e Informática y en la Teoría de lenguajes formales se refiere a la operación unitaria de lenguajes que identifica a la concatenación sucesiva de ninguna o más veces de todas y cada una de las cadenas que conforman al lenguaje en cuestión.

Definiciones

Sean los lenguajes formales A y B el producto concatenacional, denotado AxB se define por AxB, al conjunto de todas las cadenas ab donde a es cada cadena de A y b todas las cadenas de B, es decir .

Sea el lenguaje formal L se define a la operación potencia concatenacional n-ésima de L y denotada Lⁿ' según las definiciones:

• L⁰={ε}.
• L¹=L.
• L²=LxL={a₁a₁,a₁a₂} para todas las cadenas a_i y a_j de L.
• Lⁿ=LxL^n-1. (Definición recursiva).

Sea un lenguaje formal L={a,b,c,...}, se llama clausura de Kleene a la operación sobre el lenguaje L y denotado L* a la unión de lenguajes .

También existe la clausura positiva de Kleene que se denota L⁺=L*-L⁰.

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 e₁* el AF equivalente toma la forma: donde T(e₁) es el AFND-V resultante de las expresión e₁

Consecuencias

La clausura de Kleene reviste gran importancia en la teoría de lenguajes formales y la operatoria básica de los mismos, pues permite representar lenguajes obtenidos de concatenaciones recurrentes y otros formalismos de gran uso en todos los tipos de lenguajes de la jerarquía de Chomsky.

Por ejemplo, en los lenguajes regulares es común la representación de versiones más simples como las clasuras en las expresiones regulares, permitiendo una estrecha interrelación entre los distintos tipos de formas de reconocimiento y representación de lenguajes regulares, en autómatas finitos y gramáticas regulares.

Similar ocurre en reducciones de LLC como son los LL(k) y los LR(k).

Véase también

• Jerarquía de Chomsky.
• Lenguaje formal.
• Lenguaje regular.
• Expresión regular.
• Autómata finito.
• Lenguaje libre de contexto.

Fuentes

1. Tanembaum, A. Compilers: Principles, Tecniques, and Tools. Tomo 1. ACM Press. 5ta Edición.
2. Conferencias de la Asignatura "Compilación 1" del Departamento de Ciencias de la Computación de la Universidad de Oriente de la Universidad de Oriente. Santiago de Cuba, 2000.
3. Clausura de Kleene en Wikipedia. Consultado el 5 de diciembre de 2013.
4. Acevedo Martínez, Liesner; Osorio Ramírez, Karel. Manual de apoyo a la docencia. Técnicas de Compilación: Manual Práctico para estudiantes de Informática. Libro electrónico en PDF. UCI. La Habana, 2011.