Automatas

50
Teorías de Autómatas

ISBN 84-7723-747-6
ISBN 978-84-7723-747-1

y Lenguajes Formales

• Álgebra lineal y Geometría

9 788477 237471

50

Colección manuales uex - 55
(E.E.E.S.)

Elena
Jurado Málaga

55

Teoría de auTómaTas
y lenguajes formales

manuales uex

55
(e.e.e.s.)
espacio
europeo
educación
superior

elena jurado málaga

Teoría de auTómaTas
ylenguajes formales

2008

La publicación del presente manual fue subvencionada por el Vicerrectorado de
Calidad y Formación Continua de la Universidad de Extremadura en la Convocatoria
de Acciones para la Mejora de la Calidad Docente del curso 2007/08 dentro de la
modalidad B.2: “Diseño y desarrollo de materiales docentes adaptados a la metodología derivada del E.E.E.S.” Esta convocatoria deacciones forma parte del Plan de
Adaptación de la UEX al Espacio Europeo de Educación Superior.

FSE

Fo n d o S o c i a l E u ro p e o

Edita
Universidad de Extremadura. Servicio de Publicaciones
C./ Caldereros, 2 - Planta 2ª - 10071 Cáceres (España)
Telf. 927 257 041 - Fax 927 257 046
publicac@unex.es
www.unex.es/publicaciones
ISSN 1135-870-X
ISBN 978-84-691-6345-0
Depósito LegalM-45.211-2008
Edición electrónica: Pedro Cid, S.A.
Teléf.: 914 786 125

A Juan

El estudio de la teor´ de aut´matas y de los lenguajes formales se puede ubicar
ıa
o
en el campo cient´
ıfico de la Inform´tica Te´rica, un campo cl´sico y multidisciplinar
a
o
a
dentro de los estudios universitarios de Inform´tica. Es un campo cl´sico debido no
a
a
s´lo a su antig¨edad (anterior ala construcci´n de los primeros ordenadores) sino,
o
u
o
sobre todo, a que sus contenidos principales no dependen de los r´pidos avances
a
tecnol´gicos que han hecho que otras ramas de la Inform´tica deban adaptarse a los
o
a
nuevos tiempos a un ritmo vertiginoso. Es multidisciplinar porque en sus cimientos
encontramos campos tan aparentemente dispares como la ling¨´
uıstica, lasmatem´ticas
a
o la electr´nica.
o
El hecho de que esta materia no haya sufrido grandes cambios en las ultimas
´
d´cadas no le resta un ´pice de inter´s. El estudio de las m´quinas secuenciales que
e
a
e
a
abarca la teor´ de aut´matas, por una parte, sienta las bases de la algoritmia y
ıa
o
permite modelar y dise˜ar soluciones para un gran n´mero de problemas. Por otra
n
u
parte, permiteabordar cuestiones de gran inter´s para un inform´tico como qu´ tipo
e
a
e
de problemas pueden ser resueltos por un computador o, caso de existir una soluci´n
o
computable para un problema, c´mo podemos medir la calidad (en t´rminos de eficao
e
cia) de dicha soluci´n. Es decir, la teor´ de aut´matas es la puerta que nos permite
o
ıa
o
la entrada hacia campos tan interesantes como lacomputabilidad y la complejidad
algor´
ıtmica. Adem´s, una de las principales aportaciones del estudio de los lenguajes
a
formales, sobre todo desde un punto de vista pr´ctico, es su contribuci´n al dise˜o de
a
o
n
lenguajes de programaci´n y a la construcci´n de sus correspondientes traductores.
o
o
En este sentido la asignatura ayudar´ a conocer con mayor profundidad la estructura
a
delos lenguajes de programaci´n y el funcionamiento de los compiladores.
o
Este manual es el resultado del trabajo que durante varios a˜os he realizado imparn
tiendo la asignatura de Teor´ de Aut´matas y Lenguajes Formales en las titulaciones
ıa
o
de Inform´tica de la Universidad de Extremadura. Dicha asignatura es troncal para
a
los alumnos de Ingenier´ Inform´tica y de Ingenier´ T´cnica enInform´tica de Sisıa
a
ıa e
a
temas pero tambi´n puede ser cursada como materia optativa por los alumnos de
e
Ingenier´ T´cnica en Inform´tica de Gesti´n. Se imparte en el tercer curso de estas
ıa e
a
o
titulaciones.
La asignatura se ha dise˜ado teniendo en cuenta las diferentes circunstancias de
n
los alumnos de las tres titulaciones, as´ como el tiempo disponible a lo largo del...