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, onlyper ala finiteseconda contiguoussolo portionuna whoseporzione lengthfinita ise acontigua [[lineardella function]]lunghezza ofdell'input theiniziale lengthche ofè theuna initial[[funzione inputlineare]] canpuò beessere accessedacceduto bydalla thetestina read/writedi headlettura/scrittura. Questa Thislimitazione limitationrende makes anuna LBA aun moremodello accuratepiù modelaccurato ofdi un [[computer]]sthatche actuallyattualmente existesiste thanche auna Turingmacchina machinedi Turing in somealcuni respectsaspetti.
LinearGli boundedautomi automatalineari arelimitati sono [[accepter|accepters]] for the class of [[context-sensitive language]]s. The only restriction placed on [[grammars]] for such languages is that no production maps a string to a shorter string. Thus no derivation of a string in a context-sensitive language can contain a [[sentential form]] longer than the string itself. Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string to be recognized by the automaton.
