Page 20 - Revista FIUDE 2014

Autómatas Finitos

Los autómatas finitos son un tipo especial de máquina de estados con una utilidad más teórica que
práctica.

También tienen un conjunto de estados pero sus transiciones, en lugar de ser acciones del mundo real,
tales como detectar si una persona está al frente o detrás de una puerta, involucran el procesar el símbolo
de una cadena de entrada.
Recordemos el lenguaje L mencionado anteriormente en páginas anteriores.
1
L = { ab, bc, cba } era un lenguaje formado por tres cadenas cuyo alfabeto es ∑ .
1
1
Este lenguaje se destaca por ser un Lenguaje Regular.
Esto quiere decir que se puede encontrar un autómata finito que genere todas sus cadenas.
Un autómata finito que genera sus cadenas (M
1
podría ser un nombre apropiado) es el siguiente:
Este autómata es una máquina de estados que
tiene los siguientes estados abstractos: S, T, U, V,
W, FIN.
Por transiciones, en lugar de tener una acción
como FRENTE o DETRÁS tiene símbolos de un
alfabeto, en este caso a los símbolos a, b, c.
Algunos de los estados del autómata son estados
especiales.
S es el único estado inicial del autómata.
FIN es un estado final (podría haber más de un
estado final en otros autómatas de ejemplo).

Los autómatas finitos toman como entrada una cadena de símbolos como ‘cba’, y comenzando en el
estado inicial, van procesando cada símbolo de dicha cadena de izquierda a derecha (primero c, luego b
y finalmente a) y paran cuando terminan de procesar el último símbolo.

En el eventual caso que luego de procesar el último símbolo la máquina se encuentre en un estado final
(un estado de doble círculo como FIN), se dice que esa cadena es aceptada por el autómata.

Por ejemplo, si en el autómata M se procesa la cadena cba, se iniciará el procesamiento de la misma en
1
el estado S y restará por procesar la porción de la cadena cba. Luego se procesará la c y la máquina se
moverá al estado V, restando la subcadena ba por procesar. A continuación se procesará la b y la máquina
se moverá del estado V al estado W, restando una a por procesar. Finalmente se procesará la última a y la
máquina se moverá del estado W al estado FIN. Y como luego de procesar el último símbolo, la máquina
quedó sobre un estado final, se dice que la cadena cba es una cadena aceptada por el autómata M .
1

Reflexiones sobre Ingeniería