4 feb 2009

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
  • Vn es el conjunto de todas las palabras de longitud n, que se pueden formar utilizando el alfabeto V.
  • V0 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 Vn
    • 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

No hay comentarios:

Publicar un comentario