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.

TALF 1: Lenguajes y Gramáticas Formales

Hola amigos, Bienvenidos a la primera entrada de este blog, que espero me ayude a estudiar :D

Comenzamos el tema1 de TALF (Teoría de Autómatas y Lenguajes Formales)

Este tema tiene muchos conceptos, que puede ser útil conocer para el Test, recordamos algunos:

Palabras

• Vⁿ es el conjunto de todas las palabras de longitud n, que se pueden formar utilizando el alfabeto V.
• V⁰ es el conjunto que solo tiene la palabra vacía, λ , como elemento.
• De esta manera, el conjunto de todas las palabras de cualquier longitud que se pueden formar usando el alfabeto V es:
• V^* = U Vⁿ
• V⁺ = lo mismo pero sin contener la palabra vacía λ.

• Las palabras se pueden concatenar, y esta operación tiene 3 propiedades (que le conceden el honor de llamarla un monoide y encima libre, por que cada palabra se prepresenta de forma única) :
  
• Es una operación CERRADA: para cualesquiera 2 palabras de un alfabeto, si las concatenas, el resultado es otra palabra de ese alfabeto.
• Es ASOCIATIVA: x(yz) = (xy)z.
• Tiene ELEMENTO NEUTRO que es λ: λx = xλ = x
• Como todos sabemos de toda la vida, los monoides libres cumplen la ley de cancelación por la izquierda y derecha:
• (xy=xz) => (y=z)
• Las palabras pueden tener prefijos y sufijos (qué novedad ¬¬) y estos son PROPIOS si son distintos a la propia palabra, osea si un prefijo es toda la palabra, no es propio.
• A las palabras se les puede aplicar la operación potencia, que es concatenarla consigo misma las veces que sea. (Una palabra elevada a 0 es λ).

Lenguajes

Hablemos ahora de nuestros amigos los Lenguajes, que están definidos sobre un determinado alfabeto V y sonsisten en todas las posibles palabras, o sea: V*

• Podemos definir un lenguaje así : L = {w ∈ V* | w cumple una propiedad P}
• La unión de 2 lenguajes es todas las palabras de uno mas todas las palabras del otro (Como era de esperar)
• Resulta que los Lenguajes son monoides abelianos (más adelante estudiaremos los monoides Pepa-nios), por que cumplen la propiedad conmutativa, además de las otras 3 que hemos visto antes).
• Los lenguajes tambien se pueden concatenar (palabras del lenguaje 1 concatenadas con palabras del lenguaje 2). La concatenación de lenguajes es distributiva respecto la unión: A(B U C) = (AB) U (AC).
• La potencia de lenguajes es concatenarlos consigo mismos, al igual q las palabras (L elevado a 0 es {λ} ).
• El cierre positivo de un Lenguaje, L⁺ es todas las palabras que se obtienen concatenando palabras del lenguaje, excluyendo a la palabra vacía, y el cierre, a secas es todas las palabras y ademas la palabra vacía.

Gramáticas Formales

Ahora le toca a las Gramáticas Formales, que son mecanismos generadores de lenguajes, especifican cómo construir palabras de un lenguaje determinado.

• Las gramáticas están formadas por 4 elementos: (variables, símbolos terminales, variable inicial y un conjunto de reglas de producción, que son de la forma α => β).
• α deriva directamente en β, si β se puede obtener sustituyendo alguna variable de α por la parte derecha (weno vale, quedeará mas claro cuando hagas ejercicios).
• α deriva en β, si β se puede obtener como resultado de varias derivaciones directas (O tambien si α = β).
• Una forma sentencial de una gramática, es cualquier palabra (que puede ser variables y/o terminales) que sea resultado de una derivación . Y si la palabra esa está formada solo por TERMINALES, entonces es una SENTENCIA (que son las que forman el lenguaje).
• Dos Gramáticas son equivalentes si generan el mismo lenguaje.

Notación Buenafuente (BNF)

Las variables se pone entre <ángulos> y las flechas de derivación con ::= .La notacion Buenafuente extendida añade [cosa opcional] y {cosa que se repite}

Jerarquía de Chomsky

De más a menos general:

• L0: Estructura de frase: las producciones son de cualquier forma!
• L1: Sensibles al contexto (en la parte izq. solo hay variables)
• L2: Libres del contexto (pueden aparecer terminales que acompañen a las variables)
• L3: Regulares, pueden ser
• Lineales por la derecha: A -> bC, A-> b, A-> λ //La variabla aparece a la derecha
  
• Lineales por la izquieda: A -> Cb, A-> b, A-> λ //La variabla aparece a la izquierda

L0 incluye aL1, que incluye a L2, que incluye a L3

Y hasta aquí lo más destacado del tema1, nos vemos en el tema 2! :D