Introducción a los autómatas acotados lineales (LBA)

Historia: En 1960, Myhill
introdujo el modelo de autómata de grado asociado y en la actualidad este modelo de automatización se entiende como un autómata lineal determinista limitado. Después de esto, otro científico llamado Landweber trabajó en esto y propuso que los lenguajes aceptados por un LBA determinista son lenguajes continuamente sensibles al contexto.

En 1964, Kuroda introdujo un reemplazo y muchos modelos generales especialmente para autómatas acotados lineales no deterministas, y estableció que los lenguajes aceptados por los autómatas acotados lineales no deterministas son exactamente los lenguajes sensibles al contexto.

Introducción a los autómatas acotados lineales:
un autómata acotado lineal (LBA) es similar a la máquina de Turing con algunas propiedades que se indican a continuación:

• Máquina de Turing con lógica no determinista ,
• Máquina de Turing con multipista y
• Máquina de Turing con una longitud finita acotada de la cinta.

                                                                 

      

Tuplas utilizadas en LBA: 
LBA se puede definir con ocho tuplas (elementos que ayudan a diseñar autómatas) como: 

M = (Q , T , E , q0 , ML , MR , S , F), 

where,  
Q -> A finite set of transition states
T -> Tape alphabet
E -> Input alphabet
q0 -> Initial state
ML-> Left bound of tape
MR -> Right bound of tape
S -> Transition Function
F -> A finite set of final states 

Representación esquemática de LBA:

Ejemplos:

Idiomas que forman LBA con cinta como se muestra arriba,

• L = {una ^n! | norte >= 0}
• L = {wn | w de {a, b}+, n >= 1}
• L = {wwwR | w de {a, b}+}

Hechos :

Suppose that a given LBA M has
    --> q states,
    --> m characters within the tape alphabet, and
    --> the input length is n

1. Entonces M puede estar como máximo en f(n) = q * n * mn configuraciones, es decir, una cinta de n celdas ym símbolos, podemos tener únicamente mn cintas totalmente diferentes.
2. El cabezal de la cinta suele estar en cualquiera de las n celdas que suelen ser pena de muerte en cualquiera de los q estados.