En informática teórica , y en particular en teoría de autómatas , un autómata acotado lineal (en inglés , autómata acotado lineal , abreviado como LBA ) es una máquina de Turing no determinista que utiliza solo una parte contigua de la tira de tamaño lineal en la entrada. Talla.
Un autómata acotado linealmente satisface las siguientes tres condiciones:
En cuanto a las máquinas de Turing , un autómata delimitado linealmente tiene una tira formada por cajas que probablemente contengan un símbolo tomado de un conjunto finito llamado alfabeto , una cabeza puede leer el contenido de una caja y escribir en ella y puede ser movida por 'uno celda a la vez, y finalmente tiene un número finito de estados.
A diferencia de una máquina de Turing , donde se supone que la cinta tiene una longitud potencialmente infinita, en un autómata acotado linealmente, solo una parte contigua de la cinta, cuya longitud es una función lineal de la longitud de los datos, es accesible por el cabezal de lectura y escritura. Este segmento está delimitado por los cuadros que contienen los marcadores finales.
Los autómatas delimitados linealmente reconocen exactamente la clase de lenguajes contextuales . Para mostrar que un lenguaje contextual es reconocido por un autómata acotado linealmente, observamos que en una gramática contextual , un paso de una derivación siempre alarga la palabra producida. Por tanto, si tratamos de reducir una palabra a un axioma, cada paso equivale a acortar la palabra. Por eso es suficiente una memoria limitada.
El argumento, en la otra dirección, es un poco más largo.
En 1960 , John Myhill introdujo un modelo de autómata que ahora se llama autómata determinista acotado linealmente . Poco después, Lawrence Landweber demuestra que los lenguajes reconocidos por autómatas deterministas delimitados linealmente son contextuales. En 1964, Sige-Yuki Kuroda introdujo el modelo más general de autómatas linealmente limitados (no deterministas) como se describió anteriormente y demostró que aceptan exactamente los lenguajes contextuales.
En su artículo fundamental, Kuroda plantea dos problemas de investigación que se han hecho famosos con el nombre en inglés de problemas de LBA .
Kuroda ya notó que una respuesta negativa al segundo problema habría resultado en una respuesta negativa al primero. Pero, de hecho, el segundo problema tiene una respuesta positiva. Esto es una consecuencia del teorema de Immerman-Szelepcsényi que vincula las clases NSPACE y co-NSPACE. Este resultado, probado de forma independiente por Neil Immerman y Róbert Szelepcsényi en 1987 , les valió el Premio Gödel en 1995 . Respecto al primer problema, en 2010 sigue abierto.