TALF 3: Autómatas Finitos

Paso de AFND a AFD

1. En Q' metemos {q0} y el nuevo estado inicial, q'0 es {q0}
2. Calculamos las transiciones con q'0 y cada símbolo. Los nuevos estados que aparezcan, los metemos en Q' (si son nuevos)
3. Marcamos q'0 para saber que se han calculado sus transiciones.
4. Mientras haya estados no marcados, cogemos uno y para cada símbolo, la func. de transición será:

• los estados a los que se llegue con el símbolo actual, a partir de cada estado que confomre el estado no marcado que acabamos de seleccionar.
• El resutlado lo metemos en Q' como un nuevo estado, y marcamos el estado del que acabamos de calcular sus trans
  

3. Yasta, y el nuevo F' contendrá todos los estados en los que alguno de sus componentes (estados originales del AFND) era final.

Paso de AFN-L a AFND

1. Para cada estado q del AFN-L, calcular la L-clausura, que es todos los estados a los que se puede llegar pasando solamente por arcos con L, partiendo de q.
2. La nueva función de transición:

• Para cada estado q y cada símbolo v, te coges la L-clausura de q que ya deberias tener calculada, y para cada estado de esos, ves a donde se llega con el simbolo v y lo añades a S. Tonces la L-clausura de S, es la nueva funcion de transición para (q, v).

3. El nuevo F' contiene el antiguo F y ademas, si alguno de los estados de L-clausura del estado inicial es final, tonces añadir el estado inicial a la nueva F'.

Obtener la ER a partir de un AF

1. Mu facil, se obtienen las ec. características de cada estado y se resuelve el sistema. La ER es la solución del estado inicial.
   
2. La ec. característica de un estado se construye poniendo

• estado = simbolo1.estado_al_que_lleva + simbolo2.estado_al_que_lleva

Y si el estado es final, tonces añadimos + L

Obtener el AF a partir de una ER

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