Automa lineare limitato: differenze tra le versioni

Un '''Automa lineare limitato''' (abbreviato in inglese '''LBA''') è una forma ristretta di una [[macchina di Turing non deterministica]]. Possiede un nastro composto di celle che possono contenere simboli di un [[alfabeto]] [[insieme finito|finito]], una testina che può leggere o scrivere una cella sul nastro per volta e può essere mossa e un finito numero di stati. Differisce da una macchina di Turing per il fatto che mentre per la prima il nastro è inizialmente considerato infinito, per la seconda solo una porzione finita e contigua della lunghezza dell'input iniziale che è una [[funzione lineare]] può essere acceduto dalla testina di lettura/scrittura. Questa limitazione rende una LBA un modello più accurato di un [[computer]] che attualmente esiste che una macchina di Turing in alcuni aspetti.

 

 

{{Linguaggi formali e grammatiche}}