Teoria Automatas Finito

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˜os recientes se ha visto la aparici´n de un buen n´mero de textos en el tema de
n
o
u
Lenguajes Formales y Aut´matas (Ver al final referencias [10], [7], [23], [8], [3], [21], etc.). Por
o
una parte, esto indica laimportancia y riqueza que el tema tiene; por otra, ante tal variedad
de oferta todo nuevo libro en el ´rea requiere una justificaci´n que indique su aporte con
a
o
respecto a lo existente.
Este texto se sit´a en una generaci´n de textos que tratan de poner el estudio de los
u
o
lenguajes formales y aut´matas al alcance de estudiantes que no necesariamente son avezados
o
matem´ticos buscandoestablecer nuevos teoremas, sino que buscan una iniciaci´n a estos
a
o
temas, que adem´s les sirva como un ejercicio en el arte de formalizar, en particular en
a
nociones relacionadas con la computaci´n. Entre estos textos “accesibles”, encontramos, por
o
ejemplo, a [23]. Estos nuevos textos han reemplazado en muchas universidades a los “cl´sicos”
a
[6] y a´n [10] -que ya era m´saccesible-, y han permitido que la teor´ de la computaci´n se
u
a
ıa
o
estudie a nivel profesional en carreras relacionadas con computaci´n y matem´ticas.
o
a
El presente libro es resultado de una experiencia de impartir el curso de Teor´ de la
ıa
1
Computaci´n por m´s de 10 semestres en el ITESM, en Monterrey, M´xico. Durante este
o
a
e
lapso, aunque ciertamente se fue enriqueciendo elcontenido t´cnico, el principal refinamiento
e
consisti´ en ir detectando cuidadosamente las dificultades principales a las que se enfrentao
ban los estudiantes, para poder estructurar y presentar el material de forma que aquellos
estuvieran en condiciones de comprenderlo de manera eficiente. Aqu´ el ´nfasis no est´ tanto
ı e
a
en hacer el curso “m´s f´cil” para los estudiantes, sino enasegurarse de que ´stos cuenten
a a
e
con los elementos para que ellos mismos reconstruyan estos contenidos dentro de su cabeza;
no se trata, pues, simplemente de “vaciar” informaci´n en la cabeza del estudiante. La teor´
o
ıa
educativa que sustenta esta forma de trabajo esta basada en el “aprendizaje por reestructuraci´n” [18].
o
El texto est´ presentado de manera tal que es posible para elalumno estudiar el material
a
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´n
o
del profesor y ya luego estudia el texto. En el ITESM la clase no se utiliza principalmente
para exposici´n del profesor, sino que se hacen ejercicios, problemas en equipo,miniex´menes
o
a
semanales, etc. Esta situaci´n exige del texto que sea comprensible sin tener ninguna noci´n
o
o
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
ejemploilustrativo.
Este texto es aplicable tanto al nivel de maestr´ en computaci´n o equivalente, como
ıa
o
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´gico y de Estudios Superiores de Monterrey”.
o

iii
de maestr´estriba en que el curso de nivel ingeniero enfatiza los aspectos de “saber hacer”,
ıa
(por ejemplo, saber comparar dos aut´matas deterministas), mientras que el curso de nivel
o
maestr´ enfatiza el “saber justificar” (por ejemplo, probar por inducci´n que una gram´tica
ıa
o
a
es correcta).
El material cuyo nivel es propiamente de maestr´ es identificado por medio de una
ıa
barra vertical...