holasas

AUTOMATAS
Y LENGUAJES
Un enfoque de diseño

ab a b b

q7

q0

q6
q5

...

q1
q2

q4

q3
Ramón Brena
Tec de Monterrey
Verano 2003

ii

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 laimportancia 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 con
respecto 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 buscandoestablecer 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
nociones relacionadas 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 hanpermitido 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 una experiencia 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 principalrefinamiento
consisti´o en ir detectando cuidadosamente las dificultades principales a las que se enfrentaban los estudiantes, para poder estructurar y presentar el material de forma 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 elementospara que ellos mismos reconstruyan estos contenidos dentro de su cabeza;
no se trata, pues, simplemente de “vaciar” informaci´on en la cabeza del estudiante. La teor´ı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 enclase; 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
del profesor 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 quesea comprensible sin tener ninguna noci´on
del tema adquirida previamente, por lo que tuvimos que incluir explicaciones claras que
permitan al alumno reconstruir en su 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 encomputaci´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 entre el enfoque del curso de nivel profesional y el
1

Abreviatura 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 “saberhacer”,
(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´on que 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...