Autómatas delimitados lineales

Un autómata acotado lineal es una máquina de Turing no determinista de múltiples pistas con una cinta de cierta longitud finita acotada.

Length = function (Length of the initial input string, constant c)

Aquí,

Memory information ≤ c × Input information

El cálculo está restringido al área acotada constante. El alfabeto de entrada contiene dos símbolos especiales que sirven como marcadores del extremo izquierdo y marcadores del extremo derecho, lo que significa que las transiciones no se mueven a la izquierda del marcador del extremo izquierdo ni a la derecha del marcador del extremo derecho de la cinta.

Un autómata lineal acotado se puede definir como una tupla de 8 (Q, X, ∑, q 0 , ML, MR, δ, F) donde -

  • Q es un conjunto finito de estados

  • X es el alfabeto de la cinta

  • es el alfabeto de entrada

  • q0 es el estado inicial

  • ML es el marcador del extremo izquierdo

  • MRes el marcador del extremo derecho donde M R ≠ M L

  • δ es una función de transición que asigna cada par (estado, símbolo de cinta) a (estado, símbolo de cinta, constante 'c') donde c puede ser 0 o +1 o -1

  • F es el conjunto de estados finales

Un autómata delimitado lineal determinista es siempre context-sensitive y el autómata lineal acotado con lenguaje vacío es undecidable..