Estudiante

Dr. Arno Formella

3.

TALF v6

8

Introducción
¿Por qué 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 unentorno 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 sintaxis (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 formalesserán meramente conjuntos de secuencias de símbolos (cuya construcción
se consigue con una gramática formal).
¿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, ¿elcerebro?
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

Dr. Arno Formella

TALF v6

9

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 sedescubrió:
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 losLenguajes 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:
favoritas
Con este “diagrama” podemos formar unasreglas para sustituir símbolos:
$ −→ AB
C −→ son
G −→
J −→

A −→ esos
D −→ EF
H −→ IJ
F −→ en informatica

A −→
B −→ CD
E −→ GH G −→ mis
I −→ clases J −→ favoritas
F −→

donde usamos para decir que no escribimos nada.
Con dichas reglas podemos ‘derivar’ diferentes frases, por ejemplo:
$ −→
−→
−→
−→
−→
−→
−→
−→
−→
−→
−→

AB
esosB
esosCD
esos sonD
esos sonEF
esossonGHF
esos sonHF
esos sonH
esos sonIJ
esos son clasesJ
esos son clases

Dr. Arno Formella

TALF v6

10

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:
$ −→ AB
C −→ sind
G −→
J −→

A −→ dies
B −→ CD
D −→ EF
E −→ GH
G −→ meine
H −→JI
I −→ Vorlesungen J −→ liebsten
F −→ in Informatik F −→

es decir, hemos quitado la regla A −→ y hemos cambiado la regla de H −→ IJ a H −→ JI.
Otro ejemplo mas sencillo.
Usamos las reglas $ −→ ab$ y $ −→ ab para generar palabras del tipo ab, abab, ababab ...
Podemos derivar una palabra:
$ −→ ab$ −→ abab$ −→ ababab$ −→ ababab
siempre aplicando alguna de las reglas hasta tal punto que yano 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:
automata
donde el estado inicial (o de comienzo) está marcado con una flecha, el estado final está marcado
con un doble círculo....