In informatica teorica , e in particolare in teoria degli automi , un lineare limitata automa (in inglese automa lineare limitato , abbreviato come LBA ) è un non-deterministico macchina di Turing che utilizza solo una parte contigua della striscia di dimensioni lineari nell'ingresso dimensione.
Un automa limitato linearmente soddisfa le seguenti tre condizioni:
Per quanto riguarda le macchine di Turing , un automa delimitato linearmente ha una striscia composta da scatole che probabilmente contengono un simbolo tratto da un insieme finito chiamato alfabeto , una testa può leggere il contenuto di una scatola e scrivere in essa e può essere spostata di 'uno cella alla volta, e infine ha un numero finito di stati.
A differenza di una macchina di Turing , dove si presume che il nastro abbia una lunghezza potenzialmente infinita, in un automa delimitato linearmente, solo una porzione contigua del nastro, la cui lunghezza è una funzione lineare della lunghezza dei dati, è accessibile dalla testina di lettura e scrittura. Questo segmento è delimitato dalle caselle contenenti gli indicatori di fine.
Gli automi limitati linearmente riconoscono esattamente la classe dei linguaggi contestuali . Per dimostrare che un linguaggio contestuale è riconosciuto da un automa delimitato linearmente, osserviamo che in una grammatica contestuale , un passo di una derivazione allunga sempre la parola prodotta. Quindi, se proviamo a ridurre una parola a un assioma, ogni passaggio equivale ad accorciare la parola. Questo è il motivo per cui è sufficiente una memoria limitata.
L'argomento, nella direzione opposta, è un po 'più lungo.
Nel 1960 , John Myhill introdusse un modello di automa ora chiamato automa deterministico delimitato linearmente . Poco dopo, Lawrence Landweber dimostra che le lingue riconosciute da automi deterministici limitati linearmente sono contestuali. Nel 1964, Sige-Yuki Kuroda introdusse il modello più generale di automi limitati linearmente (non deterministici) come descritto sopra e dimostrò che accettano esattamente i linguaggi contestuali.
Nel suo articolo fondamentale, Kuroda pone due problemi di ricerca che sono diventati famosi sotto il nome inglese di problemi LBA .
Già Kuroda aveva notato che una risposta negativa al secondo problema avrebbe portato a una risposta negativa al primo. Ma in effetti, il secondo problema ha una risposta positiva. Questa è una conseguenza del teorema di Immerman-Szelepcsényi che collega le classi NSPACE e co-NSPACE. Questo risultato, provato indipendentemente da Neil Immerman e Róbert Szelepcsényi nel 1987 , è valso loro il Premio Gödel nel 1995 . Per quanto riguarda il primo problema, nel 2010 è ancora aperto.