În informatică teoretică , și în special în teoria automatelor , un automat liniar mărginit (în engleză linear bounded automaton , prescurtat ca LBA ) este o mașină Turing nedeterministă care folosește doar o porțiune contiguă a benzii de dimensiune liniară la intrare mărimea.
Un automat delimitat liniar îndeplinește următoarele trei condiții:
În ceea ce privește mașinile Turing , un automat delimitat liniar are o bandă formată din cutii susceptibile să conțină un simbol preluat dintr-un set finit numit alfabet , un cap poate citi conținutul unei cutii și scrie în ea și poate fi mutat de „unul” celulă la un moment dat și, în cele din urmă, are un număr finit de stări.
Spre deosebire de o mașină Turing , unde se presupune că banda are o lungime potențial infinită, într-un automat delimitat liniar, doar o porțiune contiguă a benzii, a cărei lungime este o funcție liniară a lungimii datelor, este accesibilă prin capul de citire și scriere. Acest segment este delimitat de casetele care conțin marcajele finale.
Automatele delimitate liniar recunosc exact clasa limbajelor contextuale . Pentru a arăta că un limbaj contextual este recunoscut de un automat mărginit liniar, observăm că într-o gramatică contextuală , un pas al unei derivări întinde întotdeauna cuvântul produs. Dacă încercăm, prin urmare, să reducem un cuvânt la o axiomă, fiecare pas înseamnă scurtarea cuvântului. Acesta este motivul pentru care o memorie limitată este suficientă.
Argumentul, în cealaltă direcție, este puțin mai lung.
În 1960 , John Myhill a introdus un model de automat numit acum un automat determinist mărginit liniar . La scurt timp, Lawrence Landweber demonstrează că limbile recunoscute de automatele deterministe delimitate liniar sunt contextuale. În 1964, Sige-Yuki Kuroda a introdus modelul mai general al automatului delimitat liniar (nedeterminist) așa cum este descris mai sus și a dovedit că acceptă exact limbaje contextuale.
În articolul său seminal, Kuroda pune două probleme de cercetare care au devenit celebre sub numele englez LBA problems .
Deja Kuroda a observat că un răspuns negativ la a doua problemă ar fi rezultat într-un răspuns negativ la prima. Dar, de fapt, a doua problemă are un răspuns pozitiv. Aceasta este o consecință a teoremei Immerman-Szelepcsényi care leagă clasele NSPACE și co-NSPACE. Acest rezultat, dovedit independent de Neil Immerman și Róbert Szelepcsényi în 1987 , le-a adus premiul Gödel în 1995 . În ceea ce privește prima problemă, în 2010 este încă deschisă.