Autómatas linealmente acotados

Autómatas linealmente acotados

Un autómata linealmente acotado, abreviadamente LBA (del inglés, Linear Bounded Automaton), es un autómata similar a una máquina de Turing no determinista.

Contenido

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 (máquinas de Turing no deterministas)

Autómatas lineales

Los autómatas linealmente acotados son similares a una máquina de Turing, sabemos que ésta última tiene una cinta infinita.

Un autómata linealmente-acotado (ALA) 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 L = L(M), 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 LM = L(G).
Teorema

Componentes

Un autómata linealmente acotado esta formado por los siguientes componentes:

M = (Q, A, B, f: Q \times B \rightarrow Q \times B \times \{L, R, H,\ldots\},q_0, F)

Q Espacio del estado finito
A alfabeto de entrada
B alfabeto de la cinta
f función de transición
q0 el estado inicial
F los estados finales

{L, R, H,..}: acciones de la cinta: L = movimiento a la izquierda, R = movimiento a la derecha, H = parada.

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 sólo 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.

Ejemplo

En el caso de las computadoras, estos dispositivos cuentan con un rasgo de seguridad, los cuales indican la capacidad de almacenamiento de las mismas, por lo que no se debe de sobrepasar su límite.

Los autómatas linealmente acotados se restringen a un área limitada por una constante, esto es similar con un ambiente de programación dónde se limitan los tamaños de valores para las variables. El problema de detenimiento es solucionado para el autómata linealmente acotado.

Prueba

El argumento aquí será basado en el número de posibles configuraciones para un Autómata linealmente acotado. Asumamos que se tiene un autómata linealmente acotado con una cinta de k instrucciones, un alfabeto, una cinta de símbolos s, y una cinta de entrada de n caracteres de longitud. Una configuración de un autómata linealmente acotado está igual que una máquina Turing y consiste en:

  • una instrucción,
  • la posición de la cabeza de la cinta, y
  • el contenido de la cinta.

La pregunta ahora es: ¿cuántas configuraciones diferentes pueden estar allí?, no es difícil para deducir. Con los símbolos de s y una cinta, la cual es n cuadrados de longitud, nosotros podemos tener sólo sn cintas diferentes. La cabeza de la cinta puede estar en cualquiera de los cuadrados de n y estar ejecutando cualquiera de las instrucciones de k.

Hay sólo así el k*n*sn posibles configuraciones diferentes para el ALA. Nosotros observamos que si el autómata linealmente acotado entra en la misma configuración dos veces entonces hará esto de nuevo y de nuevo y de nuevo. Es atrancado en una vuelta. Si no ha detenido, entonces debe estar en una vuelta y nunca detenerse.

Por ejemplo, consideremos el LBA definido por:

Q ={q1, q2}, S ={a, b}, G ={a, b, <, >}, F ={q2}, q0 =q1 y d dado por:
d (q1, <) = (q1, <, R)
d (q1, a) = (q1, b, R)
d (q1, b) = (q1, a, R)

d (q1, >) = (q1, >, S), donde S significa "permanecer", es decir no mover la cabeza de lectura/escritura. Este LBA complementa sus cadenas de entrada convirtiendo las a’s en b’s y viceversa. Obsérvese que, aunque puede reconocer y trabajar sobre los símbolos < y >, no puede reemplazarlos o moverse más allá de ellos. Supongamos que un LBA comienza siempre con su cabeza situada sobre el símbolo <.

Lenguajes no reconocidos por un autómata linealmente acotado

  • Lenguajes producidos por una gramática de Tipo0, lenguajes sin restricciones.
  • Lenguajes recursivamente enumerables, los cuales sólo son reconocidos por las máquinas de Turing.
Obtenido de "Aut%C3%B3matas linealmente acotados"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Jerarquía de Chomsky — Noam Chomsky. En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956. Contenido …   Wikipedia Español

  • Gramática (autómata) — Una gramática ( G ) desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.