Lema de Arden

Documentos: Presentacion power point para exposicion + Trabajo escrito + Preguntas importantes.

DEscargar aqui: Archivos aqui

ECUACIONES LINEALES - LEMA DE ARDEN

Las ecuaciones lineales en los lenguajes regulares juegan un papel muy importante. Estas nos posibilitaran probar que las palabras generadas por una gramática regular forman un lenguaje dado por una expresión regular.

Definición
El lema Arden, este permite resolver ecuaciones lineales entre lenguajes y que ofrece un método alternativo para encontrar expresiones regulares correspondientes a autómatas finitos. Este método a pesar de requerir un tiempo de proceso del mismo orden que el algoritmo de McNaughton- Yamada, es preferible a este cuando se tienen que hacer los cálculos a mano.

Definición:
Una ecuación lineal por la derecha sobre un alfabeto Ʃ es una expresión de la forma:
X = AX + B
1) El lenguaje BA* es solución de la ecuación X = XA + B es una ecuación de expresiones regulares
2) Cualquier solución de la ecuación X = XA + B contiene el lenguaje BA*
3) Si λ    entonces entonces entonces BA* es la única soluciónes la única solución es la única solución es la única solución es la única solución


Los lenguajes regulares se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes, como por ejemplo en el lenguaje L1 siguiente: L1 = {ab, abab, ababab, abababab,. . .} En este ejemplo se aprecia que las palabras de L1 son simplemente repeticiones de “ab” cualquier número de veces. Aquí la “regularidad” consiste en que las palabras contienen “ab” algún número de veces.