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
- 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:
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
Y hasta aquí lo más destacado del tema1, nos vemos en el tema 2! :D
No hay comentarios:
Publicar un comentario