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..