TALF 2: Expresiones Regulares

Hola amigos!, si el capítulo uno te ha parecido emocionante ... espera a leer este :D, que trata sobre las EERR (en adelante ER), que nos sirven para representar o describir formalmente un lenguaje.

Cómo no, las ER tambien tenian que tener putas propiedades asquerosas que hay que saberse para trabajar con ellas (nota: solo pongo las no muy evidentes):

• α + α = α
• α . ∅ = ∅
• ∅ * = λ //por que ∅ elevado a 0 = λ
• (α*)* = α*
• (α* + β*)* = (α + β)*
• (α* . β*)* = (α + β)*

Por si esto fuera poco, tambien se pueden derivar!! (respecto de un símbolo a, que resulta ser eliminar el prefijo a de todas las palabras de L(α)):

• Da(∅) = ∅
• Da(λ) = ∅
• Da(a) = λ
• Da(v) = ∅
• Derivada de la suma = suma de las derivadas
• Da(α.β) = Da(α) . β + delta(α) . Da( β), donde delta(α) es λ si λ está en el lenguaje descrito por α, y ∅ si λ no está.
• Da(α*) = Da(α) . α*

Ahora haz algún ejemplo de derivación para prácticar las propiedades esas.

Ecuaciones de ER

Una ecuación se llama fundamental si está en la forma x = αx + β

El lema de sequeman(Arden) dice que una solución para una ecuación fundamental es: x = α*β y que es única si λ no está en L(α).

Resolver sistemas de ecuaciones de ER nos será útil más adelante, así que debemos saber cómo ahcerlo:

1. De abajo parriba vamos obteniendo las soluciones (según el lema de sequeman) y sustituyendo en las ecuaciones que haya por encima de la actual.
2. De arriba pabajo sustituimos las soluciones que queden obteniendo así la solución para cada ecuación.

Pasar de ER a GR

1. Llamamos S a la ER y si contiene λ, entonces añadimos S => λ
2. Derivar S respecto de cada símbolo:

• Si la derivada contiene λ, tonces añadimos S => símbolo actual
• Si la derivada es != de vacio y de λ, tonces añadimos S => símbolo actual A, donde A es una nueva variable que nos inventamos y añadimos a la gramática para llamar a la derivada de S.

3. Hacer lo mismo(derivar respecto de cada simbolo) hasta que no queden variables sin derivar. Al obtener una nueva derivada, comprobar si es equivalente a agluna de las ya calculadas antes.

Yasta, así de facil.

Pasar de GR a ER

Formar un sistema de ec. donde cada ecuación corresponde a una variable de la gramática y se forma sumando las reglas de producción, por ej, para A => aA | aC | bB | aB, su ecuación sería A = aA + aC + (b+a)B.