Automa lineare limitato: differenze tra le versioni

Un '''automa lineare limitato''' (in [[lingua inglese|inglese]] ''linear bounded automata'', '''LBA''') è una particolare [[macchina di Turing non deterministica]] in cui la lunghezza del nastro è [[funzione lineare]] della dimensione dell'input.<ref>{{Cita|Academic Press Dictionary of Science and Technology}}.</ref> Questi automi sono in grado di accettare i [[linguaggio dipendente dal contesto|linguaggi dipendenti dal contesto]] generati da [[grammatica dipendente dal contesto|grammatiche sensibili al contesto]] (o di Tipo-1 secondo la [[gerarchia di Chomsky]]).<ref>{{cita libro|titolo = Encyclopedia of Computer Science|url = https://archive.org/details/encyclopediaofco0000unse_y6v0|editore = Wiley |città = Hoboken |anno = 2003|lingua = inglese|capitolo = Formal languages}}</ref><ref>{{cita libro|titolo = Encyclopedia of Computer Science|url = https://archive.org/details/encyclopediaofco0000unse_y6v0|editore = Wiley |città = Hoboken |anno = 2003|lingua = inglese|capitolo = Chomsky hierarchy}}</ref>