Autómata linealmente acotado
Un autómata linealmente acotado, abreviadamente LBA (del inglés, Linear Bounded Automaton),o ALA es un autómata similar a una máquina de Turing determinista.
Historia
Si bien las máquinas abstractas introducidas hasta entonces tenían como objetivo el cálculo de funciones, con el tiempo los investigadores se encargaron de estudiar la potencia de las máquinas como reconocedoras de lenguajes. El propio Chomsky estableció en 1959 la equivalencia entre las gramáticas de tipo 0 y las Máquinas de Turing.
En 1958 Chomsky y Miller notaron que las gramáticas de tipo 3 son equivalentes a los autómatas finitos introducidos por Kleene en 1951.Chomsky y Schutzenberger en 1963 demostraron que las gramáticas de tipo 2 equivalen a los autómatas con pila. Por último, en 1964 Kuroda descubre que los lenguajes de tipo 1 son reconocidos por los autómatas linealmente acotados.
Autómatas lineales
Los autómatas linealmente acotados son similares a una máquina de Turing, sabemos que esta última tiene una cinta infinita.
Un autómata linealmente acotado es una máquina de Turing cuya cinta está formada solamente por celdas de kn de largo, donde la longitud n es 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 (los símbolos de n) , la máquina determine si la palabra es aceptable, o si la palabra está en el lenguaje del autómata.
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 (sensibles al contexto).
Para cada lenguaje sensible al contexto L existe un autómata linealmente-acotado M tales que , es decir, M acepta exactamente las secuencias de L.Teorema
Para cada lenguaje L aceptada por un autómata linealmente-acotado ALA existe una gramática sensible al contexto que produzca exactamente .Teorema
Componentes
Un autómata linealmente acotado está formado por los siguientes componentes:
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 | el estado inicial |
| F | los 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.
En ninguna cinta se permite δ(#,L) ni δ($,R), o sea no se puede ir más allá de los símbolos que delimitan la cinta.
Un autómata linealmente acotado es un autómata finito con una cinta T de acceso de lectura/escritura de una longitud determinada por la cadena de entrada W. M tiene una cabeza de lectura/escritura la cual se mueve a la izquierda o derecha en un determinado espacio de tiempo, pero no puede moverse fuera de la cinta. El nombre de "linealmente acotado" se refiere al hecho de que la capacidad de almacenamiento T, es un múltiplo constante de la capacidad que exigió tener W. M tiene un alfabeto B que contiene a un subconjunto A, y típicamente tiene caracteres adicionales usados para el trabajo improvisado.
Los autómatas linealmente acotados se desarrollaron para modelar procesos computacionales, son importantes en la teoría de cómputo aunque de ellos no han surgido tantas aplicaciones comparado a la magnitud que los autómatas de pila disfrutan.
Las computadoras son dispositivos finitos. Ellas no tienen cantidades inacabables de almacenamiento como las máquinas de Turing. Así cualquier cálculo real hecho en una computadora no es tan extenso como lo que podría completarse en una máquina de Turing. Para imitar a las computadoras, se debe restringir la capacidad del almacenamiento de las máquinas de Turing.
Un autómata linealmente acotado (ALA) es una máquina de Turing multi-direcciones que tiene solo una cinta, y esta cinta es exactamente de la misma longitud de la de entrada. Para establecer los límites de la cinta se emplean los símbolos # a la izquierda y $ a la derecha, los cuales no permiten a la máquina ir más allá de ellos.
Lenguajes no reconocidos por un autómata linealmente acotado
- Lenguajes recursivamente enumerables