Autòmat linealment acotat

Un autòmat linealment acotat , abreujadament LBA (de l'anglès, Linear bounded automaton ), o ALA és un autòmat similar a una màquina de Turing determinista.

Història

Si bé les màquines abstractes introduïdes fins llavors tenien com a objectiu el càlcul de funcions, amb el temps els investigadors es van encarregar d'estudiar la potència de les màquines com reconeixedores de llenguatges.

El mateix Noam Chomsky va establir el 1959 l'equivalència entre les gramàtiques de tipus 0 i les Màquines de Turing.

El 1958 Chomsky i Miller van notar que les gramàtiques de tipus 3 són equivalents als autòmats finits introduïts per Kleene en 1951.Chomsky i Marcel-Paul Schützenberger el 1963 van demostrar que les gramàtiques de tipus 2 equivalen als autòmats amb pila.

Finalment, el 1964 Kuroda descobreix que els llenguatges de tipus 1 són reconeguts pels autòmats linealment acotats.

Autòmats lineals

Els autòmats linealment acotats són similars a una màquina de Turing, sabem que aquesta última té una cinta infinita.

Un autòmat linealment acotat és una màquina de Turing la cinta està formada només per cel de kn de llarg, on la longitud n és la seqüència de l'entrada ik és una constant associada a l'autòmat linealment acotat particular, és a dir la quantitat de cinta que l'autòmat permet utilitzar es limita per un factor lineal k perquè quan entre una paraula de grandària n (els símbols de n), la màquina determini si la paraula és acceptable, o si la paraula està en el llenguatge de l'autòmat.

La diferència amb una màquina de Turing, consisteix que l'entrada de la cadena a la cinta és l'únic espai que la cinta permet usar, tot el procés es fa entre els marcadors de l'extrem Un autòmat linealment acotat té més poder que els autòmats de pila no determinístics, però menys poder que les màquines de Turing.

Els autòmats linealment acotats es basen en la gramàtica de Tipus 1 (sensibles al context).

«	Per a cada llenguatge sensible al context L existeix un autòmat linealment-acotat M tals que $L=L(M)$ , és a dir, M accepta exactament les seqüències de L.	»
— Teorema

«	Per a cada llenguatge L acceptada per un autòmat linealment-acotat ALA hi ha una gramàtica sensible al context que produeixi exactament $LM=L(G)$ .	»
— Teorema

Components

Un autòmat linealment acotat està format pels següents components:

M:{Q, A, B, δ, q0, F, #, $}

Q	Espai de l'estat finit
A	Alfabet d'entrada
B	Alfabet de la cinta
Δ	Funció de transició
Q0	L'estat inicial
F	Els estats finals
#	Símbol distingit d'inici de cinta
$	Símbol distingit de fi de cinta

{L, R, H}: accions de la cinta: L = moviment a l'esquerra, R = moviment a la dreta, H = moviment nul.

En cap cinta es permet δ (#, L) ni δ ($, R) òssia no es pot anar més enllà dels símbols que delimiten la cinta.

Un autòmat linealment acotat és un autòmat finit amb una cinta T d'accés de lectura/escriptura d'una longitud determinada per la cadena d'entrada W. M té un cap de lectura/escriptura la qual es mou a l'esquerra o dreta en un determinat espai de temps, però no es pot moure fora de la cinta. El nom de "linealment tancat" es refereix al fet que la capacitat d'emmagatzematge T, és un múltiple constant de la capacitat que va exigir tenir W. M té un alfabet B que conté un subconjunt A, i típicament té caràcters addicionals usats per al treball improvisat.

Els autòmats linealment acotats es van desenvolupar per modelar processos computacionals, són importants en la teoria de còmput encara que d'ells no han sorgit tantes aplicacions comparat a la magnitud que els autòmats de pila gaudeixen.

Els ordinadors són dispositius finits. Elles no tenen quantitats inacabables d'emmagatzematge com les màquines de Turing. Així qualsevol càlcul real fet en un ordinador no és tan extens com el que podria completar-se en una màquina de Turing. Per imitar les computadores, s'ha de restringir la capacitat de l'emmagatzematge de les màquines de Turing.

Un autòmat linealment acotat (ALA) és una màquina de Turing multi-adreces que té només una cinta, i aquesta cinta és exactament de la mateixa longitud de la d'entrada. Per establir els límits de la cinta s'empren els símbols # a l'esquerra i $ a la dreta, els quals no permeten a la màquina anar més enllà d'ells.

Llenguatges no reconeguts per un autòmat linealment acotat

Llenguatges recursivament enumerables

Enllaços externs

Nota