Titulo Carlos

Cap´ ıtulo 2 Aut´matas finitos o
El t´rmino m´quina evoca algo hecho en metal, usualmente ruidoso y grasoso, que ejee a cuta tareas repetitivas que requieren de mucha fuerza o velocidad o precisi´n. Ejemplos o de estas m´quinas son las embotelladoras autom´ticas de refrescos. Su dise˜o requiere de a a n conocimientos en mec´nica, resistencia de materiales, y hasta din´mica de fluidos. Al dise˜ar aa n tal m´quina, el plano en que se le dibuja hace abstracci´n de algunos detalles presentes en a o la m´quina real, tales como el color con que se pinta, o las imperfecciones en la soldadura. a El plano de dise˜o mec´nico de una m´quina es una abstracci´n de ´sta, que es util n a a o e ´ para representar su forma f´ ısica. Sin embargo, hay otro enfoque con que se puede modelar la m´quinaembotelladora: c´mo funciona, en el sentido de saber qu´ secuencia de operaciones a o e ejecuta. As´ la parte que introduce el l´ ı, ıquido pasa por un ciclo repetitivo en que primero introduce un tubo en la botella, luego descarga el l´ ıquido, y finalmente sale el tubo para permitir la colocaci´n de la c´psula (“corcholata”). El orden en que se efect´a este ciclo es o a u crucial, pues si se descarga ell´ ıquido antes de haber introducido el tubo en la botella, el resultado no ser´ satisfactorio. a El modelado de una m´quina en lo relacionado con secuencias o ciclos de acciones se a aproxima m´s al enfoque que adoptaremos en este curso. Las m´quinas que estudiaremos a a son abstracciones matem´ticas que capturan solamente el aspecto referente a las secuencias a de eventos que ocurren, sin tomaren cuenta ni la forma de la m´quina ni sus dimensiones, a ni tampoco si efect´a movimientos rectos o curvos, etc. u En esta parte estudiaremos las m´quinas abstractas m´s simples, los aut´matas finitos, a a o las cuales est´n en relaci´n con los lenguajes regulares, como veremos a continuaci´n. a o o

25

26

´ CAP´ ITULO 2. AUTOMATAS FINITOS

2.1.

Modelado de sistemas discretos

Antes de definirlos aut´matas finitos, empezaremos examinando las situaciones de la o realidad que pueden ser modeladas usando dichos aut´matas. De esta manera, iremos de lo o m´s concreto a lo m´s abstracto, facilitando la comprensi´n intuitiva del tema. a a o El modelado de fen´menos y procesos es una actividad que permite: o

Verificar hip´tesis sobre dichos procesos; o Efectuar predicciones sobre elcomportamiento futuro; Hacer simulaciones (eventualmente computarizadas); Hacer experimentos del tipo “¿qu´ pasar´ si. . . ?”, sin tener que actuar sobre el proceso e ıa o fen´meno f´ o ısico.

Llamamos eventos discretos a aqu´llos en los que se considera su estado s´lo en ciertos e o momentos, separados por intervalos de tiempo, sin importar lo que ocurre en el sistema entre estos momentos. Es como si laevoluci´n del sistema fuera descrita por una secuencia o de fotograf´ en vez de un flujo continuo, y se pasa bruscamente de una fotograf´ a otra. ıas, ıa Usualmente se considera que la realidad es continua, y por lo tanto los sistemas discretos son solamente una abstracci´n de ciertos sistemas, de los que nos interesa enfatizar su aspecto o “discreto”. Por ejemplo, en un motor de gasolina se dice quetiene cuatro tiempos: Admisi´n, o Compresi´n, Ignici´n y Escape. Sin embargo, el pist´n en realidad no se limita a pasar por o o o cuatro posiciones, sino que pasa por todo un rango de posiciones continuas. As´ los “cuatro ı, tiempos” son una abstracci´n de la realidad. o La noci´n m´s b´sica de los modelos de eventos discretos es la de estado. Un estado es o a a una situaci´n en la que sepermanece un cierto lapso de tiempo. Un ejemplo de la vida real es o el de los “estados civiles” en que puede estar una persona: soltera, casada, viuda, divorciada, etc. De uno de estos estados se puede pasar a otro al ocurrir un evento o acci´n, que es el o segundo concepto b´sico de la modelaci´n discreta. As´ por ejemplo, del estado “soltero” se a o ı, puede pasar al estado “casado” al ocurrir el...