Introducción

¿Porqué es importante la teoría de lenguajes formales y autómatas?

Bueno, aclaramos primero un poco las palabras usadas...

¿Qué es un lenguaje formal?

Conocemos lenguajes naturales...

• español, alemán, inglés, chino, árabe...
• cuando nacemos no sabemos ninguno
• se puede aprender cualquier lenguaje (por lo menos si se ha nacido en un entorno adecuado)
• el lenguaje es una secuencia de fonemas o símbolos
  • que forman sílabas, palabras, frases, párrafos, capítulos, novelas, libros, bibliotecas...
  • que tiene una síntaxis (fonética o ortografía)
  • que tiene una gramática (reglas de concatenación y construcción de palabras para formar frases)
  • (que tiene un estilo (forma de unir frases para generar textos))

Lenguajes formales serán meramente símbolos con una gramática formal para agruparlos.

¿Qué es un autómata?

• dispositivos mecánicos o electrónicos o biológicos
  • que en un punto de tiempo están en un estado
  • que dado una razón (por ejemplo una señal de entrada) cambian de estado
• ejemplos son: reloj mecánico o electrónico, máquina para lavar, todo un ordenador, ¿el cerebro?
• ya se han construido relojes biológicos con trozos de DNA artificial y síntesis de proteínas que visualizan su cambio de estado con luz fluorescente

En el contexto de esta asignatura autómatas serán máquinas matemáticas con estados y funciones de transición (donde se puede añadir entrada, salida, memoria interna modificable, etc.).

En los años 60 se descubrió:

• Los conceptos de gramáticas (formales) y de los autómatas describen el mismo fenómeno
• y están muy relacionados con los algoritmos
• y de esta manera surgió la Teoría de Computabilidad y la Teoría de Complejidad, es decir, la búsqueda de respuestas a las preguntas: ¿Qué es computable? y ¿Cuántos recursos (memoria, espacio, tiempo, transiciones) se necesitan?

Es decir, la Teoría de los Lenguajes Formales (y de los Autómatas) permite responder a preguntas escenciales de la Informática, por ejemplo:

• Tesis de Church: Todo lo que es computable se puede calcular con una Máquina de Turing.
• Existen problemas que no son computables.

Sin TALF: no hay lenguajes, no hay compiladores, no hay programas, no hay nada.

Unos ejemplos:

Con este ``diagrama'' podemos formar unas reglas para sustituir símbolos:

$$\begin{array}{llll} \$\longrightarrow AB & A\longrightarrow ... ...hrm{en\;informatica} & F\longrightarrow \epsilon & \end{array}$$

donde usamos $\epsilon$ para decir que no escribimos nada.

Con dichas reglas podemos `derivar' diferentes frases, por ejemplo:

$$\begin{eqnarray*} \$&\longrightarrow &AB \\ &\longrightarrow &\mathrm{esos}B \... ... &\longrightarrow &\mathrm{esos}\;\mathrm{son}\;\mathrm{clases} \end{eqnarray*}$$

donde siempre hemos usado una regla adecuada para sustituir símbolos hasta llegar a tal punto que ya no se puede aplicar ninguna regla más.

Y con pequeños arreglos podemos traducirlo al alemán:

$$\begin{array}{llll} \$\longrightarrow AB & A\longrightarrow ... ...thrm{in\;Informatik} & F\longrightarrow \epsilon & \end{array}$$

es decir, hemos quitado la regla $A\longrightarrow \epsilon$ y hemos cambiado la regla de $H\longrightarrow IJ$ a $H\longrightarrow JI$.

Otro ejemplo mas sencillo.

Usamos las reglas $\$\longrightarrow ab\$ y $\$\longrightarrow ab$ para generar palabras del tipo $ab$, $abab$, $ababab$ ... Podemos derivar una palabra:

$$\$\longrightarrow ab\$ \longrightarrow abab\$\longrightarrow ababab\$ \longrightarrow ababab$$

siempre aplicando alguna de las reglas hasta tal punto que ya no se puede aplicar ninguna regla.

Construimos un autómata que acepta una palabra del tipo mencionado. Entendemos por aceptar que el autómata llega a su estado final. Consumimos para cada transición de estado una letra de la palabra. Podemos dibujar un autómata:

donde el estado inicial (o de comienzo) está marcado con una flecha, el estado final está marcado con un doble círculo. Las transiciones están visualizadas con arcos entre los estados que a su vez están marcados con sus símbolos correspondientes. Si empezamos en el estado inicial, y si leemos la palabra por aceptar desde la izquierda hacia la derecha, podemos saltar de estado a estado siguiendo los arcos adecuados.

Observamos que llegamos solamente al estado final si la palabra por aceptar es una palabra válida del lenguaje.

Vemos y veremos

• que las gramáticas sirven para generar palabras (y con eso lenguajes) y
• que los autómatas sirven para aceptar palabras (y con eso lenguajes).

Hacia el final del curso tendremos conocimientos sobre una jerarquía de lenguajes y las equivalencias entre:

• Lenguajes Tipo 3, Gramáticas Regulares y Autómatas Finitos,
• Lenguajes Tipo 2, Gramáticas Libres de Contexto y Autómatas Finitos con Pila,
• (Lenguajes Tipo 1, Gramáticas Sensitivos al Contexto y Autómatas Linealmente Acotados),
• Lenguajes Tipo 0, Gramáticas Generales y Máquinas de Turing.