Linearno ograničen automat

Linearno ograničen automat (LOA) (još i omeđeni stroj^[1]) je ograničen oblik nedeterminističkog Turingovog stroja. Posjeduje diskretnu traku koja sadrži znakove (simbole) konačne abecede, pomičnu glavu za čitanje i pisanje koja operira vremenski diskretno, te konačan skup stanja. Razlikuje se od Turingovog stroja u tome što, iako se vrpca na početku smatra beskonačne duljine, samo konačni kontinuirani njezin dio čija je duljina linearno proporcionalna duljini početnog ulaznog niza se može čitati/pisati od strane glave za čitanje i pisanje. Ovo ograničenje čini LOA nešto preciznijim modelom stvarnog računala nego Turingov stroj.

Linearno ograničeni automati prihvaćaju klasu kontekstno ovisnih jezika. Jedino ograničenje nad gramatikom takvih jezika jest da ne postoji produkcija koja preslikava niz znakova (string) u kraći niz znakova. Stoga ne postoji produkcija niza znakova u kontekstno ovisnom jeziku koja sadrži rečenični oblik dulji od samog niza. Budući da postoji bijektivna korespondencija između linearno ograničenog automata i takvih gramatika, nije potrebno više vrpce nego što zauzima početni niz znakova da bi sam niz znakova bio prepoznat od strane linearno ograničenog automata.