ensayos

´
Isabel Navarrete Sanchez
´
Mar´ Antonia Cardenas Viedma
ıa
´
Daniel Sanchez Alvarez
Juan Antonio Bot´ Blaya
ıa
Roque Mar´ Morales
ın
´
Rodrigo Mart´
ınez Bejar
´
Departamento de Ingenier´ de la Informacion
ıa
y las Comunicaciones
Universidad de Murcia

´
TEOR´ DE AUTOMATAS
IA
Y
LENGUAJES FORMALES

Introducci´n
o
Aunque no debemos hacer una distinci´n tajante entrelos aspectos pr´cticos y te´ricos de la
o
a
o
Inform´tica, es cierto que existen materias que tienen un alto contenido formal, con desarrollos
a
de tipo matem´tico, al contrario que otros temas m´s cercanos a la resoluci´n de problemas de
a
a
o
tipo pr´ctico. La asignatura de Teor´ de Aut´matas y Lenguajes Formales sin duda trata con
a
ıa
o
las materias del primer tipo y loscontenidos que se imparten constituyen el eje fundamental de
diversas ´reas de conocimiento encuadradas dentro de lo que podr´
a
ıamos denominar Inform´tica
a
Te´rica. A veces estas disciplinas resultan para el alumno materias “´ridas” y distanciadas de
o
a
lo que ellos entienden que deber´ estudiar en una carrera de Ingenier´ Inform´tica. Pero la
ıan
ıa
a
Inform´tica, como cualquier otraciencia o ingenier´ tiene unos fundamentos te´ricos sobre
a
ıa,
o
los que apoyarse y que cualquier ingeniero en Inform´tica debe conocer. As´ lo entienden dia
ı
versos organismos internacionales como ACM e IEEE que recomiendan al menos un curso de
Aut´matas y Lenguajes Formales en los curricula de las carreras relacionadas con la Inform´tio
a
ca. Una motivaci´n para el estudio de estasmaterias formales la expuso Millner en un discurso
o
que dio en 1993 al recoger el prestigioso premio Turing que se otorga a distinguidos cient´
ıficos
que trabajan en el ´rea de las Ciencias de la Computaci´n:
a
o
“Estas [las aplicaciones] son altamente necesarias, pero no queremos que esto ocurra
en detrimento del trabajo te´rico...Las Ciencias de la Computaci´n son tan amplias
o
o
que si notienen una teor´ b´sica, estaremos perdidos. Tantas cosas est´n avanzanıa a
a
do...¿C´mo podr´ ocurrir esto sin una teor´ Esta tiene que ir cogida de la mano
o
ıa
ıa?
de la pr´ctica.”
a

1.

Evoluci´n hist´rica de la Teor´ de la Computaci´n
o
o
ıa
o

La Teor´ de la Computaci´n trata con modelos de c´lculo abstractos que describen con distintos
ıa
o
a
grados de precisi´n lasdiferentes partes y tipos de computadores. Pero estos modelos no se
o
usan para describir detalles pr´cticos del hardware de un determinado ordenador, sino que m´s
a
a
bien se ocupan de cuestiones abstractas sobre la capacidad de los ordenadores, en general. As´
ı,
en los curricula de Ciencias de la Computaci´n existen cursos separados para tratar materias
o
como Arquitectura deComputadores, Teor´ de Circuitos, Algoritmos y Estructuras de Datos,
ıa
Sistemas Operativos, etc. Todas estas areas tienen una componente te´rica, pero difieren del
´
o
estudio de la Teor´ de la Computaci´n fundamentalmente en dos aspectos:
ıa
o
Las primeras tratan con computadores que existen realmente, mientras que los modelos
abstractos de c´lculo abarcan todo tipo de computadores que existen, quepuedan llegar
a
a existir o simplemente que uno pueda imaginar.
En Teor´ de la Computaci´n, a diferencia de las otras materias, lo importante no es
ıa
o
buscar la mejor manera de hacer las cosas (optimalidad ) sino estudiar qu´ puede o no
e
puede hacerse con un ordenador (computabilidad ).
2

La historia de la Teor´ de la Computaci´n es bastante interesante. Se ha desarrollado graciasıa
o
a confluencia, por afortunadas coincidencias, de distintos campos de conocimiento y descubrimientos (fundamentalmente matem´ticos) realizados a principios del siglo XX. Bajo el nombre
a
Teor´ de la Computaci´n se recogen una serie de materias que constituyen hoy en d´ los funıa
o
ıa
damentos te´ricos de la Inform´tica: Teor´ de Aut´matas, Teor´ de los Lenguajes Formales,
o
a
ıa...