En informática , un autómata delimitado lineal (plural lineal delimitado autómata , abreviado LBA ) es una forma restringida de máquina de Turing .
Operación
Un autómata acotado lineal es una máquina de Turing no determinista que satisface las siguientes tres condiciones:
- Su alfabeto de entrada incluye dos símbolos especiales, que sirven como marcadores finales izquierdo y derecho.
- Es posible que sus transiciones no impriman otros símbolos sobre los marcadores finales.
- Sus transiciones no pueden moverse ni a la izquierda del marcador final izquierdo ni a la derecha del marcador final derecho. [1] : 225
En otras palabras: en lugar de tener una cinta potencialmente infinita para calcular, el cálculo se restringe a la parte 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:
- Como una máquina de Turing , una LBA posee una cinta compuesta de celdas que pueden contener símbolos de un alfabeto finito , una cabeza que puede leer o escribir en una celda de la cinta a la vez y puede moverse, y un número finito de estados.
- Un LBA se diferencia de una máquina de Turing en que mientras que inicialmente se considera que la cinta tiene una longitud ilimitada, solo una porción finita contigua de la cinta, cuya longitud es una función lineal de la longitud de la entrada inicial, puede ser accedida por la lectura / cabeza de escritura; de ahí el nombre de autómata acotado lineal . [1] : 225
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 habilidades computacionales de las respectivas clases de autómatas, [1] : 225 debido al teorema de aceleración lineal .
LBA y lenguajes sensibles al contexto
Lineal acotado autómatas son aceptantes de la clase de los 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 con una cadena más corta. Por lo tanto, ninguna derivación de una cadena en un lenguaje sensible al contexto puede contener una forma de oración más larga que la propia cadena. Dado que existe una correspondencia uno a uno entre los autómatas delimitados linealmente y tales gramáticas, no se necesita más cinta que la ocupada por la cadena original para que la cadena sea reconocida por el autómata.
Historia
En 1960, John Myhill introdujo un modelo de autómata conocido hoy como autómata determinista lineal limitado. [2] En 1963, Peter Landweber demostró que los lenguajes aceptados por los LBA deterministas son sensibles al contexto. [3] En 1964, S.-Y. Kuroda introdujo el modelo más general de autómatas delimitados lineales (no deterministas), señaló que la prueba de Landweber también funciona para autómatas delimitados lineales no deterministas, y mostró que los lenguajes aceptados por ellos 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 conocieron como los "problemas de LBA": El primer problema de LBA es si la clase de lenguajes aceptados por LBA es igual a la clase de lenguajes aceptados por LBA determinista. Este problema puede expresarse 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 de LBA implicaría una respuesta negativa al primer problema. Pero el segundo problema de 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 planteó el problema. [6] [7] A día de hoy, el primer problema de LBA sigue abierto. El teorema de Savitch proporciona una idea inicial, que NSPACE (O (n)) ⊆ DSPACE (O (n 2 )). [8]
Referencias
- ^ a b c d John E. Hopcroft ; Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 978-0-201-02988-8.
- ^ John Myhill (junio de 1960). Autómatas delimitados lineales (Nota técnica de WADD). Wright Patterson AFB, División de Desarrollo Aéreo de Wright, Ohio.
- ^ PS Landweber (1963). "Tres teoremas sobre gramáticas de estructura de frase de tipo 1" . Información y 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 acotados linealmente" . Información y control . 7 (2): 207–223. doi : 10.1016 / s0019-9958 (64) 90120-2 .
- ^ Willem JM Levelt (2008). Introducción a la teoría de lenguajes formales y autómatas . Editorial John Benjamins. págs. 126-127. ISBN 978-90-272-3250-2.
- ^ Immerman, Neil (1988), "El espacio no determinista se cierra 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 forzar para autómatas no deterministas", Acta Informatica , 26 (3): 279-284
- ^ Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
enlaces externos
- Autómatas delimitados lineales de Forbes D. Lewis
- Diapositivas de Autómatas delimitados lineales , parte de Lenguajes sensibles al contexto de Arthur C. Fleck
- Autómatas delimitados lineales , parte del programa de estudios de Teoría de la Computación, por David Matuszek