I teoretisk informatikk , og spesielt i teori om automata , er en lineær avgrenset automat (på engelsk linear bounded automaton , forkortet som LBA ) en ikke-deterministisk Turing-maskin som bare bruker en sammenhengende del av stripen av lineær størrelse i inngangen. størrelse.
En lineært avgrenset automat oppfyller følgende tre betingelser:
Når det gjelder Turing-maskiner , har en lineært avgrenset automat en stripe som består av bokser som sannsynligvis inneholder et symbol hentet fra et endelig sett som kalles alfabetet , et hode kan lese innholdet i en boks og skrive i det og kan flyttes av 'en celle om gangen, og til slutt har den et endelig antall stater.
I motsetning til en Turing-maskin , hvor båndet antas å ha potensielt uendelig lengde, i en lineært avgrenset automat, er bare en sammenhengende del av båndet, hvis lengde er en lineær funksjon av datalengden, tilgjengelig av lese- og skrivehodet. Dette segmentet avgrenses av boksene som inneholder sluttmarkørene.
Lineært avgrensede automater gjenkjenner nøyaktig klassen av kontekstuelle språk . For å vise at et kontekstuelt språk gjenkjennes av en lineært avgrenset automat, observerer vi at i en kontekstuell grammatikk forlenger et avlednings trinn alltid det produserte ordet. Hvis vi derfor prøver å redusere et ord til et aksiom, tilsvarer hvert trinn forkortelse av ordet. Dette er grunnen til at et begrenset minne er tilstrekkelig.
Argumentet, i den andre retningen, er litt lengre.
I 1960 , John Myhill innført en modell av automat nå kalles lineært avgrenset deterministisk automat . Kort tid etter beviste Lawrence Landweber at språk som er gjenkjent av lineært avgrensede deterministiske automata, er kontekstuelle. I 1964 introduserte Sige-Yuki Kuroda den mer generelle modellen for lineært avgrenset (ikke-deterministisk) automat som beskrevet ovenfor og beviste at de nøyaktig aksepterer kontekstuelle språk.
I sin banebrytende artikkel presenterer Kuroda to forskningsproblemer som har blitt kjent under det engelske navnet LBA problems .
Allerede Kuroda la merke til at et negativt svar på det andre problemet ville ha resultert i et negativt svar på det første. Men faktisk har det andre problemet et positivt svar. Dette er en konsekvens av setningen Immerman-Szelepcsényi som knytter NSPACE- og co-NSPACE-klassene. Dette resultatet, uavhengig bevist av Neil Immerman og Róbert Szelepcsényi i 1987 , tjente dem Gödel Prisen i 1995 . Når det gjelder det første problemet, er det fortsatt åpent i 2010 .