Page 22 - Revista FIUDE 2014

El modo particular en que el autómata está construido o “cableado” hace que solamente se acepte
aquellas cadenas cuyo último símbolo es una a, como por ejemplo aba, bba, a; y que rechace a aquellas
cadenas que terminan su procesamiento dejando a la máquina en el estado S, el cual no es un estado
final como FIN. Algunos ejemplos de cadenas rechazadas incluyen: b, ab, aab.
El lenguaje generado por este autómata incluye a todas las cadenas que terminan en un símbolo a y se
corresponde con el lenguaje L mencionado anteriormente.
3
L = {a, aa, ba, aaa, aba, baa, bba, … }
3
Sin embargo, existen algunos lenguajes que son aún más complejos que los lenguajes L y L vistos
3
1
anteriormente, se trata de lenguajes no regulares que no pueden ser generados por un autómata finito.
Un autómata finito si bien posee estados y el autómata al estar procesando una cadena puede recordar
en qué estado está, no posee ningún otro mecanismo que le permita ir contando o recordar la cantidad
de símbolos (símbolos a, b, etc.) de cada tipo procesados hasta el momento.

De hecho, el lenguaje L mencionado anteriormente, no puede ser generado utilizando autómatas finitos
4
y es necesario utilizar una máquina de Turing para generarlo.
L = {0#0, 1#1, 00#00, 01#01, 10#10, 11#11, … } lenguaje de todas las cadenas cuyo alfabeto es ∑ que
4
4
tienen un símbolo # en su centro y que a ambos lados del # tienen la misma subcadena, la cual está
formada por símbolos 0 y 1.
Esto es debido a que se precisa una estructura auxiliar (un contenedor con memoria) tal como una pila
de símbolos o una cinta, para poder ir recordando cuáles símbolos 0 y 1 y en qué orden se procesaron al
principio para luego poder ser capaz de chequear si se corresponden exactamente con los símbolos 0 y 1
que hay a la derecha del símbolo # del centro.

Máquinas de Turing

Las Máquinas de Turing son un tipo de autómata propuesto por el matemático Alan Turing en 1936.
Son similares a un autómata finito pero se destacan por poseer un contenedor de memoria infinita en
forma de cinta.
En cuanto a computabilidad, una Máquina de Turing es un modelo mucho más preciso de un computador
y teóricamente puede realizar cualquier tarea que un computador real pueda.
A nivel de funcionamiento, poseen también un conjunto de estados, entre los cuales se destacan un
estado inicial, un estado para aceptar cadenas y un estado para rechazar cadenas.
Usan una cinta con memoria infinita y tienen un cabezal que puede leer y escribir símbolos sobre el lugar
donde está parado este cabezal.
Además dicho cabezal puede moverse un lugar hacia adelante o hacia atrás luego de realizar un
movimiento o transición.

Reflexiones sobre Ingeniería