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ù realistico di un [[computer]] rispetto una macchina di Turing.

 

 

{{Linguaggi formali e grammatiche}}

[[pl:Automat liniowo ograniczony]]

[[pt:Autômato linearmente limitado]]

[[zh:线性有界自动机]]