Page 115 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS

115

INVESTIGACIÓN: AUTÓMATAS LINEALMENTE ACOTADOS

DEFINICIÓN

Un autómata linealmente acotado es una máquina de Turing cuya cinta está formada solamente
por celdas de kn de largo, donde n es la longitud de 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, la
máquina determine si la palabra es aceptable, o si la palabra está en el lenguaje del autómata.

DIFERENCIAS

La diferencia con una máquina de Turing, consiste en que la entrada de la cadena en la cinta es el
único espacio que la cinta permite usar, todo el proceso se hace entre los marcadores del extremo.
Un autómata linealmente acotado tiene más poder que los autómatas de pila no determinísticos,
pero menos poder que las máquinas de Turing.

Los autómatas linealmente acotados se basan en la gramática de Tipo 1 que es sensible al
contexto.

TEOREMAS

• Para cada lenguaje sensible al contexto L existe un autómata linealmente acotado M tales
que L=L (M), es decir, M acepta exactamente las secuencias de L.
• Para cada lenguaje L aceptada por un autómata linealmente acotado (ALA) existe una
gramática sensible al contexto que produzca exactamente LM = L (G).

DEFINICIÓN FORMAL

M: {Q, A, B, δ, q0, F, #, $}

Q = espacio del estado finito

A = alfabeto de entrada

B = alfabeto de la cinta
δ = función de transición

q0 = estado inicial

F = estados finales

# = símbolo distinguido de inicio de cinta

$ = símbolo distinguido de fin de cinta

{L, R, H}: acciones de la cinta.

L = movimiento a la izquierda, R = movimiento a la derecha, H = movimiento nulo.

Q ={q1, q2}, S ={a, b}, G ={a, b, <, >}, F ={q2}, q0 =q1 y d dado por: