Automatas y lenguajes computacionales

AUTOMATAS Y LENGUAJES
Un enfoque de diseño

ab a b b

...

q7 q6 q5

q0

q1 q2 q3 Ramón Brena Tec de Monterrey Verano 2003

q4

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 la importancia yriqueza 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 buscando establecer 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´s accesible-, y han permitido que la teor´ dela 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 el contenido t´cnico, el principal refinamiento econsisti´ 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 en asegurarse de que ´stos cuenten a a e con los elementos para queellos 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 el alumno estudiar el material a antes de cubrir el tema en clase; de hechoesta 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 seacomprensible 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 ejemplo ilustrativo. 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 (porejemplo, 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 al margen, como en el presente p´rrafo. Esto incluye tambi´n las secciones de a e ejercicios. En breve,...