Teoria de automatas

´ 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 Septiembre,2008

Introducci´n o
Aunque no debemos hacer una distinci´n tajante entre losaspectos 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 los contenidos que se impartenconstituyen 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 otra ciencia o ingenier´ tiene unosfundamentos 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 estas materias formales la expuso Millner en undiscurso 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 no tienen una teor´ b´sica, estaremos perdidos. Tantascosas 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 las diferentes partes y tipos de computadores. Pero estos modelos no se ousan 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 de Computadores, Teor´ de Circuitos, Algoritmos y Estructuras de Datos, ıa SistemasOperativos, etc. Todas estas ´reas tienen una componente te´rica, pero difieren del a 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, que puedan llegar a a existir o simplemente que uno pueda imaginar. En Teor´ de laComputaci´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 ydescubrimientos (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 o ıa Computabilidad y Complejidad Algor´ ıtmica. Computabilidad El primer tema que cae claramente dentro del...