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 Ln' según las definiciones:

  • L0={ε}.
  • L1=L.
  • L2=LxL={a1a1,a1a2} para todas las cadenas ai y aj de L.
  • Ln=LxLn-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*-L0.

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

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

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.
This article is issued from Ecured. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.