Page 21 - Revista FIUDE 2014

Sin embargo este autómata no aceptará cualquier cadena, por ejemplo rechazará la cadena ba.
Si en el autómata M se procesa la cadena ba, se iniciará el procesamiento de la misma en el estado S y
1
restará por procesar la porción de la cadena ba.
Al recibir una b, la máquina se moverá al estado U, consumiendo esa b y restando por consumir una a.
Pero al llegar al estado U, al no estar definida la transición que dice a dónde ir con una a, la máquina entra
en un estado inválido, del cual no se recupera y por lo tanto cataloga a la cadena ba como una cadena
inválida y no reconocida por este autómata.
Aquellas cadenas que son reconocidas por el autómata M (en este caso ab, bc y cba) se dicen conforman
1
el conjunto de cadenas aceptadas por el autómata y al ser un conjunto de cadenas conforman por
definición un lenguaje. Y este lenguaje es justamente el lenguaje L = {ab, bc, cba }
1
No todos los autómatas finitos son tan sencillos como el anterior, en particular la mayor parte de los
autómatas finitos de la teoría de la computación resultan tener ciclos en su composición y generan
lenguajes infinitos (lenguajes con infinitas cadenas, pero cada cadena es de un largo finito).

Un autómata finito que reconoce una cantidad infinita de cadenas es el siguiente autómata M 2

Este autómata es una máquina de estados que tiene por
estados los siguientes estados abstractos: S, FIN.
Siendo S el estado inicial y FIN el único estado final.

Vale la pena resaltar que aunque una cadena visite un estado final, no necesariamente es aceptada pues
lo importante es tomar en cuenta el estado en el cual queda la máquina luego de haber procesado el
último símbolo de la cadena.
En particular, este autómata tiene “bucles” en su estado S y en su estado FIN.
Si en este autómata M se procesa la cadena aba, se iniciará el procesamiento de la misma en el estado S
2
y restará por procesar la porción de la cadena aba. De modo similar al visto anteriormente, el autómata
irá procesando cada símbolo de la cadena, hasta llegar (en este caso) a que la máquina quede en el
estado FIN (el cual es estado final).

0 Revista de la Facultad de Ingeniería