Page 41 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

41

TIPOS DE AUTÓMATAS

Los autómatas reconocidos son:

 La máquina de Turing propiamente dicha.
 Los autómatas lineales acotados.
 Autómata de pila.
 Autómata finito determinista.

Cada uno resuelve un lenguaje en particular y es usado en múltiples aplicaciones de la vida diaria.

Máquinas de Turing: (definición de máquinas de Turing)

Dispositivo hipotético capaz de manipular símbolos en una tira de cinta considerando ciertas
reglas. A pesar de su simplicidad, pueden simular la lógica de cualquier algoritmo de un
computador. Intuitivamente, una máquina de Turing se puede conceptuar como un dispositivo
capaz de adoptar un estado entre varios posibles y que dispone de un cabezal capaz de leer y
escribir símbolos que lee de la cinta y realiza 3 acciones:

 Escribe un nuevo símbolo en la cinta, en la misma casilla donde acaba de leer un símbolo.
 Desplaza el cabezal una única posición a lo largo de la cinta, hacia la derecha o hacia la
izquierda, o bien dejarlo apuntando a la misma casilla
 Cambia de estado.

Esquema de una máquina de Turing

CINTA

CABEZA DE ESCRITURA
LECTURA LA CABEZA SE MUEVE EN
AMBAS
DIRECCIONES
INDICADOR DE
ESTADO

Autómatas lineales acotados:

Un autómata linealmente acotado es un dispositivo abstracto cuya cinta está formada solamente
por celdas de kn de largo, donde la longitud n es la secuencia de la entrada y k es una constante
asociada al autómata linealmente-acotado particular, es decir la cantidad de cinta que el autómata
permite usar se limita por un factor lineal k para que cuando entre una palabra de tamaño n (los
símbolos de n) , la máquina determine si la palabra es aceptable, o si la palabra está en el lenguaje
del autómata.