Automa lineare limitato

Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto (o di Tipo-1 secondo la gerarchia di Chomsky).

Come una macchina di Turing, il nastro di un LBA è composto da celle che possono contenere simboli appartenenti ad un alfabeto finito. L'automa possiede un numero finito di stati e la sua testina può leggere e scrivere una sola cella per volta.

Grammatiche di Tipo-1

L'unica restrizione posta nelle grammatiche di Tipo-1 è che le regole di produzione siano nella forma $\alpha \rightarrow \beta$ con $\left|\alpha \right|\leq \left|\beta \right|$.

Quindi nessuna derivazione di una stringa in linguaggio sensibile al contesto può contenere una forma sentenziale più lunga della stringa stessa. Dal momento che c'è una corrispondenza uno ad uno tra gli automi lineari limitati e queste grammatiche, non si necessita per il riconoscimento della stringa da parte dell'automa un nastro più lungo di quello occupato dalla stringa originale.

Bibliografia

• (EN) linear bounded automaton, in Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.