Az elméleti számítástechnikában , és különösen az automaták elméletében , a lineárisan korlátozott automata (angolul lineárisan korlátozott automata , rövidítve LBA ) egy nem determinisztikus Turing-gép, amely a lineáris méretű sávnak csak egy összefüggő részét használja a bejáratnál. méret.
Egy lineárisan korlátozott automata megfelel a következő három feltételnek:
Ami a Turing-gépeket illeti , egy lineárisan kötött automatán egy dobozokból álló csík található, amely valószínűleg egy ábécé nevű véges halmazból vett szimbólumot tartalmaz , egy fej elolvashatja a doboz tartalmát, és beleírhat, és 'eggyel mozgathatja. sejt egyszerre, és végül véges számú állapota van.
Ellentétben egy Turing-géppel , ahol feltételezzük, hogy a szalag potenciálisan végtelen hosszúságú, egy lineárisan korlátozott automatában csak a szalag egy szomszédos része érhető el, amelynek hossza az adathossz lineáris függvénye , az olvasó és író fej számára. Ezt a szegmenst a végjelzőket tartalmazó dobozok határolják.
A lineárisan behatárolt automaták pontosan felismerik a kontextuális nyelvek osztályát . Annak bemutatására, hogy a kontextus nyelvét lineárisan korlátozott automata ismeri fel, megfigyelhetjük, hogy egy kontextus szerinti nyelvtanban a levezetés egy lépése mindig meghosszabbítja az előállított szót. Ha tehát megpróbálunk egy szót axiómává redukálni, akkor minden lépés a szó rövidítését jelenti. Ezért elegendő a korlátozott memória.
Az érvelés a másik irányban kissé hosszabb.
A 1960 , John Myhill bevezetett modellje egy automata most hívott egy lineárisan korlátos determinisztikus automatát . Röviddel ezután Lawrence Landweber bebizonyítja, hogy a lineárisan korlátozott determinisztikus automaták által felismert nyelvek kontextuálisak. 1964-ben Sige-Yuki Kuroda bevezette a lineárisan behatárolt (nem determinisztikus) automata általánosabb modelljét, a fent leírtak szerint, és bebizonyította, hogy pontosan elfogadják a kontextus nyelvét.
Kuroda alapvető cikkében két olyan kutatási problémát vet fel, amelyek az angol LBA problémák néven váltak híressé .
Kuroda már észrevette, hogy a második problémára adott nemleges válasz az elsőre negatív választ eredményezett volna. De valójában a második problémára pozitív válasz van. Ez annak a következménye, hogy az Immerman -Szelepcsényi tétel összekapcsolja az NSPACE és a co-NSPACE osztályokat. Ez az eredmény, függetlenül bizonyítja Neil Immerman és Róbert Szelepcsényi a 1987 , szerzett nekik a Gödel-díjat az 1995 . Az első problémát illetően 2010-ben még mindig nyitott.