988999

Prefacio
En a˜nos recientes se ha visto la aparici´on de un buen n´umero de textos en el tema de
Lenguajes Formales y Aut´omatas (Ver al final referencias [10], [7], [23], [8], [3], [21], etc.). Por
una parte, esto indica la importancia y riqueza que el tema tiene; por otra, ante tal variedad
de oferta todo nuevo libro en el ´area requiere una justificaci´on que indique su aporte conrespecto a lo existente.
Este texto se sit´ua en una generaci´on de textos que tratan de poner el estudio de los
lenguajes formales y aut´omatas al alcance de estudiantes que no necesariamente son avezados
matem´aticos buscando establecer nuevos teoremas, sino que buscan una iniciaci´on a estos
temas, que adem´as les sirva como un ejercicio en el arte de formalizar, en particular en
nocionesrelacionadas con la computaci´on. Entre estos textos “accesibles”, encontramos, por
ejemplo, a [23]. Estos nuevos textos han reemplazado en muchas universidades a los “cl´asicos”
[6] y a´un [10] -que ya era m´as accesible-, y han permitido que la teor´ıa de la computaci´on se
estudie a nivel profesional en carreras relacionadas con computaci´on y matem´aticas.
El presente libro es resultado de unaexperiencia de impartir el curso de Teor´ıa de la
Computaci´on por m´as de 10 semestres en el ITESM, 1 en Monterrey, M´exico. Durante este
lapso, aunque ciertamente se fue enriqueciendo el contenido t´ecnico, el principal refinamiento
consisti´o en ir detectando cuidadosamente las dificultades principales a las que se enfrentaban
los estudiantes, para poder estructurar y presentar el material deforma que aquellos
estuvieran en condiciones de comprenderlo de manera eficiente. Aqu´ı el ´enfasis no est´a tanto
en hacer el curso “m´as f´acil” para los estudiantes, sino en asegurarse de que ´estos cuenten
con los elementos para que ellos mismos reconstruyan estos contenidos dentro de su cabeza;
no se trata, pues, simplemente de “vaciar” informaci´on en la cabeza del estudiante. Lateor´ıa
educativa que sustenta esta forma de trabajo esta basada en el “aprendizaje por reestructuraci
´on” [18].
El texto est´a presentado de manera tal que es posible para el alumno estudiar el material
antes de cubrir el tema en clase; de hecho esta es la forma en que se utiliza en el ITESM,
contrariamente a muchas clases tradicionales, en las que el alumno se presenta a la exposici´on
delprofesor y ya luego estudia el texto. En el ITESM la clase no se utiliza principalmente
para exposici´on del profesor, sino que se hacen ejercicios, problemas en equipo, miniex´amenes
semanales, etc. Esta situaci´on exige del texto que sea comprensible sin tener ninguna noci´on
del tema adquirida previamente, por lo que tuvimos que incluir explicaciones claras que
permitan al alumno reconstruir ensu mente la idea intuitiva, y -sobre todo- ejemplos. A
lo largo del texto, cada una de las nociones presentadas es seguida inmediatamente por un
ejemplo ilustrativo.
Este texto es aplicable tanto al nivel de maestr´ıa en computaci´on o equivalente, como
a clases de nivel profesional (licenciaturas, ingenier´ıas). De hecho en el ITESM se aplica en
ambos niveles. La diferencia fundamental entreel enfoque del curso de nivel profesional y el
1Abreviatura de “Instituto Tecnol´ogico y de Estudios Superiores de Monterrey”.
iii
de maestr´ıa estriba en que el curso de nivel ingeniero enfatiza los aspectos de “saber hacer”,
(por ejemplo, saber comparar dos aut´omatas deterministas), mientras que el curso de nivel
maestr´ıa enfatiza el “saber justificar” (por ejemplo, probar por inducci´onque una gram´atica
es correcta).
El material cuyo nivel es propiamente de maestr´ıa es identificado por medio de una
barra vertical al margen, como en el presente p´arrafo. Esto incluye tambi´en las secciones de
ejercicios.
En breve, los puntos que caracterizan a este libro, y que en cierta medida lo hacen
particular, son:
La presentaci´on did´actica ha sido -en nuestra opini´on- m´as...