En informática , un autómata lineal acotado (en plural: autómatas lineales acotados , abreviado LBA ) es una forma restringida de máquina de Turing .
Un autómata lineal acotado es una máquina de Turing que satisface las tres condiciones siguientes:
En otras palabras: en lugar de tener una cinta potencialmente infinita en la cual realizar los cálculos, el cálculo está restringido a la porción de la cinta que contiene la entrada más los dos cuadrados de cinta que contienen los marcadores finales.
Una definición alternativa, menos restrictiva, es la siguiente:
Esta limitación hace que un LBA sea un modelo algo más preciso de una computadora del mundo real que una máquina de Turing, cuya definición supone una cinta ilimitada.
La definición fuerte y la más débil conducen a las mismas capacidades computacionales de las respectivas clases de autómatas, [1] : 225 por el mismo argumento utilizado para demostrar el teorema de aceleración lineal .
Los autómatas lineales acotados son aceptores para la clase de lenguajes sensibles al contexto . [1] : 225–226 La única restricción impuesta a las gramáticas para tales lenguajes es que ninguna producción asigna una cadena a una cadena más corta. Por lo tanto, ninguna derivación de una cadena en un lenguaje sensible al contexto puede contener una forma oracional más larga que la cadena misma. Dado que existe una correspondencia uno a uno entre los autómatas lineales acotados y tales gramáticas, no se necesita más cinta que la ocupada por la cadena original para que el autómata reconozca la cadena.
En 1960, John Myhill introdujo un modelo de autómata conocido hoy como autómata lineal acotado determinista. [2] En 1963, Peter Landweber demostró que los lenguajes aceptados por los autómatas lineales acotados deterministas son sensibles al contexto. [3] En 1964, S.-Y. Kuroda introdujo el modelo más general de autómatas lineales acotados (no deterministas) y adaptó la prueba de Landweber para mostrar que los lenguajes aceptados por los autómatas lineales acotados no deterministas son precisamente los lenguajes sensibles al contexto. [4] [5]
En su artículo seminal, Kuroda también planteó dos desafíos de investigación, que posteriormente se hicieron famosos como los "problemas LBA": el primer problema LBA es si la clase de lenguajes aceptados por LBA es igual a la clase de lenguajes aceptados por LBA determinista. Este problema se puede expresar sucintamente en el lenguaje de la teoría de la complejidad computacional como:
El segundo problema de LBA es si la clase de lenguajes aceptados por LBA está cerrada bajo complemento.
Como ya observó Kuroda, una respuesta negativa al segundo problema LBA implicaría una respuesta negativa al primer problema. Pero el segundo problema LBA tiene una respuesta afirmativa, que está implícita en el teorema de Immerman-Szelepcsényi demostrado 20 años después de que se planteara el problema. [6] [7] A día de hoy, el primer problema LBA sigue abierto. El teorema de Savitch proporciona una idea inicial: NSPACE (O( n )) ⊆ DSPACE (O( n 2 )). [8]