Hispanopedia WikiEn informática , un autómata lineal acotado (abreviado LBA ) es una forma restringida de máquina de Turing que funciona como un modelo más preciso de un ordenador del mundo real , ya que su definición no presupone una cinta ilimitada.
Formalmente, cumple las siguientes tres condiciones:
- Su alfabeto de entrada incluye dos símbolos especiales que sirven como marcadores de extremo izquierdo y derecho.
- Sus transiciones pueden no imprimir otros símbolos sobre los marcadores de extremo.
- Sus transiciones no pueden moverse ni a la izquierda del marcador de extremo izquierdo ni a la derecha del marcador de extremo derecho. [ 1 ] : 225
En otras palabras: en lugar de disponer de una cinta potencialmente infinita para realizar los cálculos, estos se limitan a la porción de la cinta que contiene la entrada más los dos cuadrados de cinta que contienen los marcadores de extremo.
Una definición alternativa y menos restrictiva es la siguiente:
- Al igual que una máquina de Turing , un LBA posee una cinta compuesta por celdas que pueden contener símbolos de un alfabeto finito , un cabezal que puede leer o escribir en una celda de la cinta a la vez y que puede moverse, y un número finito de estados.
- Un autómata lineal acotado (LBA) se diferencia de una máquina de Turing en que, si bien inicialmente se considera que la cinta tiene una longitud ilimitada, el cabezal de lectura/escritura solo puede acceder a una porción finita y contigua de la cinta, cuya longitud es una función lineal de la longitud de la entrada inicial; de ahí el nombre de autómata lineal acotado . [ 1 ] : 225
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 probar el teorema de aceleración lineal .
LBA y lenguajes sensibles al contexto
Los autómatas lineales acotados son aceptadores 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 mapea 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 sentencial más larga que la propia cadena. Dado que existe una correspondencia biunívoca entre los autómatas lineales acotados y dichas gramáticas, no se necesita más cinta que la ocupada por la cadena original para que el autómata la reconozca.
Historia
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 demostración 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 ]
Problemas de LBA
En su artículo fundamental, 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 puede formularse 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 es cerrada bajo el complemento.
Como ya observó Kuroda, una respuesta negativa al segundo problema LBA implicaría una respuesta negativa al primero. Pero el segundo problema LBA tiene una respuesta afirmativa, que se deduce del 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 ]
Referencias
- ^ a b c d Hopcroft, John E. ; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley. ISBN 0-201-02988-X.( Accesible para usuarios con discapacidades visuales )
- ^ John Myhill (junio de 1960). Autómatas lineales acotados (nota técnica de WADD). Base de la Fuerza Aérea Wright-Patterson, División de Desarrollo Aéreo Wright, Ohio.
- ^ PS Landweber (1963). "Tres teoremas sobre gramáticas de estructura sintagmática de tipo 1" . Information and Control . 6 (2): 131– 136. doi : 10.1016/s0019-9958(63)90169-4 .
- ^ Sige-Yuki Kuroda (junio de 1964). "Clases de lenguajes y autómatas linealmente acotados" . Information and Control . 7 (2): 207– 223. doi : 10.1016/s0019-9958(64)90120-2 .
- ^ Willem JM Levelt (2008). Introducción a la teoría de los lenguajes formales y los autómatas . John Benjamins Publishing. pp. 126–127 . ISBN 978-90-272-3250-2.
- ^ Immerman, Neil (1988), "El espacio no determinista es cerrado bajo complementación" (PDF) , SIAM Journal on Computing , 17 (5): 935–938 , doi : 10.1137/0217058 , MR 0961049
- ^ Szelepcsényi, Róbert (1988), "El método de enumeración forzada para autómatas no deterministas", Acta Informatica , 26 (3): 279– 284, doi : 10.1007/BF00299636 , S2CID 10838178
- ^ Arora, Sanjeev ; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Cambridge University Press. ISBN 978-0-521-42426-4.
Enlaces externos
- Autómatas lineales acotados por Forbes D. Lewis
- Diapositivas sobre autómatas lineales acotados , parte de Lenguajes sensibles al contexto de Arthur C. Fleck.
- Autómatas lineales acotados. Archivado el 18 de enero de 2021 en Wayback Machine , parte del programa de estudios de Teoría de la Computación, por David Matuszek.
- Autómatas (computación)
- Modelos de computación