EJEMPLO 1
Quizá el autómata finito no trivial más simple sea un interruptor de apagado/encendido (posiciones on/off). El dispositivo recuerda si está en el estado encendido (“on”) o en el estado apagado (“off”), y permite al usuario pulsar un botón cuyo efecto es diferente dependiendo del estado del interruptor. Es decir, si el interruptor está en el estado off, entonces al pulsar el botón cambia al estado on, y si el interruptor está en el estado on, al pulsar el mismo botón pasa al estado off.
En la figura anterior se muestra el modelo de autómata finito para el interruptor. Como en todos los autómatas finitos, los estados están representados mediante círculos; en este ejemplo, hemos denominado a los estados on y off. Los arcos entre los estados están etiquetados con las “entradas”, las cuales representan las influencias externas sobre el sistema. Aquí, ambos arcos se han etiquetado con la entrada Pulsar, que representa al usuario que pulsa el botón. Los dos arcos indican que, sea cual sea el estado en que se encuentra el sistema, cuando recibe la entrada Pulsar pasa al otro estado.
Uno de los estados se designa como el “estado inicial”, el estado en el que el sistema se encuentra inicialmente. En nuestro ejemplo, el estado inicial es apagado (off) y, por conveniencia, hemos indicado el estado inicial mediante la palabra Inicio y una flecha que lleva al otro estado.
A menudo es necesario especificar uno o más estados como estado “final” o“de aceptación”. Llegar a uno de estos estados después de una secuencia de entradas indica que dicha secuencia es correcta. Por ejemplo, podríamos establecer el estado on de la Figura anterior como estado de aceptación, ya que en dicho estado, el dispositivo que está siendo controlado por el interruptor funciona. Normalmente, los estados de aceptación se indican mediante un círculo doble, aunque en la Figura anterior no lo hemos hecho.
EJEMPLO 2
En ocasiones, lo que recuerda un estado puede ser mucho más complejo que una elección entre las posiciones apagado/encendido(on/off). La Figura siguiente muestra otro autómata finito que podría formar parte de un analizador léxico. El trabajo de este autómata consiste en reconocer la palabra clave then, por lo que necesita cinco estados, representando cada uno de ellos la posición dentro de dicha palabra que se ha alcanzado hasta el momento. Estas posiciones se corresponden con los prefijos de la palabra, desde la cadena de caracteres vacía (es decir, cuando no contiene ningún carácter) hasta la palabra completa.
En la Figura siguiente, los cinco estados se designan mediante el correspondiente prefijo de then visto hasta el momento. Las entradas se corresponden con las letras. Podemos imaginar que el analizador léxico examina un carácter del programa que se está compilando en un determinado instante, y que el siguiente carácter que se va a examinar es la entrada al autómata. El estado inicial se corresponde con la cadena vacía y cada uno de los estados tiene una transición a la siguiente letra de la palabra then, al estado que corresponde al siguiente prefijo más largo. El estado denominado then se alcanza cuando la entrada está formada por todas las letras de dicho término. Puesto que el trabajo de este autómata es indicar el reconocimiento de la palabra then, podemos considerar dicho estado como el único estado de aceptación.
